树的性质小总结

树的性质总结

树的定义

树是一种非线性存储结构，通常用来存储逻辑关系为 "一对多" 的数据。

T=（D，R）

树是n（n≥0）结点的有限集合。n=0时，称为空树。

1. 有且仅有一个结点d0∈D,它对于关系来说没有前驱结点，结点d0称为根的结点。
2. 除根结点外，D中每个结点有且仅有一个前驱结点，但可以有多个后继结点。
3. D中可以有多个终端结点。

实际上顺序表、链式表就是特殊的树 

树的递归定义

在任意非空树T（有一个或多个结点组成的有限集）中应满足：
1）有且仅有一个特定的称为根的结点。
2）当n>1时，其余结点可分为m（m>0）个互不相交的有限集合，其中每个集合本身又是一棵树，并且称为根结点的子树。
 

注意：一棵树（包括二叉树）的最少结点个数为 0（空树）

树的逻辑结构表示

树的逻辑结构表示有树状表示法、文氏图表示法、凹入表示法和括号表示法等。

1. 树状表示法。这是树的基本逻辑结构表示形式，使用一棵倒置的树表示树的结构。如上图树。
2. 文氏图表示法。使用集合以及集合的包含关系描述树的结构。（集合之间绝不能相交，即任意两个圆圈不能有交集），如图二左。
3. 凹入表示法。使用线段的伸缩关系来描述树的结构。如图二右。

1. 
2. 4.括号表示法，将树的根节点写在括号的左边，除根结点之外的其余结点写在括号中，并用逗号隔开。

树的基本术语

1）结点的度：一个结点含有的子树的个数称为该结点的度；

2）叶子结点或终端结点：度为0的结点称为叶子结点；

3）非终端结点或分支结点：度不为0的结点；

4）双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点；

5）孩子结点或子结点：一个结点含有的子树的结点称为该结点的子结点；

6）兄弟结点：具有相同双亲结点的结点互称为兄弟结点；

7)树的度：一棵树中，最大的结点的度称为树的度；

8)结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推；

9)树的高度或深度：树中结点的最大层次；

10)堂兄弟结点：双亲在同一层的结点互为堂兄弟；

11) 祖先结点：从根到该结点所经分支上的所有结点；

12)子孙结点：以某结点为根的子树中除自身结点外任一结点都称为该结点的子孙结点。

13)森林：由m（m>=0）棵互不相交的树的集合称为森林；

树的性质

1. 树中的结点数为所有结点的度数加1（1既加根结点）。

除去树根的结点数=总分支数=所有结点的度之和；

树中的结点数=除去树根的结点数+1=所有结点的度之和+1。

1. 度为m的树中第i层最多有mi-1个结点（i>=1）。
2. 高度为h的m次树至多(mh-1)/(m-1)个结点。

结合性质二知道第i层最多结点数为mi-1

所以  整棵树的最多结点数=每一层最多结点书之和

                        =m0+m1+…+mh-1

4） 具有n个结点的m次树的最小高度为logm( n(m-1) + 1 )  向上取整。

叶子结点：假如树的度为N（当为二叉树时N0=1+n2)

N0=1+n2+2*n3+…+(N-1)*nN

用该公式可以直接求得：

N0=1+2+2*1+3*1=8(n2为度数为2的结点个数，n3为度数为3的结点个数，n4为度数为4的结点个数)

N0=1+5+2*6=18  也成立