二叉树

二叉树的特点

• 每个节点度最大为2(最多拥有两颗子树)

• 左子树和右子树是有顺序的

• 即使某节点只有一棵树，也要区分左右子树

二叉树的性质

• 非空二叉树的第i层，最多有2^n-1个节点（i >= 1）

• 高度为h的二叉树上最多有 2^h - 1个节点（h >= 1）

• 对于任何一颗非空二叉树,如果叶子节点个数为n0,度为2的节点个数为n2,则有：n0 = n2 + 1

• 对于任何一棵非空二叉树,如果叶子节点个数为n0,度为2的节点个数为n2，则有n0 = n2 + 1

• 二叉树的边数T = n1 + 2 * n2 = n - 1 = n0 + n1 - n2 - 1

真二叉树

• 所有的度要么为0 要么为2

完全二叉树

• 叶子节点只出现在最后两层，且最后1层叶子都靠左对齐

• 完全二叉树从更节点至倒数第二层是一棵满二叉树

性质

• 度为1的只有左子树
• 度为1的节点要么0个要么1个
• 至少有2^h-1 个节点 (2^0 ...+ 2^h-2 + 1)