本文共 1055 字，大约阅读时间需要 3 分钟。

一、常用术语：

1）树的节点

2）节点路径：

从根节点到该节点所经历的节点和分支的顺序。

3）路径长度：

节点路径包含的分支数。

4）节点的度：

节点拥有的子树的数目。

5）树的度：

所有节点的度  中 的最大值。

6）叶子节点（终端节点）

树中 节点的度为0的节点。

7）分支节点（非终端节点）

树中 节点的度不为0的节点。树中除了叶子节点的其他节点。

8）孩子节点（子节点）

一个节点的子节点是指 该节点 子树的根结点。

9）双亲节点（父节点）

如果一个节点有子节点，那么他就是这个子节点的父节点。

10）子孙节点

一个节点的子孙节点是指这个节点的所有子树中的任意节点。

11）祖先节点

一个节点的祖先节点是指该节点的路径中除此节点之外的所有节点。

12）兄弟节点

具有同一双亲的节点。

13）节点层次

根结点层次为 0，其他节点层次为 父节点层次 +1。

14）树的深度

所有节点中层次数最大值 +1。

15）有序树

各节点的所有子树之间从左到右有严格的次序关系，不能互换。

16）无序树

各节点的所有子树之间没有严格的次序关系。

17）森林

m（m>=0)棵互不相交的树所构成的集合。

二、二叉树（特殊的树）

1、每个节点最多有两棵子树，并且子树也是二叉树。

2、二叉树允许只有右子树；一般树中不允许。

3、满二叉树

4、完全二叉树

5、单分支树

1）定义：所有节点没有右孩子或没有左孩子。

2）例如

三、二叉树的性质

1、二叉树中第i（i>=0)层上的节点数最多为2的i次幂。

2、深度为h（h>=1)的二叉树最多有2^h -1 个节点

3、叶子节点为n0，度为2的节点个数为n2则 n0 = n2 +1。

4、具有n个节点的完全二叉树，其深度为log2（n）+ 1 或者 log2（n+1)

5、对于具有n个节点的完全二叉树，节点从0开始编号。

1）i = 0  二叉树的根结点；i>1,i节点的双亲编号（i-1)/2。

2）若2i+1>=n,i节点无左孩子，否则 2i+1 为其左孩子

3）若2i+2>=n,i节点无右孩子，否则 2i+2 为其右孩子

4、二叉树 与 树 、森林的转换

1）二叉树与树的转换

树 —>二叉树

（1）断右子（加线）

（2）连兄弟（断线）

（3）顺转45‘

二叉树 —> 树

（1）逆转45’（加线）

（2）断兄弟（断线）

（3）找双亲

2）二叉树 《=》树《=》 森林

森林 —> 树

方法：第一棵树根结点 为 树的根结点，其他树为右孩子

反之亦然

森林 <—> 二叉树