树的相关术语

树的相关术语

(2010-02-23 14:47:12)

标签： 二叉树 杂谈

树的相关术语

1. 结点（node）

2. 结点的度（degree of node）：结点所拥有的子树个数

3. 树的度（degree of tree）：树中各结点度的最大值

4. 叶子结点（leaf node）

5. 分支结点（branch node）

6. 结点的层次（level of node）：从根结点到某结点所经路径上的分支数称为该结点的层次。根结点的层次为1，其余结点为其父结点的层次+1

7. 树的深度：树中结点的最大层次数

 

 

二叉树（Binary Tree）：

n个相同类型的结点的有限集合

1）有且仅有一个根结点

2）除根结点外，其余结点被分成2个互不相交的集合

 

满二叉树（Full Binary Tree）：

树中只有度为0或2的结点，且度为0的结点在同一层次上

 

完全二叉树（Complete Binary Tree）:

叶子结点只能出现在层次最大的层上，并且某个结点下的左分支下子孙与右分支下子孙的最大层次相等或大于1

 

 

二叉树的性质：

1. 一棵非空二叉树的第i层上最多有2^i-1个结点

2. 若规定空树的深度为0，则深度为K的二叉树最多有2^k-1个结点

3. 具有n个结点的完全二叉树的深度k为log₂n+1

4. 对于一棵非空二叉树，如果度为0的结点个数为n₀，度为2的结点个数为n₂，则有n₀=n₂+1

5. 对于具有n个结点的完全二叉树，如果按照从上到下和从左到右的顺序对所有结点从1开始编号，则对于序号为i的结点，有：

1）如果i>1，则序号i的结点的双亲结点的序号为i/2；如果i=1，则该结点为根结点，无双亲结点

2）如果2i<=n，则该结点的左孩子的结点序号为2i；如果2i>n，则该结点无左孩子

3）如果2i+1<=n，则该结点的右孩子的结点序号为2i+1；如果2i+1<n，则该结点无右孩子