第6章树和二叉树

第6章树和二叉树16.1树6.1.1树的定义

树是由n（n≥0）个元素构成的有限集合。n=0称为空树；n>0称为非空树。任意一颗非空树，都满足：（1）有且仅有一个称为根的结点，没有前驱结点。（2）其余结点被分成m（m≥0）个互不相交的有限集T1，T2，…，Tm，其中每一个集合Ti（1≤i≤m）又是一颗树，称为根的子树。26.1.1树的定义结点的度：结点所拥有子树的个数称为结点的度。树的度：树中所有结点的度的最大值称为树的度。叶结点：度为零的结点称为叶结点。也称终端结点或叶子分支结点：度不为零的结点称为分支结点。也称非终端结点。除根结点以外，分支结点也称为内部结点。孩子结点和双亲结点：树中一个结点的子树的根结点称为孩子结点。该结点就称为孩子结点的双亲结点。兄弟结点：具有同一双亲的孩子结点互为兄弟结点。结点的祖先：从根到该结点所经分支上的所有结点，称为结点的祖先。36.1.1树的定义结点的子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。结点的层次：树是一种层次结构，树中的每个结点都处于某个层次上。树的深度：树中所有结点的层次的最大值称为树的深度。也称为树的高度。有序树：如果树中各结点的子树是按照从左到右有序排列的，即各子树的位置不能交换，这样的树称为有序树。无序树：如果树中各结点的子树的排列是无序的，称为无序树。森林：m（m≥0）颗互不相交的树的集合称为森林。46.1.2树的表示方法1.树形表示法以圆圈表示结点，以连线表示结点之间的关系。2.嵌套集合表示法也称为文氏图表示法。用圆圈表示树、子树和结点，并用包含关系表示结点间的关系。3.凹入表示法结点逐层缩进，即孩子结点缩进于双亲结点。4.广义表表示法用广义表表示树。用名称表示树的根，括号内表示子树。5线性结构和树结构的比较线性结构第一个数据元素：无前驱最后一个数据元素：无后继其他元素：一个前驱一个后继树结构根结点（只有一个）：无双亲叶子结点（可以有多个）：无孩子其他结点：一个双亲多个孩子66.1.3树的抽象数据类型ADTTree数据元素集合：具有相同性质的称为结点的数据元素的一个有限序列。其中一个称为根结点，其它形成m颗互不相交的子树。基本操作：构造树(CreateTree)：构造一颗树求树根(Root)：返回树的根取值(Value)：获取指定结点的值赋值(Assign)：将值赋给指定的结点双亲(Parent)：获取指定结点的双亲左孩子(LeftChild)：获取指定结点的左孩子右兄弟(RightSibling)：获取指定结点的右兄弟插入子树(InsertChild)：在指定的结点下插入第i颗子树删除子树(DeleteChild)：删除指定结点的第i颗子树树的深度(TreeDepth)：返回树的深度遍历树(TraverseTree)：访问树中的每一个元素，且仅访问一次76.1.4树的存储结构1.双亲表示法双亲表示法就是以一组地址连续的存储空间存储树的结点。其中，每个结点包含数据域和指针域。数据域存放数据元素的值，指针域存放一个指向其双亲的指针。86.1.4树的存储结构2.孩子表示法在结点中设置指向每个孩子的指针域，利用指针指向该结点的所有孩子结点。大多采用按树的度设置结点的指针域的个数。96.1.4树的存储结构3.孩子兄弟表示法在结点中设置两个指针域，一个指针域指向该结点的第一个孩子，另一个指针域指向其右兄弟。106.2二叉树6.2.1二叉树的定义

二叉树是n（n≥0）个结点构成的有限集合。当n=0时，它是一颗空二叉树；当n>0时，它由一个根结点和两颗互不相交的、分别称作左子树和右子树的二叉树构成。（1）二叉树的度只能是0、1或2；（2）二叉树是有序树，它的左、右子树是有次序的，即使只有一颗子树也要区分是左子树还是右子树。

11两种特殊形态的二叉树（1）满二叉树如果二叉树的所有分支结点都有左子树和右子树，并且所有叶子结点都在二叉树的最下一层，则称这样的二叉树为满二叉树。

（2）完全二叉树在一颗具有n个结点的二叉树中，如果它的结构与满二叉树的前n个结点的结构相同，则称这样的二叉树为完全二叉树。

126.2.1二叉树的定义【例6-3】所示的4颗二叉树中，哪颗是完全二叉树？133.二叉树的抽象数据类型ADTBiTree数据元素集合：具有相同性质的称为结点的数据元素的一个有限序列。其中一个称为根结点，其它形成两颗互不相交的、分别称作左子树和右子树的二叉树基本操作：构造二叉树(CreateBiTree)：构造一颗二叉树求树根(Root)：返回二叉树的根取值(Value)：获取指定结点的值赋值(Assign)：将值赋给指定的结点双亲(Parent)：获取指定结点的双亲左孩子(LeftChild)：获取指定结点的左孩子左兄弟(LeftSibling)：获取指定结点的左兄弟插入子树(InsertChild)：在指定的结点下插入第i颗子树删除子树(DeleteChild)：删除指定结点的第i颗子树遍历树(TraverseBiTree)：遍历的次序主要有先序遍历、中序遍历、后序遍历和层次遍历四种146.2.2二叉树的性质性质1非空二叉树的第i（i≥1）层上最多有2i-1个结点

证明：使用归纳法。当i=1（第1层）时，非空二叉树只有一个根结点，即21-1=1，命题成立。假定对于第i-1层命题成立，即非空二叉树第i-1层最多有2i-2个结点。由二叉树的定义可知，二叉树的每个结点最多有两个孩子结点，因此，第i层的结点总数最多是第i-1层结点数的2倍，即第i层最多有2×2i-2=2i-1个结点。命题得证。156.2.2二叉树的性质性质2深度为h（h≥1）的非空二叉树最多有2h-1个结点。证明：只有满二叉树才能出现最多结点个数，即二叉树的每层结点数都应该达到最大结点数2i-1（由性质1得到）。因此，深度为h的二叉树所具有的最多结点数为166.2.2二叉树的性质性质3在任意非空二叉树中，若度为0（叶子结点）的结点数为n0，度为2的结点数为n2，则关系n0=n2+1成立。证明：

设度为1的结点个数为n1，则二叉树的结点总数为 n=n0+n1+n2 (6-1)

除了根结点以外，每个结点都有一个直接前驱，即每个结点都有一个分支与之相连，因此，具有n个结点的二叉树的分支总数为

B=n-1 （6-2）这些分支来自于度为1和度为2的结点，因此，分支总数为

B=n1+2×n2 （6-3）把式（6-1）代入式（6-2），并使之等于式（6-3），得到

n0=n2+1176.2.2二叉树的性质性质4具有n（n>0）个结点的完全二叉树的深度h=证明：根据完全二叉树的定义可知深度为h-1层及以上的结点构成满二叉树，因此由性质2得深度为h的完全二叉树满足

n>2h-1-1和n≤2h-1整理后得到

2h-1≤n<2h不等式两边取对数，得

h-1≤log2n<h由于h为正整数，因此

h=186.2.2二叉树的性质性质5

对于具有n个结点的完全二叉树，如果按照从第1层、第2层、…、第层的次序，且每层从左到右的次序对结点进行编号，则编号为i的结点有以下性质：（1）若i>1，则编号为i的结点的双亲结点的编号为；当i=1时，编号为i的结点为二叉树的根结点，没有双亲结点。（2）若2i≤n，则编号为i的结点的左孩子结点的编号为2i；若2i>n，则编号为i的结点没有左孩子结点。（3）若2i+1≤n，则编号为i的结点的右孩子结点的编号为2i+1；若2i+1>n，则编号为i的结点没有右孩子结点。196.2.2二叉树的性质【例6-4】已知一颗完全二叉树的第6层有7个结点，则该完全二叉树总共有多少个结点？度为1的结点有多少个？度为0的结点有多少个？编号最大的非叶结点是哪一个？编号最小的叶结点是哪一个？解：深度为5的满二叉树：25-1=31，第6层7个结点，总结点数为38。第6层的7个结点会出现一个度为1的结点。第6层的7个结点是度为0的结点，除第5层上有4个结点之外的结点均是度为0的结点，总共有25-1-4=12个。度为0的结点有7+12=19个。编号最大的非叶结点就是第5层上的4个双亲结点中编号最大的结点，即编号为31-4=27的结点。编号最小的叶结点是编号最大的非叶结点的下一个结点，因此是编号为28的结点。206.2.3二叉树的存储结构1.二叉树的顺序存储结构

是用一组地址连续的存储单元依次存放二叉树的数据元素。根据二叉树的性质5，完全二叉树中结点编号之间的关系反映了结点之间的逻辑关系。非完全二叉树的顺序存储：为非完全二叉树增添一些实际上不存在的“空结点”，从而转换成完全二叉树。然后再顺序存储。216.2.3二叉树的存储结构2.二叉树的链式存储结构（1）二叉链表结点结构：数据域、左孩子指针域和右孩子指针域。226.2.3二叉树的存储结构二叉链表的存储结构：typedef

structNode{ DataTypedata; /*数据域*/ structNode*left;/*左孩子指针域*/ structNode*right;/*右孩子指针域*/}BTNode,*PBTNode,*BiTreeLink;（2）三叉链表结点结构：

parent域存放指向结点双亲的指针。236.2.3二叉树的存储结构3.二叉链式存储结构的操作

（1）创建二叉树

BiTreeLink

CreateBiTree(char*nodes,int

pos,intnum){

PBTNodep;

if(nodes[pos]==''||pos>num)returnNULL;/*递归结束条件*/ p=(PBTNode)malloc(sizeof(BTNode));/*建立根结点*/

if(!p){printf("初始化链表错误！\n");return0;} p->data=nodes[pos]; p->left=CreateBiTree(nodes,2*pos,num); /*递归建立左子树*/ p->right=CreateBiTree(nodes,2*pos+1,num);/*递归建立右子树*/ returnp;}246.2.3二叉树的存储结构（3）插入右孩子PBTNode

InsertRight(PBTNode

r,DataTypex){

PBTNodep;

if(!r)returnNULL; p=(PBTNode)malloc(sizeof(BTNode));/*生成新结点*/ p->data=x; p->left=NULL;/*若结点原来有右孩子，则把它作为新插入结点的右孩子*/

p->right=r->right; r->right=p;/*将x插入作为r的右孩子*/ returnp;}256.2.4二叉树的遍历（4）删除右子树

voidDeleteRight(PBTNoder){

if(!r)return;

ReleaseTree(&r->right); r->right=NULL;}（5）销毁子树

voidReleaseTree(PBTNode*r){ if(*r){

ReleaseTree(&(*r)->left); /*销毁左子树*/

ReleaseTree(&(*r)->right); /*销毁右子树*/ free(*r); }} /*销毁根*/ 266.2.4二叉树的遍历二叉树的遍历是指按一定次序访问二叉树中的每个结点，且每个结点仅被访问一次。1.前序遍历若二叉树非空，则按以下次序进行遍历：（1）访问根结点；（2）前序遍历根结点的左子树；（3）前序遍历根结点的右子树。voidPreOrder(BiTreeLinkr){

if(r!=NULL){

printf("%c",r->data); /*访问根*/

PreOrder(r->left); /*前序遍历左子树*/

PreOrder(r->right);}} /*前序遍历右子树*/ 276.2.4二叉树的遍历2.中序遍历若二叉树非空，则按以下次序进行遍历：（1）中序遍历根结点的左子树；（2）访问根结点；（3）中序遍历根结点的右子树。voidInOrder(BiTreeLinkr){

if(r!=NULL){

InOrder(r->left); /*中序遍历左子树*/

printf("%c",r->data); /*访问根*/

InOrder(r->right); /*中序遍历右子树*/ }}286.2.4二叉树的遍历3.后序遍历若二叉树非空，则按以下次序进行遍历：（1）后序遍历根结点的左子树；（2）后序遍历根结点的右子树；（3）访问根结点。voidPostOrder(BiTreeLinkr){

if(r!=NULL){

PostOrder(r->left); /*后序遍历左子树*/

PostOrder(r->right); /*后序遍历右子树*/

printf("%c",r->data); /*访问根*/ }}296.2.4二叉树的遍历【例6-7】已知一颗二叉树的中序遍历序列和后序遍历序列分别为DBAEGCHFI和DBGEHIFCA，试画出这颗二叉树。思路：由任意一个遍历序列均不能惟一确定一颗二叉树，只有知道中序和后序或中序和前序遍历序列才能惟一确定一颗二叉树。确定方法：由前序或后序遍历序列确定树或子树的根，再由中序遍历序列确定根的左子树和右子树306.2.4二叉树的遍历4.二叉树遍历的应用（1）统计二叉树中结点个数

二叉树结点的个数=左子树中所含结点的个数+右子树所含结点的个数+根结点。int

BiTreeCount(BiTreeLinkr){

if(r==NULL)return0;/*空二叉树的结点个数为0*/ else returnBiTreeCount(r->left)+BiTreeCount(r->right)+1;}316.2.4二叉树的遍历（2）求二叉树的深度

二叉树的深度=左子树的深度>右子树的深度?左子树的深度+1：右子树的深度右子树的深度+1。

int

BiTreeDepth(BiTreeLinkr){

int

ld,rd;

if(r==NULL) return0; else{ ld=BiTreeDepth(r->left); rd=BiTreeDepth(r->right); returnld>rd?ld+1:rd+1; }}326.2.4二叉树的遍历【例6-9】仿照算法6-12，编写一个算法统计二叉树中叶子结点的数目。

思路：叶子结点数=左子树叶子结点数+右子树叶子结点数。int

LeafCount(BiTreeLinkr){

if(!r)return0;/*空树叶子个数为0*/ elseif(!r->left&&!r->right)/*只有根结点，叶子数为1*/ return1; else returnLeafCount(r->left)+LeafCount(r->right);}

336.4森林6.4.1树、森林与二叉树的转换

树、森林与二叉树之间有着一一对应关系。1.树与二叉树之间的相互转换

任何一颗树都可以用孩子兄弟链表表示出来，而任何一颗二叉树都可以用二叉链表表示出来。

346.4.1树、森林与二叉树的转换（1）树转换为二叉树方法将树中具有同一双亲的兄弟结点之间用线段连接起来；保留双亲与第一个孩子之间的连线，删除其他孩子与双亲之间的连线；将兄弟之间的连线顺时针旋转45°。【例6-11】将树转换为二叉树。356.4.1树、森林与二叉树的转换（2）二叉树转换为树方法若二叉树某结点是其双亲的左孩子，则把以该结点为根的右子树中的所有右孩子与该结点的双亲之间用线段连接起来；删除这些右孩子与其他结点之间的连线；整理连线，使各结点按层次排列。【例6-12】将二叉树转换为树。366.4.1树、森林与二叉树的转换2.森林与二叉树之间的相互转换

（1）森林转换成二叉树方法将森林中的所有树均转换为二叉树；将森林中第一颗树转换成的二叉树作为转换后的二叉树的根和左子树；将森林中第二颗树转换成的二叉树作为转换后的二叉树的右子树添加到转换后的二叉树上；将森林中第三颗树转换成的二叉树作为转换后的二叉树的右子树的右子树添加到转换后的二叉树上；依此类推，直至把所有二叉树均添加到转换后的二叉树上为止。376.4.1树、森林与二叉树的转换【例6-13】将森林转换为二叉树。386.4.1树、森林与二叉树的转换（2）二叉树转换成森林方法将二叉树的根及左子树转换成树，作为森林第一颗树；将剩下的二叉树的根及左子树转换成树，作为森林的第二颗树；以此类推，直至把二叉树转换完为止。【例6-14】将二叉树转换为森林。

396.4.2树和森林的遍历1.树的遍历按一定次序访问树中的每个结点，且每个结点仅被访问一次。（1）先根遍历若树不空，则访问根结点；按照从左到右的次序先根遍历根结点的每一颗子树。（2）后根遍历若树不空，则按照从左到右的次序后根遍历根结点的每一颗子树。访问根结点；406.4.2树和森林的遍历2.森林的遍历（1）先序遍历森林若森林不空，则访问森林中第一颗树的根结点；先序遍历第一颗树中根结点的子树森林；先序遍历除去第一颗树之后剩余的树构成的森林。（2）中序遍历森林若森林不空，则中序遍历森林中第一颗树中根结点的子树森林；访问第一颗树的根结点；中序遍历除去第一颗树之后剩余的树构成的森林。416.4.2树和森林的遍历3.二叉树、树和森林遍历的对应关系树森林二叉树先根遍历先序遍历先序遍历后根遍历中序遍历中序遍历426.5哈夫曼树及其应用在一颗二叉树中，从一个结点到另一个结点之间的分支序列构成这两个结点之间的路径。二叉树中两个结点之间的路径上的分支数目称作结点间的路径长度。从二叉树的根结点到每一个结点的路径长度之和称作树的路径长度。若给二叉树的叶结点赋以权值，则定义从二叉树的根结点到二叉树中所有叶结点的路径长度与相应叶结点权值的乘积之和为二叉树的带权路径长度，记作

其中，wi为第i个叶结点的权值，li为第i个叶结点的路径长度，n为叶结点数。436.5.1哈夫曼树给定一组带有权值的叶结点，可以构造出许多带权路径长度不同的二叉树，其中带权路径长度最小的二叉树称作哈夫曼树或最优二叉树。WPL=6×3+5×3+1×2+2×2=39WPL=6×1+5×2+1×3+2×3=25446.5.1哈夫曼树2.哈夫曼树构造算法（1）用给定的n个权值{w1,w2,…,wn}构造n颗只有根结点的二叉树，形成一个二叉树森林F={T1,T2,…,Tn}；（2）在二叉树森林F中，选出根的权值最小的两