数据结构简明教程（第3版）课件 第6章树和二叉树(下)

第6章树和二叉树6.1树6.2二叉树6.3递归算法设计方法6.4二叉树的基本运算算法6.5二叉树的遍历6.6二叉树的构造6.7二叉树与树之间的转换6.8线索二叉树6.9哈夫曼树第6章树和二叉树1/506.6二叉树的构造6.6.1什么是二叉树的构造一棵所有结点值不同的二叉树，其先序、中序、后序和层次遍历都是唯一的。二叉树的构造就是给定某些遍历序列，反过来唯一地确定该二叉树。6.6二叉树的构造2/50

【例6.15】一棵二叉树的先序遍历序列和中序遍历序列相同，说明该二叉树的形态。

二叉树的先序遍历序列为NLR，中序遍历序列为LNR:NLR=LNR则L应为空（因为N为空后其L、R没有意义）。所以这样的二叉树为右单支树（除叶子结点外每个结点只有一个右孩子）。高度为4的满足题目要求的二叉树6.6二叉树的构造3/506.6.2二叉树的构造方法二叉树遍历序列图(a)的二叉树图(b)的二叉树图(c)的二叉树图(d)的二叉树图(e)的二叉树先序遍历序列ABCABCABCABCABC中序遍历序列BACBCAACBCBAABC后序遍历序列BCACBACBACBACBAABCABCABCABCABC(a)(b)(c)(d)(e)6.6二叉树的构造4/50从中看到，对于不同形态的二叉树：先序遍历序列可能相同（图中5棵二叉树的先序遍历序列均相同）。中序遍历序列可能相同。后序遍历序列可能相同（图(b)～(e)的后序遍历序列均相同）先序遍历序列和后序遍历序列可能都相同（图(d)和(e)的先序遍历序列和后序遍历序列均相同）。ABCABCABCABCABC(a)(b)(c)(d)(e)6.6二叉树的构造5/50实际上，对于含2个或者以上结点的二叉树，在先序、中序和后序遍历序列中：由先序遍历序列和中序遍历序列能够唯一确定一棵二叉树。由后序遍历序列和中序遍历序列能够唯一确定一棵二叉树。由先序遍历序列和后序遍历序列不能唯一确定一棵二叉树。6.6二叉树的构造6/50任何n（n≥0）个不同结点的二又树，都可由它的中序序列b和先序序列a唯一地确定。1.由先序遍历序列和中序遍历序列构造一棵二叉树6.6二叉树的构造7/50左子树先序序列，有k个结点右子树先序序列，有n-k-1个结点先序序列：a0

a1

…

ak

ak+1

…

an-1左子树中序序列，有k个结点右子树中序序列，有n-k-1个结点中序序列：b0

b1

…

bk

bk+1

…

bn-1通过根结点a0在中序序列中找到bk由a0（根结点）找到bk。若bk前面有k个结点，则左子树有k个结点，右子树有n-k-1个结点。可以求出左右子树的中序序列和先序序列。这样根结点是确定的，左右子树也是确定的，则该二叉树是确定的。6.6二叉树的构造8/50

【例6.16】已知先序序列为ABDECFG，中序序列为DBEACGF，给出构造该二叉树的过程。根：D左先序：空

右先序：空右中序：空

右中序：空根：E左先序：空

右先序：空右中序：空

右中序：空根：F左先序：G右先序：空右中序：G右中序：空根：G左先序：空

右先序：空右中序：空

右中序：空根：B左先序：D右先序：E右中序：D右中序：E根：C左先序：空

右先序：FG右中序：空

右中序：GF6.6二叉树的构造构造该二叉树的过程如下所示。根：A左先序：BDE右先序：CFG右中序：DBE右中序：CGF9/50

任何n（n≥0）个不同结点的二又树，都可由它的中序序列和后序序列唯一地确定。2.由中序遍历序列和后序遍历序列构造一棵二叉树6.6二叉树的构造10/50左子树后序序列，有k个结点右子树后序序列，有n-k-1个结点后序序列：a0

a1…ak-1

ak…an-2

an-1左子树中序序列，有k个结点右子树中序序列，有n-k-1个结点中序序列：b0

b1

…

bk

bk+1

…

bn-1通过根结点an-1在中序序列中找到bk由an-1（根结点）找到bk。若bk前面有k个结点，则左子树有k个结点，右子树有n-k-1个结点。可以求出左右子树的中序序列和后序序列。这样根结点是确定的，左右子树也是确定的，则该二叉树是确定的。6.6二叉树的构造11/50

【例6.17】已知一棵二叉树的后序遍历序列为DEBGFCA，中序遍历序列为DBEACGF，给出构造该二叉树的过程。根：D左后序：空

右后序：空右中序：空

右中序：空根：E左后序：空

右后序：空右中序：空

右中序：空根：F左后序：G右后序：空右中序：G右中序：空根：G左后序：空

右后序：空右中序：空

右中序：空根：B左后序：D右后序：E右中序：D右中序：E根：C左后序：空

右后序：GF右中序：空

右中序：GF6.6二叉树的构造构造该二叉树的过程如下所示。根：A左后序：DEB右后序：GFC右中序：DBE右中序：CGF12/506.7二叉树与树之间的转换6.7.1森林/树转换成二叉树树中所有相邻兄弟之间加一条连线；对树中的每个结点，只保留它与第一个孩子结点之间的连线，删除它与其他孩子结点之间的连线；以树的根结点为轴心，将整棵树顺时针转动45度，使之结构层次分明。6.7二叉树与树之间的转换将一棵树转换成二叉树的过程如下：13/50【例6.18】将图6.27(a)所示的树转换成二叉树。ABEFCDG一棵树相邻兄弟之间加连线(虚线)删除与双亲结点的连线转换后的二叉树ABEFCDGABEFCDGABEFCDG6.7二叉树与树之间的转换14/50当要转换为二叉树的森林由两棵或以上树构成时，将这样的森林转换为二叉树的过程如下：将森林中的每棵树转换成相应的二叉树。第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子结点，当所有二叉树连在一起后，此时所得到的二叉树就是由森林转换得到的二叉树。6.7二叉树与树之间的转换15/50【例6.19】将下图所示的森林转换成二叉树。ABCDEFGHIJKABCDEFGHIJKABCDEFGHIJK6.7二叉树与树之间的转换16/506.7.2二叉树还原为树/森林当一棵二叉树是由一棵树转换而来的，则该二叉树还原为树的过程如下：若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子、…、都与该结点的双亲结点用连线连起来。删除原二叉树中所有双亲结点与右孩子结点之间的连线。整理由①、②两步所得到的树，使之结构层次分明。6.7二叉树与树之间的转换17/50【例6.21】将下图的一棵二叉树还原为森林。ABECFDG一棵二叉树ABECFDG加连线ABECFDG删除与右孩子的连线ABECFDG6.7二叉树与树之间的转换18/50当一棵二叉树是由m棵树构成的森林转换而来的，该二叉树的根结点一定有m-1个右下孩子，则该二叉树还原为森林的过程如下：抹掉二叉树根结点右链上所有结点之间的“双亲－右孩子”关系，将其分成若干个以右链上的结点为根结点的二叉树，设这些二叉树为bt1、bt2、…、btm。分别将bt1、bt2、…、btm二叉树各自还原成一棵树。6.7二叉树与树之间的转换19/50【例6.22】将如下图的二叉树还原为森林。ABCDEGFHI一棵二叉树ABCDEFGHI6.7二叉树与树之间的转换20/50ABCDEFGHIABCDEFGHI6.7二叉树与树之间的转换21/50ABCDEFGHI6.7二叉树与树之间的转换ABCDEGFHI一棵二叉树森林还原22/506.8线索二叉树6.8.1什么是线索对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域。利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。线索二叉树分为先序、中序和后序线索二叉树。6.8线索二叉树23/50图中虚线为线索。ABDCEF二叉树ABDCEF先序序列：ABDCEF先序线索二叉树6.8线索二叉树24/506.8.2线索二叉树的存储结构在原二叉链中增加了ltag和rtag两个标志域。ltag=0表示lchild指向结点的左孩子1表示lchild指向结点的前驱结点即为线索rtag=0表示rchild指向结点的左孩子1表示rchild指向结点的后继结点即为线索6.8线索二叉树25/50线索二叉树的类型定义如下：typedefstructbthnode{ElemTypedata;structbthnode*lchild,*rchild;intltag,rtag;}BthNode;6.8线索二叉树26/50下面以中序线索二叉树为例，讨论线索二叉树的建立和相关算法。为了方便算法实现，为线索二叉树增加一个头结点。01头结点head0A1根结点1B00C11D10E10F1中序序列：DBAECF6.8线索二叉树27/506.8.3建立线索二叉树及其销毁建立线索化二叉树称之为二叉树线索化。以中序线索化一棵二叉树为例，实质上就是中序遍历一棵二叉树，在遍历过程中，检查当前结点的左、右指针域是否为空；如果为空，将它们改为指向前驱结点或后继结点的线索。6.8线索二叉树28/50先创建一个头结点head，在进行中序遍历过程中需保留当前结点p的前驱结点的指针，设为pre（全局变量，初值时指向头结点）。在p不空的情况下：遍历左子树（即左子树线索化）。对空指针线索化。若p->lchild为空，则置p->ltag=1，且p->lchild=pre；6.8线索二叉树算法思想prep∧29/50先创建一个头结点head，在进行中序遍历过程中需保留当前结点p的前驱结点的指针，设为pre（全局变量，初值时指向头结点）。在p不空的情况下：遍历左子树（即左子树线索化）。对空指针线索化。若p->lchild为空，则置p->ltag=1，且p->lchild=pre；若p->rchild为空，则置pre->rtag=l，且pre->rchild=ppre=p；遍历右子树（即右子树线索化）。6.8线索二叉树算法思想∧prep30/50中序线索二叉树过程：01头结点head0A1根结点1B00C11D10E10F1中序序列：BDAECF6.8线索二叉树31/50BthNode*CreaThread(BthNode*bt)//对以bt为根结点的二叉树中序线索化,并增加一个头结点head{BthNode*head;

head=(BthNode*)malloc(sizeof(BthNode));

head->ltag=0;head->rtag=1;//创建头结点head

head->rchild=bt;

if(bt==NULL)

//bt为空树时

head->lchild=head;

else

{ head->lchild=bt; pre=head; //pre是p的前驱结点,供加线索用

Thread(bt); //中序遍历线索化二叉树

pre->rchild=head; //最后处理,加入指向根结点的线索

pre->rtag=1; head->rchild=pre; //根结点右线索化

}

returnhead;}6.8线索二叉树32/50BthNode*pre; //定义pre为全局变量voidThread(BthNode*&p)//对以p为根结点的二叉树进行中序线索化{if(p!=NULL)

{

Thread(p->lchild); //左子树线索化if(p->lchild==NULL) //前驱线索

{p->lchild=pre; //给结点p添加前驱线索

p->ltag=1;

}

elsep->ltag=0;

if(pre->rchild==NULL)

{pre->rchild=p; //给结点pre添加后继线索

pre->rtag=1;

}

elsepre->rtag=0;

pre=p;

Thread(p->rchild); //右子树线索化

}}6.8线索二叉树33/50当建立好一棵中序线索二叉树tb后，销毁tb的过程是先销毁原来的二叉链，最后释放头结点。voidDestroyBTree1(BthNode*&b){if(b->ltag==0) //b有左孩子,释放左子树

DestroyBTree1(b->lchild);

if(b->rtag==0) //b有右孩子,释放右子树

DestroyBTree1(b->rchild);

free(b);}voidDestroyBTree(BthNode*&tb){DestroyBTree1(tb->lchild); //释放以tb->lchild为根结点的树

free(tb); //释放头结点}6.8线索二叉树34/506.8.4线索二叉树的基本运算算法（1）查找中序序列的第一个结点从中序线索二叉树的根结点出发沿左指针向下到达最左下结点，它是中序序列的第一个结点。而中序线索二叉树的根结点由头结点的lchild所指向。BthNode*FirstNode(BthNode*tb)//在中序线索树中查找中序序列的第1个结点{BthNode*p=tb->lchild; //p指向根结点

while(p->ltag==0) //找根结点的最左下结点p=p->lchild;

return(p);}6.8线索二叉树35/50（2）查找中序序列的最后一个结点在中序线索二叉树中，由头结点的rchild域指向中序序列的最后一个结点。BthNode*LastNode(BthNode*tb) //在中序线索树中查找中序序列的最后1个结点{

return(tb->rchild);}6.8线索二叉树36/50（3）查找p结点的前驱结点若p->ltag=1（线索），则p->lchild指向前驱结点；否则，查找p结点的左孩子的最右下结点，该结点作为p结点的前驱结点。BthNode*PreNode(BthNode*p)//在中序线索二叉树上,查找p结点的前驱结点{BthNode*pre;

pre=p->lchild;

if(p->ltag!=1){while(pre->rtag==0)

pre=pre->rchild;}

return(pre);}6.8线索二叉树37/50（4）查找p结点的后继结点若p->rtag=1，则p->rchild指向后继结点；否则，查找p结点的右孩子的最左下结点，该结点作为p结点的后继结点。BthNode*PostNode(BthNode*p)//在中序线索二叉树上,查找p结点的后继结点{BthNode*post;

post=p->rchild;

if(p->rtag!=1){ while(post->ltag==0)

post=post->lchild;

}return(post);}6.8线索二叉树38/50（5）输出中序遍历序列先访问第一个结点，继续访问其后继结点，直到遍历完所有结点为止。voidThInOrder(BthNode*tb)//中序遍历线索二叉树,输出中序遍历序列{BthNode*p;

p=FirstNode(tb);

while(p!=tb)

{ printf("%c",p->data); p=PostNode(p);

}

printf("\n");}6.8线索二叉树39/506.9哈夫曼树6.9.1哈夫曼树的定义设二叉树具有n个带权值的叶子结点，从根结点到每个叶子结点都有一个路径长度。从根结点到各个叶子结点的路径长度与相应结点权值的乘积的和称为该二叉树的带权路径长度，记作：其中，wi为第i个叶子结点的权值，li为第i个叶子结点的路径长度。6.9哈夫曼树40/50以下二叉树的带权路径长度值：WPL=1×3+3×3+2×2+4×1=20。42136.9哈夫曼树41/50给定一组具有确定权值的叶子结点，可以构造出许多形状的二叉树。它们的带权路径长度可能不相同。把其中具有最小带权路径长度的二叉树称为哈夫曼树。6.9哈夫曼树42/50

【例6.19】如下图的4棵二叉树具有相同的叶子结点，计算出它们的带权路径长度。

1357(a)1735(b)1375(c)7513(d)6.9哈夫曼树

它们的带权路径长度分别为：（a）WPL=1×2+3×2+5×2+7×2=32（b）WPL=1×2+3×3+5×3+7×1=33（c）WPL=7×3+5×3+3×2+1×1=43（d）WPL=1×3+3×3+5×2+7×1=29其中图(d)所示的二叉树就是一棵哈夫曼树。43/506.9.2构造哈夫曼树根据哈夫曼树的定义，一棵二叉树要使其WPL值最小，必须使权值越大的叶子结点越靠近根结点。而权值越小的叶子结点越远离根结点。6.9哈夫曼树44/50构造一棵哈夫曼树的过程