二叉树中的判断有以下几种:
是否完全二叉树、是否满二叉树、是否为BST树、是否为平衡二叉树、是否为对称二叉树、完美二叉树
满二叉树:
除最后一层无任何子节点外,每一层上的所有结点都有两个子结点的二叉树。
上述所示图除最外一层节点之外,每个节点都有两个子节点,所以上述两图都是满二叉树!!!
完全二叉树:
完全二叉树是满二叉树的一直特例,怎么个特例法呢?
上图为啥有些是完全二叉树,有些又不是完全二叉树呢?
完全二叉树定义:完全二叉树(Complete Binary Tree):若设二叉树的高度为h。除第h层外,其它各层(0~h-1)的结点数都达到最大个数,第h层从右向左连续缺若干结点,这就是完全二叉树
上述所说从右向左缺若干节点,也就是说在h层的时候,如果有节点都在左半边,而缺的都是右半边的节点,这就是完全二叉树!
BST树(二叉搜索树)
这玩意就是说,右孩子的节点比双亲结点大,左孩子的节点比双亲节点小,从根节点走出来之后,左子树和右子树都按照这个大小再次进行排序!!!
平衡二叉搜索树(AVL树)
两子树高度相差不超过1的搜索二叉树即为平衡搜索二叉树!!!
对称二叉树
如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。
最后再了解一下完美二叉树
除了最外层叶子结点之外的每一个结点都有两个孩子,每一层(当然包含最后一层)都被完全填充。