二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。
- 二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。
- 二叉树的第i层至多有2i-1个结点；深度为k的二叉树至多有2k-1个结点。
- 对于任意二叉树，叶子节点N0个，度为2的节点n2个，则满足n0=n2+1。
- 完全二叉树：若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层从右向左连续缺若干结点，这就是完全二叉树。
- 满二叉树：一棵深度为k，且有2k-1个节点的二叉树。特点：每一层上的结点数都是最大结点数。
- 具有n个结点的完全二叉树的深度为log2n+1。
- 二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
网友评论