数据结构-刘波-6

《数据结构-刘波-6》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

数据结构第六章树主讲人:刘波

1本章要点树的相关概念,树的表示,树的性质二叉树的相关概念,二叉树的性质和存储结构二叉树运算的实现过程树和森林相互转换过程哈夫曼树的构造过程和哈夫曼编码

2树型结构的引入线性结构不能反映所有应用中的数据关系树型结构是一类应用广泛的非线性结构，反映元素之间的层次关系和分支关系应用示例人类社会的族谱和各种社会组织机构操作系统中的文件目录管理数据库系统中的信息组织形式计算机网络中层次路由

3树的示例

4树的定义和基本术语树:是n(n>0)个结点的有限集合,满足如下两个条件:有且仅有一个称作根的结点;其余结点可分为m(m>=0)棵互不相交的有限集合T1,T2…Tm,其中每个集合又是一棵树,并称为根的子树.树的结点(node):包含一个数据元素及若干指向其子树的分支.结点的度(degree):结点具有子树的个数.树的度:树中所有结点的度的最大值.

5树的基本术语(2)分支结点(非终端结点):度大于0的结点.叶子(终端结点):度为0的结点.结点的孩子:结点子树的根,该结点为孩子的双亲.兄弟:同一双亲的孩子.堂兄弟：其双亲在同一层的结点间互称堂兄弟。结点的祖先:从根到该结点所经分支上的所有结点结点的子孙:一个结点的所有子树中的结点.

6树的基本术语(3)结点的层次:根为第一层,其孩子结点为第二层,如此类推到每个结点层次.树的深度:树中结点的最大层次数.有序树(无序树)：若将树中结点的各子树看成从左至右是有序的(不能互换)，则称该树为有序树，否则为无序树。森林:0个或多个互不相交的树的集合.

7树的抽象数据类型定义ADTTree{数据对象D：具有相同特性的数据元素集合。数据关系R：若D为空集，则称为空树。否则R={H},H是如下关系：（1）在D中存在唯一的称为根的数据元素root；（2）若D除了根结点外，D中还有其它结点，则其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。

8树基本操作InitTree(&T)//初始化置空树CreateTree(&T,definition)//按定义构造树Assign(T,&e,value)//给e赋值为valueParent(T,e)//求T中结点e的双亲结点TreeDepth(T)//求树的深度TraverseTree(T,Visit())//遍历ClearTree(&T)//将树清空DestroyTree(&T)//销毁树的结构DeleteChild(&T,&p,i)//删除结点p的第i棵子树……}

9二叉树定义:每个结点至多有两棵子树,子树有左右之分性质1:在二叉树的第i层上至多有2i-1个结点性质2:深度为k的二叉树至多有2k-1个结点性质3:非空二叉树上叶子结点数等于双分支结点数加1.即n0=n2+1.

10二叉树的定义二叉树的特点：（1）二叉树中不存在度大于2的结点；（2）二叉树每个结点至多有两棵子树，且有左右之分，次序不能颠倒。

11二叉树的五种基本形态

12特殊的二叉树满二叉树一棵深度为k且有2k-1个结点的二叉树称为满二叉树，即所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，其特点是每一层上的结点数都是最大结点数。

13特殊的二叉树(2)完全二叉树深度为k，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应，称为完全二叉树，其特点是:（1）叶子结点只可能在层次最大的两层上出现，即最下层和次最下层；（2）对任一结点，若其右分支下的子孙的最大层次为L，则其左分支下的子孙的最大层次必为L或L+1，即最下层的叶子结点集中在树的左部。

14

15完全二叉树性质性质1:具有n个结点的完全二叉树的深度为性质2:对有n个结点的完全二叉树的结点按层序编号(从上至下,从左至右),则对任一结点i(1≤i≤n),有:如果i=1,则结点为根;如果i>1,则其双亲parent是结点如果2i>n,则结点i无左儿子;否则其左孩子Lchild(i)是结点2i如果2i+1>n,则结点i无右儿子;否则其右孩子Rchild(i)是结点2i+1

16二叉树的存储结构顺序存储结构根结点编号定为1,当一结点编号为i时,其左儿子编号为2i,右儿子编号为2i+1顺序存储结构仅适合用于完全二叉树.

17二叉树的存储结构(2)链式存储结构含有两个指针域的结点结构含有三个指针域的结点结构链式存储方式存在大量的空指针,浪费存储空间,但二叉树的运算算法实现比较简单直观.

18（1）二叉链表存储链表中的每个结点由三个域组成：数据域、左、右指针域，其形式定义如下:typedefstructBiTNode{//结点结构TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;

19（2）三叉链表存储每个结点由四个域组成：数据域、左、右指针域和双亲域，数据域(data)，其形式定义如下:typedefstructTriTNode{//结点结构TElemTypedata;structTriTNode*lchild,*rchild;structTriTNode*parent;//双亲指针}TriTNode,*TriTree;

20

21二叉树的基本运算----遍历应用背景在树中查找具有某种特征的结点对树中全部结点逐一进行某种处理遍历要解决的问题如何按某条搜索路径巡访树中每个结点,使得每个结点均被访问一次,而且仅被访问一次.常用的按规律遍历二叉树的方式先序遍历中序遍历后序遍历

22先序遍历按照:先访问根结点;再访问左子树;最后访问右子树的次序;访问二叉树中所有结点,且每个结点只访问一次.例:ABDEFCGHBHACDEFG

23试问下面一棵二叉树,其先序遍历序列是什么?DABCGEFHI

24先序遍历递归算法voidpreorderTraverse(BiTreeT){if(T){printf(T->data);preorderTraverse(T->lchild);preorderTraverse(T->rchild);}}

25先序遍历非递归算法VoidpreorderTraverse(BiTreeT){Inistack(S);P=T;while(P||!StackEmpty(S)){if(P){printf(P->data);push(S,P);P=P->lchild;}else{pop(S,P);P=P->rchild;}}}BHACDEFG

26中序遍历按照:先访问左子树;再访问根结点;最后访问右子树的次序;访问二叉树中所有结点,且每个结点仅访问一次.例:EDFBAGHCBHACDEFG

27试问下面一棵二叉树,其中序遍历序列是什么?DABCGEFHI

28中序遍历递归算法voidInorderTraverse(BiTreeT){if(T){InorderTraverse(T->lchild);printf(T->data);InorderTraverse(T->rchild);}}

29中序遍历的非递归算法VoidInorderTraverse(BiTreeT){IniStack(S);P=T;while(P||!StackEmpty(S)){if(P){push(S,P);P=P->lchild;}else{pop(S,P);printf(P->data);P=P->rchild;}}}BHACDEFG

30后序遍历按照:先访问左子树;再访问右子树;最后访问根结点的次序;访问二叉树中所有结点,且每个结点仅访问一次.例:EFDBHGCABHACDEFG

31试问下面一棵二叉树,其后序遍历序列是什么DABCGEFHI

32后序遍历递归算法voidPostorderTraverse(BiTreeT){if(T){PostorderTraverse(T->lchild);PostorderTraverse(T->rchild);printf(T->data);}}

33后序遍历非递归算法VoidPostorderTraverse(BiTreeT){Inistack(T);P=T;while(P||!StackEmpty(S)){if(P){push(S,P);P=P->lchild;}else{pop(S,P);if(P->rchild&&(P->rchild).tag==0){push(S,P);P=P->rchild;}else{printf(P->data);P.tag=1;P=NULL}}}}说明:在二叉树的存储结构中给每个结点增加一个是否访问的tag域,初始值均为0;BHACDEFG

34思考?按层次从上到下,从左到右的遍历算法

35遍历是二叉树各种操作的基础.如:求已知树结点的双亲,求已知树结点的孩子,求已知树层次;创建二叉树

36StatusCreateBiTree(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;}

37注意：由中序和先序(或后序)遍历序列可以唯一确定一棵二叉树，但由先序和后序遍历不能唯一确定一棵二叉树。因为对二叉树的先序和后序遍历序列来说，我们无法根据根结点唯一地划分出左子树和右子树的遍历序列，因此也就不能唯一确定这棵二叉树，除非二叉树为空二叉树或只有一个结点。

38例如：已知一棵二叉树的中序和后序序列为BDCEAFHG和DECBHGFA，构造这棵二叉树的过程如图

39线索二叉树结点结构lchildLtagdataRtagrchild其中:lchild域指示结点左孩子lchild域指示结点的前驱rchild域指示结点右孩子rchild域指示结点的后续

40二叉线索存储表示TypedefenumPointerTag{Link,Thread};//Link=0,Thread=1TypedefstructBiThrNode{TElemTypedata;structBiThrNode*lchild,*rchild;//左右孩子指针PointerTagLTag,RTag;//左右标志}BiThrNode,*BiThrTree;

41三种线索树先序线索树中序线索树后序线索树线索化:将二叉链表中的空指针改为指向前驱或后继的线索.例：

42添加一个头结点

43建立一棵中序线索化二叉树的算法StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){//中序遍历二叉树T,并将其中序线索化,Thrt指向头结点。If(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))))exit(OVERFLOW);Thrt->ltag=Link;Thrt->rtag=Thread;//建头结点Thrt->rchild=Thrt;//右指针回指if(!T)Thrt->lchild=Thrt;//若二叉树空，则左指针回指else{Thrt->lchild=T;pre=Thrt;InThreading(T);//中序遍历进行中序线索化pre->rtag=Thread;pre->rchild=Thrt;//最后一个结点线索化Thrt->rchild=pre;}returnOK;}

44中序遍历进行中序线索化voidInThreading(BiThrTreep)//中序遍历进行中序线索化。{if(p){InThreading(p->lchild);//递归左子树线索化if(!p->lchild)//没有左孩子{p->ltag=Thread;//前驱线索p->lchild=pre;//左孩子指针指向前驱}if(!pre->rchild)//前驱没有右孩子{pre->rtag=Thread;//后继线索pre->rchild=p;//前驱右孩子指针指向后继(当前结点p)}pre=p;//保持pre指向p的前驱InThreading(p->rchild);//递归右子树线索化}}

45中序线索二叉树中找结点后继结点的算法StatusNext_Thr(BiThrTreeThrt,BiThrTrees){//求某一结点的后继，其中Thrt指向线索二叉树的头结点。BiThrTreep;p=s->rchild;if(s->rtag!=thread)while(p->ltag==Link)p=p->lchild;return(p)}

46中序线索二叉树中找结点前驱结点StatusPre_Thr(BiThrTreeThrt,BiThrTrees){//求某一结点s的前驱，其中Thrt指向线索二叉树的头结点。BiThrTreepre;pre=s->lchild;if(s->ltag!=thread)while(pre->rtag==Link)pre=pre->rchild;return(pre)}

47树的链表结构双亲表示用一个数组连续存储结点,各结点中附设一个指示其双亲的结点位置(下标).

48孩子表示法把每个结点的孩子排列成单链表

49孩子兄弟表示法(二叉树表示法)以二叉链表作为存储结构TypedefstructCSNode{ElemTypedata;structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;

50

51树,森林与二叉树的转换树与二叉树的转换按孩子兄弟表示法转换森林与二叉树的转换森林转换成二叉树以第一棵树的根为二叉树的根,先将第一棵树转为二叉树,再依次转换其它子树,最后按孩子兄弟表示法将它们连接.二叉树转换成森林二叉树的根为第一棵树的根,先把左子树转为第一棵树,再将右子树转换成一棵或若干棵树.

52

53森林转换成二叉树的过程

54二叉树转换成森林

55树和森林的遍历树的遍历先根(次序)遍历后根(次序)遍历森林的遍历先序遍历中序遍历

56树的先根遍历:先访问树的根结点，然后依次先根遍历根的每棵子树，遍历方法与对应的先序遍历二叉树相同。例：先根序列为：ABCDE

57树的后根遍历：先依次遍历每棵子树，然后访问根结点，与后序遍历二叉树相同。例：后根序列为：BDCEA

58森林的先序遍历：先访问森林中第一棵树的根结点，然后先序遍历第一棵树中根结点的子树森林，最后先序遍历除去第一棵树之后剩余的树构成的森林。（即:每棵树按先根遍历，将森林对应的二叉树进行先序遍历）例：森林的先序序列为：ABCDEFGHIJ

59森林的中序遍历：先中序遍历森林中第一棵树的根结点的子树森林，然后访问第一棵树的根结点，最后中序遍历除去第一棵树之后剩余的树构成的森林。每棵树按后根遍历（即:每棵树按后根遍历,将森林对应的二叉树进行中序遍历）例：森林的中序序列为：BCDAFEHJIG

60赫夫曼树及其应用基本概念路径:从树中一个结点到另一个结点之间的分支构成两结点之间路径。路径长度:路径上的分支数目。树的路径长度:从树根到树中每一个结点的路径长度之和。结点的权：树中的结点上赋予的一定的实数带权路径长度：从结点到根之间的路径长度与结点上权值的乘积。树的带权路径长度:树中所有叶子结点的带权路径长度之和.

61赫夫曼树有何用途?(a)WPL=36的二叉树(b)WPL=46的二叉树(c)WPL=35的二叉树赫夫曼树(最优二叉树):是n个带权叶子结点构成的所有二叉树中,带权路径长度WPL最小的二叉树.

62构造赫夫曼树直观上观察:离根近的叶结点权值大,离根远的叶结点权值小.Huffman算法:1)根据给定的n个权值{W1,W2,…,Wn}构成n棵二叉树的集合F={T1,T2，…，Tn}，其中每棵二叉树Ti中只有一个带权为Wi的根结点，左右子树均空。2)在F中选取两棵根结点的数值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。3)在F中删除这两棵树，同时将新得到的二叉树加入F中。4)重复2)、3)步，直到F只含一棵树为止。Huffman树是一棵严格的(正则的)二叉树,没有度为1的结点.

63例如:下图展示了按权值W={5,6,2,9,7}构造哈夫曼树的过程。注意:Huffman树并不一定唯一,但它们的WPL一定相等.

64赫夫曼编码引例:电文“abcadeabbbbbec…”，如何编码？编码目标可区分各字符使总长度最短前缀编码任一编码不能为另一个字符编码的前缀赫夫曼编码以电文中n个字符出现的频率作权,设计一棵赫夫曼树,得到的二进制前缀码.

65例:电文“abcadeabbbbbec……”f(a)=6,f(b)=7,f(c)=10,f(d)=5,f(e)=2构造赫夫曼树

66赫夫曼树和赫夫曼编码的存储表示typedefstruct{unsignedintweight;//权unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树typedefstructchar**HuffmanCode;//动态分配指针数组存储哈夫曼编码

67例:P148例6-2已知某系统在通信联络中只可能出现8种字符,其概率分别为:0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11试设计赫夫曼编码.解:w={5,29,7,8,14,23,3,11}53887151119142923422958100

68赫夫曼编码算法VoidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){If(n<=1)return//n为字符种类数，即叶结点数m=2*n-1;//Huffman树的总结点数HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));for(p=HT,i=1;i<=n;++i,++p,++w)*p={*w,0,0,0};//HT的初始化//前n个元素存叶子结点for(;i<=m;++i,++p)*p={0,0,0,0};//后n-1个元素存非叶子结点for(i=n+1;i<=m;++i){//建赫夫曼树{select(HT,i-1,s1,s2);//求Weight最小的两个结点s1,s2HT[s1].parent=i;HT[s2].parent=i;//修改HTHT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}

69赫夫曼编码算法(2)//从叶子到根逆向求每个字符的赫夫曼编码HC=(HuffmanCode)malloc((n+1)*sizeof(char*));cd=(char*)malloc(n*sizeof(char));cd[n-1]=“\0”;//编码结束符For(i=1;i<=n;++i){//逐个字符求赫夫曼编码start=n-1;//编码结束位置for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)if(HT[f].lchild==c)cd[--start]=“0”;elsecd[--start]=“1”;HC[i]=(char*)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间strcpy(HC[i],&cd[start]);}free(cd);}

70典型例题例1：统计二叉树中叶子结点的个数。（作业6.42）算法思想：先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增1。voidCountLeaf(BiTreeT,int&count){if(T){if((T->lchild==NULL)&&(T->rchild==NULL))count++;//对叶子结点计数CountLeaf(T->lchild,count);CountLeaf(T->rchild,count);}}

71例2：求二叉树的深度算法思想：如果树为空，则深度为零，如果树不为空，则令其深度等于左子树和右子树深度中较大者加1，即：当T=NULL时，depth(t)=0,否则depth(t)=MAX{depth(T->lchild),depth(T->rchild)}+1intDepth(BiTreeT)//返回二叉树的深度{if(!T)depth=0;else{depthLeft=Depth(T->lchild);depthRight=Depth(T->rchild);depth=1+(depthLeft>depthRight?depthLeft:depthRight);}return(depth);}

72作业6.3,6.5,6.7,6.12,6.15,6.16,6.17,6.19,6.22,6.23,6.24,6.26,6.27,6.28,6.42,6.43,6.54*