树的基本概念

• 节点, 根节点,父节点,子节点,兄弟节点.
• 一棵树可以没有任何节点,称为空树.
• 一棵树可以只有一个节点,也就是根节点.
• 子树,左子树,右子树.
• 节点的度(degree):子树的个数.
• 树的度:所有节点度中的最大值.
• 叶子节点(leaf): 度为0的节点.
• 非叶子节点:度不为0的节点.
• 层数(level):根节点在第一层,根节点的子节点在第二层,依次类推.
• 节点的深度(depth):从根节点到当前节点的唯一路径上的节点总数.
• 树的深度:所有节点深度中的最大值.
• 节点的高度(height):从当前节点到最远节点的路径上的节点总数.
• 树的高度:所有节点高度中的最大值.
• 树的深度 等于 树的高度.

二叉树的特点

• 每个节点的度最大为2(最多拥有2棵子树).
• 左子树 和 右子树是有顺序的.
• 即使某节点只有一颗子树,也要区分左右子树.

二叉树的性质

• 非空二叉树的第 i 层,最多有2^i-1个节点( i >= 1 ).
• 高度为h的二叉树上最多有2^h - 1 个节点(h >= 1).
• 对于任何一棵非空二叉树,如果叶子节点个数为n0,度为2的节点个数为n2,则有:n0 = n2 + 1
• 假设度为1的节点个数为n1,那么二叉树的节点总数 n = n0 + n1 + n2
• 二叉树的边树 T = n1 + 2 * n2 = n - 1 = n0 + n1 + n2
• 因此 n0 = n2 + 1