满二叉树:如果一棵二叉树只有度为0的结点和度为2的结点,并且度为0的结点在同一层上,则这棵二叉树为满二叉树。深度为k,有2^k-1个节点的二叉树。
完全二叉树:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2^(h-1) 个节点。
二叉搜索树:一个有序树,若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;其左、右子树也分别为二叉排序树。
平衡二叉搜索树:又被称为AVL(Adelson-Velsky and Landis)树,且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1(不超过一层),并且左右两个子树都是一棵平衡二叉树。
二叉树可以链式存储,也可以顺序存储。链式存储方式就用指针, 顺序存储的方式就是用数组。
二叉树主要有两种遍历方式:
深度优先遍历:先往深走,遇到叶子节点再往回走。
前序遍历(递归法,迭代法):根左右(先序)
中序遍历(递归法,迭代法):左根右
后序遍历(递归法,迭代法):左右根
广度优先遍历:一层一层的去遍历。
层次遍历(迭代法)
链式存储的二叉树节点的定义方式:
public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } }标签:结点,遍历,TreeNode,val,二叉树,节点 From: https://www.cnblogs.com/cjhtxdy/p/17024869.html