树和二叉树

(一)、树的基本概念

1.树的定义和基本术

（1）树的定义

       树(Tree)是n(n≧0)个结点的有限集合T，若n=0时称为空树，否则：

a.有且只有一个特殊的称为树的根(Root)结点；

      b.若n>1时，其余的结点被分为m(m>0)个互不相交的子集T1, T2,

T3…Tm，其中每个子集本身又是一棵树，称其为根的子树(Subtree)。

（2）树的基本术语

a.结点(node)：一个数据元素及其若干指向其子树的分支。

b.结点的度(degree) 、树的度：结点所拥有的子树的棵数称为结点的度。树中结点度的最大值称为树的度。

结点A的度是3 ，结点B的度是2 ，结点M的度是0，树的度是3 。

c.叶子(left)结点、非叶子结点：

树中度为0的结点称为叶子结点(或终端结点)。

度不为0的结点称为非叶子结点(或非终端结点或分支结点)。

除根结点外，分支结点又称为内部结点。

d.孩子结点、双亲结点、兄弟结点

一个结点的子树的根称为该结点的孩子结点(child)或子结点；该结点是其孩子结点的双亲结点(parent)或父结点。

e.层次、堂兄弟结点

规定树中根结点的层次为1，其余结点的层次等于其双亲结点的层次加1。双亲结点在同一层上的所有结点互称为堂兄弟结点。

f.结点的层次路径、祖先、子孙

从根结点开始，到达某结点p所经过的所有结点成为结点p的层次路径(有且只有一条)。

结点p的层次路径上的所有结点（p除外）称为p的祖(ancester) 。以某一结点为根的子树中的任意结点称为该结点的子孙结点(descent)。

g.树的深度(depth)

树中结点的最大层次值，又称为树的高度。

h.有序树和无序树

对于一棵树，若其中每一个结点的子树（若有）具有一定的次序，则该

树称为有序树，否则称为无序树。

i.森林(forest)

是m(m≧0)棵互不相交的树的集合。显然，若将一棵树的根结点删除，剩余的子树就构成了森林。

（3）树的表示形式

a.倒悬树。

是最常用的表示形式

b.嵌套集合。

是一些集合的集体，对于任何两个集合，或者不相交，或者一个集合包含另一个集合。

c.广义表形式。

(A(B(E(K,L),F),C(G(M,N)),D(H,I,G)))

d.凹入法表示形式。

1.树的抽象数据类型定义

    ADT Tree

{

数据对象D：D是具有相同数据类型的数据元素的集合。

数据关系R：若D为空集，则称为空树；

……

基本操作：

……

} ADT Tree

(二)、二叉树

1.二叉树的定义

二叉树(Binary tree)是n(n≥0)个结点的有限集合。若n=0时称为空树，否则：

⑴ 有且只有一个特殊的称为树的根(Root)结点；

⑵ 若n>1时，其余的结点被分成为二个互不相交的子集T1,T2，分别称之为左、右子树，并且左、右子树又都是二叉树。

2.二叉树的基本形态

二叉树有5种基本形态。

3.二叉树的性质

性质1：在非空二叉树中，第i层上至多有2i-1个结点(i≧1)

性质2：深度为k的二叉树至多有2k-1个结点（k≧1) 。

性质3：对任何一棵二叉树，若其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1。

性质4：n个结点的完全二叉树深度为：[㏒2n]+1。

性质5：若对一棵有n个结点的完全二叉树(深度为└㏒2n┘+1)的结点按层（从第1层到第㏒2n +1层)序自左至右进行编号,则对于编号为i（1≦i≦n)的结点：

⑴ 若i=1：则结点i是二叉树的根，无双亲结点；否则，若

i>1，则其双亲结点编号是 i/2 。

⑵ 如果2i>n：则结点i为叶子结点，无左孩子；否则，其左

孩子结点编号是2i。

⑶ 如果2i+1>n：则结点i无右孩子；否则，其右孩子结点编

号是2i+1

4.满二叉树

（1）一棵深度为k且有2k-1个结点的二叉树称为满二叉树(Full Binary Tree)。

（2）满二叉树的特点

    (1)每一层上的结点数总是最大结点数。

(2) 所有的支结点都有左、右子树。

(3）对满二叉树的结点进行连续编号，若规定从根结点开始，按“自上而下、自左至右”的原则进行。

5.完全二叉树

（1）深度为k，由n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应，该二叉树称为完全二叉树。或深度为k的满二叉树中编号从1到n的前n个结点构成了一棵深度为k的完全二叉树。其中 2k-1 ≦ n≦2k-1。

（2）完全二叉树的特点

    若完全二叉树的深度为k ，则所有的叶子结点都出现在第k层或k-1层。对于任一结点，如果其右子树的最大层次为l，则其左子树的最大层次为l或l+1。

6.二叉树的存储结构

1 顺序存储结构

二叉树存储结构的类型定义：

#define MAX_SIZE 100

typedef telemtype sqbitree[MAX_SIZE];

用一组地址连续的存储单元依次“自上而下、自左至右”存储完全二叉树的数据元素

2 链式存储结构

(1) 结点的类型及其定义

① 二叉链表结点。有三个域：一个数据域，两个分别指向左右子结点的指针域。

typedef struct BTNode

{ ElemType data ;

struct BTNode *Lchild , *Rchild ;

}BTNode ;

② 三叉链表结点。除二叉链表的三个域外，再增加一个指针域，用来指向结点的父结点。

typedef struct BTNode_3

{ ElemType data ;

struct BTNode_3 *Lchild , *Rchild , *parent ;

}BTNode_3 ;

(2) 二叉树的链式存储形式