数据结构-第6章 树和二叉树

第6章树和二叉树6.1树的定义和基本术语6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.5赫夫曼树及其应用6.1树的定义和基本术语6.1.1树的定义6.1.2基本术语6.1.3树的表示1.树的定义树是由n（n≥0）个结点组成的有限集合。若n=0，称为空树；若n>0，则：

（1）有且仅有一个特定的称为根（root）的结点。它只有直接后继，但没有直接前驱；

（2）当n>1时,其余结点可以划分为m（m>0）个互不相交的有限集合T1，T2，…，Tm，每个集合又是一棵树，称为根的子树，每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。

由此可知，树的定义是一个递归的定义，即树的定义中又用到了树的概念。树的结构参见图6-1。6.1.1树的定义一棵树的逻辑结构可以用二元组描述为：

tree=(k,R)k={ki∣1≤i≤n;n≥0,ki∈elemtype}R={r}

其中，n为树中结点个数，若n=0，则为一棵空树，n>0时称为一棵非空树，而关系r应满足下列条件：

（1）有且仅有一个结点没有前驱,称该结点为树根;

（2）除根结点以外,其余每个结点有且仅有一个直接前驱;

（3）树中每个结点可以有多个直接后继(孩子结点)。2.树的逻辑结构描述例如，对图6-1(c)的树结构,可以二元组表示为：

K={A，B，C，D，E，F，G，H，I，J，K，L，M}

R={r}

r={<A,B>，<A,C>，<A,D>，<B,E>，<B,F>，<C,G>，<D,H>，<D,I>，<E,J>，<E,K>，<E,L>，<H,M>}(1)InitTree(&T)初始化树T。

(2)Root(T)求树T的根结点(3)Parent(T,x)求树T中，值为x的结点的双亲。

(4)Child(T,x,i)求树T中，值为x的结点的第i个孩子。

(5)AddChild(y,i,x)把值为x的结点作为值为y的结点的第i个孩子插入到树中。

(6)DelChild(x,i)删除值为x的结点的第i个孩子。

(7)TraverseTree(T)遍历或访问树T。3.树的基本运算1.结点:

树的结点包含一个数据元素及若干指向其子树的分支2.度:

一个结点包含子树的数目，称为该结点的度。

3.叶子（终端）结点

度为0的结点，称为叶子结点或树叶，也叫终端结点。

4.孩子结点

若结点X有子树，则子树的根结点为X的孩子结点，也称为孩子，儿子，子女等。如图6-1（c）中A的孩子为B，C，D。

5.双亲结点

若结点X有子女Y，则X为Y的双亲结点。6.1.2基本术语

6.祖先结点

从根结点到该结点所经过分支上的所有结点为该结点的祖先，如图6-1（c）中M的祖先有A，D，H。

7.子孙结点

某一结点的子女及子女的子女都为该结点子孙。

8.兄弟结点

具有同一个双亲的结点，称为兄弟结点。

9.分支结点

除叶子结点外的所有结点，为分支结点，也叫非终端结点。(度不为0的结点)

10．层数(层次)

根结点的层数为1，其它结点的层数为从根结点到该结点所经过的分支数目再加1。

11.树的高度（深度）

树中结点所处的最大层数称为树的高度，如空树的高度为0，只有一个根结点的树高度1。

12.树的度

树中结点度的最大值称为树的度。

13.有序树

若一棵树中所有子树从左到右的排序是有顺序的，不能颠倒次序。称该树为有序树。

14.无序树

若一棵树中所有子树的次序无关紧要，则称为无序树。

15．森林（树林）

若干棵互不相交的树组成的集合为森林。一棵树可以看成是一个特殊的森林。1．树形结构表示法6.1.3树的表示2.凹入法表示法

3.嵌套集合表示法4.广义表表示法

（A（B（E（J，K，L），F），C（G），D（H（M），I）））6.2二叉树6.2.1二叉树的定义6.2.2二叉树的性质6.2.3二叉树的存储结构6.2.1二叉树的定义1．二叉树的定义

和树结构定义类似，二叉树的定义也可以递归形式给出：二叉树是n（n≥0）个结点的有限集，它或者是空集（n=0），或者由一个根结点及两棵不相交的左子树和右子树组成。

二叉树的特点是每个结点最多有两个孩子，或者说，在二叉树中不存在度大于2的结点，并且二叉树是有序树（树为无序树），其子树的顺序不能颠倒。因此，二叉树有五种不同的形态。(a)空二叉树(b)仅有一个根结点的二叉树(c)右子树为空的二叉树(d)左子树为空的二叉树(e)左、右子树均非空的二叉树二叉树的五种基本形态（1）InitBitree(&T)二叉树的初始化。

（2）Root(T)求二叉树的根结点

（3）Parent(T,x)求二叉树T中值为x的结点的双亲（4）Lchild(T,x)求二叉树T中值为x的结点的左孩子。

（5）Rchild(T,x)求二叉树T中值为x的结点的右孩子。

（6）Lbrother(T,x)求二叉树T中值为x的结点的左兄弟。

（7）Rbrother(T,x)求二叉树T中值为x的结点的右兄弟。

2.二叉树的基本运算（8）Traverse(T)遍历二叉树T。

（9）CreateBiTree(&T)建立一棵二叉树T。

（10）AddLchild(&T,x,y)在二叉树T中，将值为y的结点作为值为x的结点的左孩子插入。

（11）AddRchild(&T,x,y)在二叉树T中，将值为y的结点作为值为x的结点的右孩子插入。

（12）DelLchild(&T,x)在二叉树T中，删除值为x的结点的左孩子。

（13）DelRchild(&T,x)在二叉树T中，删除值为x的结点的右孩子。性质1

若二叉树的层数从1开始，则二叉树的第i层结点数，最多为2i-1个（i≥1）。6.2.2二叉树的性质

20=121=222=423=8

深度（高度）为k的二叉树最大结点数为2k-1（k≥1）。证明:最大结点个数=20+21+22+……+2k-1

=2k-1性质2

对任意一棵二叉树，如果叶子结点个数为n0，度为2的结点个数为n2，则有n0=n2+1。证明：设n0,n1和n2分别为二叉树中度为0,度为1和度为2的结点个数，则二叉树中总的结点个数n满足：n=n0+n1+n2①

再有除了根结点之外，每个结点都由一个分支射入，则分支数B与总的结点数之间的关系为：

n=B+1②另外，由于这些分支是由度为1或2的结点射出的，则有B=n1+2n2③则由上三式得：n0=n2+1

性质3

为继续给出二叉树的其它性质，先定义两种特殊的二叉树：满二叉树

深度为k具有2k-1个结点的二叉树，称为满二叉树。完全二叉树

如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1--n的结点一一对应，则称这棵二叉树为完全二叉树。

具有n个结点的完全二叉树的深度为log2n+1证明：设深度为k,则由性质2和完全二叉树的性质有：

2k-1-1<n≤2k-1即

2k-1≤

n<

2k

则有

k-1≤

log2n

<

k由于k是整数，则有k=log2n+1性质4对于完全二叉树中任一个编号为i的结点(1≤i≤n)，它的父结点和左、右儿子结点的编号与i值有如下的关系：(1)如果i=1，则它是整个树的根结点，无父结点；若i>1，则其父结点编号为i/2。(2)如果2i≤n，则其左儿子结点编号为2i；若2i>n，则无左儿子结点。(3)如果（2i+1）≤n，则其右儿子结点编号为（2i+1）；反之，则无右儿子结点。性质56.2.3二叉树的存储结构1.顺序存储结构2.链式存储结构

1.顺序存储结构

思想:用一个一维数组来存储二叉树的各个结点C语言表示#defineMAX_TREE_SIZE100//二叉树的最大结点数typedefTElemTypeSqBiTree[MAX_TREE_SIZE];//0号单元存储根结点SqBiTreebt;分析:显然，二叉树的结点必须按某种次序分别存入数组的各个单元，这种次序应能反映结点间的逻辑关系，否则二叉树上的各种基本运算在顺序存储结构上很难实现。对于完全二叉树来说，可以采用“以编号为地址”的方法，将编号为i的结点存入一维数组的第i个单元(下标为i-1)。例:对应的顺序存储结构:下标123456789100123456789完全二叉树的顺序表示:例:对应的顺序存储结构:一维数组的21单元中只用上了7个.最坏情况下,一个深度为k且只有k个结点的单支树,却需要长度为2k-1的一维数组.非完全二叉树的顺序表示:总结:顺序存储结构适合存储完全二叉树对于非完全二叉树，采用链式存储结构更合适2.二叉链表结点结构:通常每个结点中设置三个域,即值域、左指针域和右指针域，其结点结构如下：其中data表示值域，用于存储放入结点的数据，lchild和rchild分别表示左指针域和右指针域，用以分别存储指向左儿子结点和右儿子结点的指针。

lchilddatarchild

存储表示typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BITree;

这里的TElemType可以是任何相应的数据类型如int、float或char等。二叉链表例:链式存储:3.三叉链表通常每个结点中设置四个域,即值域、左指针域、右指针域和双亲指针域，其结点结构如下：其中data表示值域，用于存储放入结点的数据，lchild和rchild分别表示左指针域和右指针域，用以分别存储指向左儿子结点和右儿子结点的指针,parent指向双亲结点。

lchilddata

rchildparent6.3遍历二叉树和线索二叉树

6.3.1遍历二叉树定义:二叉树的遍历(Traverse)是指按一定的规律访问二叉树的每个结点，且每个结点只被访问一次的过程。对二叉树的遍历过程实际上是将非线性结构的二叉树中的结点排列成一个线性序列的过程。本节仅讨论二叉链表的遍历过程。一个非空的二叉树由根结点及左、右子树这三个基本部分组成，因此若能依次遍历这三部分，便是遍历了整个二叉树。在任一给定结点上，可以按某种次序执行三个操作：访问结点本身，遍历该结点左子树，遍历该结点右子树，操作排列次序：①左、根、右；③根、左、右；⑤左、右、根；②右、根、左；④根、右、左；⑥右、左、根；由于实际问题一般都是要求左子树较右子树先遍历，故只采用其中①、③、⑤三种遍历次序，分别称为中序遍历、先序遍历和后序遍历。(1)中序（InOrder）遍历若遍历的二叉树为空，执行空操作；否则依次执行下列操作：中序遍历左子树；访问根结点；中序遍历右子树。(2)先序（PreOrder）遍历若遍历的二叉树为空，执行空操作；否则依次执行下列操作：访问根结点；先序遍历左子树；先序遍历右子树。三种遍历次序以递归的形式定义：(3)后序（PostOrder）遍历若遍历的二叉树为空，执行空操作；否则依次执行下列操作：后序遍历左子树；后序遍历右子树；访问根结点。中序遍历序列：

先序遍历序列：

后序遍历序列：

二叉树遍历举例HDIBEAFCGABDHIECFGHIDEBFGCA中序遍历递归算法voidInOrder(BITreeT){if(T){InOrder(T->lchild);visit(T->data);InOrder(T->rchild);}}先序遍历递归算法voidPreOrder(BITreeT){if(T){visit(T->data);PreOrder(T->lchild);PreOrder(T->rchild);}}后序遍历递归算法voidPostOrder(BITreeT){if(T){PostOrder(T->lchild);PostOrder(T->rchild);visit(T->data);}}遍历算法的应用二叉树的遍历算法是一个重要的应用注意:1.理解访问根结点的意义2.对具体问题需要考虑遍历的顺序1.先序创建二叉链表StatusCreateBiTree(BITree&T){scanf(&ch);if(ch==‘’)T=Null;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}returnOK;}2.输出二叉树的结点voidPreOrder(BITreeT){if(T){printf(T->data);PreOrder(T->lchild);PreOrder(T->rchild);}}3.输出二叉树的叶子结点voidPreOrder(BITreeT){if(T){if(T->lchild==NULL&&T->rchild==NULL)printf(T->data);PreOrder(T->lchild);PreOrder(T->rchild);}}4.统计二叉树的叶子结点个数intn=0;voidleafcount(BITreeT){if(T){if(T->lchild==NULL&&T->rchild==NULL)n++;leafcount(T->lchild);leafcount(T->rchild);}}5.求二叉树的高度intPostTreeDepth(BITreeT){if(T){hl=PostTreeDepth(T->lchild);hr=PostTreeDepth(T->rchild);max=hl>hr?hl:hr;return(max+1);}elsereturn0;}二叉树的非递归遍历可利用堆栈将递归算法改写成非递归的形式。下面以中序遍历为例来具体说明。T--*caba*--cb&--&*&a^^&b^^&c^^a*b--c中序非递归遍历算法分析：1.栈初始化,根指针入栈2.当栈非空时

(1)当栈顶元素非空时,左指针入栈向左走向尽头

(2)栈顶空指针出栈

(3)当栈非空时,

栈顶元素出栈并访问且将其右指针入栈算法实现：voidInOrder(BiTreeT){InitStack(S);Push(S,T);while(!StackEmpty(S)){while(GetTop(S,p)&&p)Push(S,p->lchild);Pop(S,p);if(!StackEmpty(S)){Pop(S,p);visit(p->data);Push(S,p->rchild);}//if}//while}6.3.2线索二叉树相关概念:在一个n结点的链式存储二叉树中，有n+1个指针域是空指针域，可以把每个空指针域用于存放分别指向某种遍历次序的前趋和后继结点的指针。线索:在结点的空指针域中存放的该结点在某遍历次序下的前趋结点和后继结点的指针叫做线索。线索二叉树:对一个二叉树中的所有结点的空指针域按照某种遍历次序加线索的过程叫作线索化，被线索化了的二叉树称作线索二叉树。在一个线索二叉树中，必须设法将线索与指向结点左、右儿子结点的指针加以区别。可给每个结点增加两个标志域，即左线索标志域LTag，右线索标志域RTag。LTagRTaglchild域指示结点的左孩子lchild域指示结点的前趋rchild域指示结点的右孩子rchild域指示结点的后继增加线索标志域后的结点结构为：这种结点类型和相应结点的指针类型定义如下：typedefenumPointerTag{Link,Thread};typedefstructBiThrNode{ElemTypedata;PointerTagLTag,RTag;/*ltag和rtag只能取值为0或1*/structBiThrNode*lchild,*rchild;}BiThrNode,*BiThrTree;

lchildLTagdataRTagrchild

中序线索树T11中序遍历线索树思想:

先由头结点指针找到根结点，从根结点起沿左指针逐结点一直向左查找，找到左线索标志为1的结点(“最左”的结点)即为遍历中需首先访问的结点。由此结点开始，反复进行寻找后继结点的过程，并陆续访问这些结点，直至结束。中序遍历线索二叉树非递归算法voidthinorder(BiThrTreeT){//二叉树附加了头结点,T指向头结点p=T->lchild;//p指向根结点whild(p!=T)/*空树或遍历结束时,p==T*/{while(p->LTag==Link)p=p->lchild;/*从根往下找到"最左"的结点，即中序序列的开始结点*/visit(p->data);//访问左子树为空结点

while(p->Rtag==Thread&&p->rchild!=T){p=p->rchild;visit(p->data);}/*访问后继结点*/p=p->rchild;}returnOK;}中序线索化思想：一边中序遍历一边建立线索。若访问结点的左儿子结点为空，则建立前趋线索；若右儿子结点为空，则建立后继线索。为此附设一个指针pre始终指向刚刚访问过的结点，而用指针p指示当前正在访问的结点。pre的初始值为NULL。中序线索化算法voidinthread(BiThrTree&p,*pre){if(p){inthread(p->lchild,pre);/*左子树线索化*/if(p->lchild==NULL)/*若当前结点的左子树为空，则建立指向其前趋结点的前趋线索*/{p->ltag=1;p->lchild=pre;}elsep->ltag=0;中序线索化算法续if(pre!=NULL&&pre->right==NULL)/*若前趋结点不为空，且其右指针域为空，则建立该前趋结点指向当前结点的后继线索*/{pre->RTag=1;pre->rchild=p;}elsepre->RTag=0;pre=p;/*中序向后遍历一个结点*/inthread(p->rchild,pre);}}6.4树和森林6.4.1树的存储结构6.4.2森林与二叉树的转换6.4.3树和森林的遍历6.4.1树的存储结构1．双亲表示法2.孩子表示法3．孩子兄弟表示法1．双亲表示法这种方法用一组连续的空间来存储树中的结点，在保存每个结点的同时附设一个指示器来指示其双亲结点在表中的位置.其结点的结构如下：

数据域双亲位置域dataparent双亲表示法的形式说明如下：#defineMAX100typedefstructPTNode//结点结构{

TElemTypedata;

intparent;}PTNode;typedefstruct//树结构{PTNodenodes[MAX];intr,n;//根的位置和结点数}PTree;双亲表示法举例2.孩子表示法这种方法通常是把每个结点的孩子结点排列起来，构成一个单链表，称为孩子链表。n个结点共有n个孩子链表（叶结点的孩子链表为空表），而n个结点的数据和n个孩子链表的头指针又组成一个顺序表.类型说明typedefstructCTNode

//孩子链表结点的定

{

intchild;

//该孩子结点在线性表中的位置

structCTNode*next;//指向下一个孩子结点

}*ChildPtr;

typedefstruct

//顺序表结点的结构定义{TElemTypedata;

//结点的信息

ChildPtrfirstChild;

//孩子链表的头指针}CTBox;typedefstruct

//树的定义{

CTBox

nodes[MAX];

//顺序表

intn,r;

//结点数和根的位置}CTree;孩子表示法举例67^4563.孩子兄弟表示法这种表示法又称为树的二叉表示法，或者二叉链表表示法，即以二叉链表作为树的存储结构。链表中每个结点设有两个链域，分别指向该结点的第一个孩子结点和下一个兄弟（右兄弟）结点。形式说明typedefstructCSNode{

ElemTypedata;

/*结点信息*/StructCSNode*firstChild,*Nextsibling;

/*第一个孩子,下一个兄弟*/}CSNode,*CSTree;孩子兄弟表示法举例6.4.2森林与二叉树的转换树的孩子兄弟链表结构与二叉树的二叉链表结构在物理结构上是完全相同的，只是它们的逻辑含义不同，所以树和森林与二叉树之间必然有着密切的关系。本节我们就介绍树和森林与二叉树之间的相互转换方法。方法如下：

(1)在所有兄弟结点之间加一连线；

(2)对树中的每个结点，只保留其与第一个孩子结点之间的连线，删去其与其它孩子结点之间的连线。

(3)以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。1．树转换为二叉树树转换成二叉树举例森林是若干棵树的集合。树可以转换为二叉树，森林同样也可以转换为二叉树。因此，森林也可以方便地用孩子兄弟链表表示。方法如下：（1）将森林中的每棵树转换成相应的二叉树。（2）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连在一起后，所得到的二叉树就是由森林转换得到的二叉树。2.森林转换为二叉树森林转换成二叉树举例6.4.3

树与森林的遍历1.树的遍历方法主要有以下两种：（1）

先根遍历若树非空，则遍历方法为：访问根结点。从左到右，依次先根遍历根结点的每一棵子树。

（2）后根遍历若树非空，则遍历方法为：从左到右，依次后根遍历根结点的每一棵子树。访问根结点。树的遍历举例如右图树先根遍历序列为ABECFHGD后根遍历序列为EBHFGCDA2.森林的遍历森林的遍历方法主要有以下两种：(1)先序遍历若森林非空，则遍历方法为：访问森林中第一棵树的根结点。先序遍历第一棵树的根结点的子树森林。先序遍历除去第一棵树之后剩余的树构成的森林。

(2)

后序遍历若森林非空，则遍历方法为：后序遍历森林中第一棵树的根结点的子树森林。访问第一棵树的根结点。后序遍历除去第一棵树之后剩余的树构成的森林。森林的遍历举例如右图森林先序遍历序列为ABCDEFGHIJ后序遍历序列为BCDAFEHJIG6.5赫夫曼树及其应用6.5.1赫夫曼树(最优二叉树)6.5.2赫夫曼编码6.5.1赫夫曼树(最优二叉树)1.基本术语：路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。路径长度：路径上的分支数称为这两点之间的路径长度。树的路径长度：树的路径长度是从树的根到每一结点的路径长度之和，一般记作pl。在结点数目相同的二叉树中，完全二叉树或满二叉树的路径长度最短。pl=0+1+1+2+2+2+2=10pl=0+1+1+2+2+2+3=11结点的权：在许多实际应用中，常常将树中结点赋予一个有某种意义的实数，称为该结点的权。结点的带权路径长度：从树的根结点到该结点之间的路径长度与该结点上权的乘积称为该结点的带权路径长度。树的带权路径长度定义为树中所有叶子结点的带权路径长度之和，通常记为：其中n表示叶子结点个数，wi和li分别表示叶子结点ki的权值和根到ki之间的路径长度。给定一组n个实数，以它们作为各个叶子结点的权，可构成不同的有n个叶子结点的二叉树，这