数据结构与算法 第四章 树与二叉树精.ppt

《数据结构与算法 第四章 树与二叉树精.ppt》由会员分享，可在线阅读，更多相关《数据结构与算法 第四章 树与二叉树精.ppt（75页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构与算法 第四章 树与二叉树11/30/20221第1页，本讲稿共75页第4章 树与二叉树l4.14.1 树的基本概念树的基本概念l4.2 4.2 二叉树二叉树l4.34.3 二叉树的遍历二叉树的遍历l4.44.4 线索二叉树线索二叉树l4.54.5 树和森林树和森林l4.64.6 哈夫曼树哈夫曼树11/30/20222第2页，本讲稿共75页4.1 树的基本概念4.1.1树的定义及表示树:n个结点的有限集(n=0)Root树根子树子树11/30/20223第3页，本讲稿共75页4.1.2 树的常用术语及运算l树的结点l结点的度-结点拥有的子树的个数l叶子结点-度为0的结点，又称终端结点l

2、分枝结点-度不为0的结点l树的度-树内结点度的最大值l树的层次-第一层从根结点开始，根的孩子在第二层，依此类推l树的深度-树中结点的最大层次ADEBCFHIGJKM11/30/20224第4页，本讲稿共75页4.1.2 树的常用术语及运算l孩子(结点)-结点的子树的根结点l双亲(结点)-结点作为根结点的子树的根结点l兄弟(结点)-同一个双亲的孩子结点之间互为兄弟l祖先-从根结点到该结点所经分枝上的所有结点l子孙-以某结点为根的子树中的任一结点都是该结点的子孙ADEBCFHIGJK11/30/20225第5页，本讲稿共75页4.1.2 树的常用术语及运算l树的基本运算(1)setnull(T):

3、初始化操作，置T为空树。(2)求根结点ROOT(T)或ROOT(x)。求树T的根或求结点x所在的树的根结点。若T是空树或x不在任何一棵树上，则函数值为“空”。(3)求双亲结点RARENT(T,x)。求树T中结点x的双亲结点。若结点x是树T的根结点或结点x不在树T中，则函数值为“空”。(4)求孩子结点CHILD(T,x,i)。求树T中结点x的第i个孩子结点。若结点x是树T的叶子或无第i个孩子或结点x不在树T中，则函数值为“空”。(5)建树creat(x,F)。生成以x结点为根、以森林F为子树森林的树。(6)求右兄弟结点RIGHT_SIBLING(T,x)。求树T中结点x右边的兄弟。若结点x是其双

4、亲的最右边的孩子结点或结点x不在树T中，则函数值为“空”。11/30/20226第6页，本讲稿共75页4.1.2 树的常用术语及运算l树的基本运算(7)插入子树操作addchild(y,i,x)。置以结点x为根的树为结点y的第i棵子树。若原树中无结点y或结点y的子树个数i-1，则空操作。(8)删除子树操作delchild(x,i)。删除结点x的第i棵子树。若无结点x或结点x的子树个数data;11/30/202223第23页，本讲稿共75页4.2.4 二叉树的简单运算实现（2）建立二叉树操作建立二叉树操作bitree create(elemtype x,bitree lbt,bitree rb

5、t)/*该该运运算算生生成成一一棵棵以以x为为根根结结点点，lbt和和rbt分别为左右子树的二叉树分别为左右子树的二叉树*/bitree p;p=(bitree)malloc(sizeof(bitnode);p-data=x;p-lchild=lbt;p-rchild=rbt;return p;/*返回建成的二叉树返回建成的二叉树*/11/30/202224第24页，本讲稿共75页4.2.4 二叉树的简单运算实现（3）插入左孩子：void add_lchild(bitree bt,elemtp x)bitree p;p=(bitree)malloc(sizeof(bitnode);p-data

6、=x;p-lchild=NULL;p-rchild=NULL;bt-lchild=p;/*插入插入bt的左孩子域的左孩子域*/11/30/202225第25页，本讲稿共75页4.2.4 二叉树的简单运算实现（4）删除左孩子：void delete_lchild(bitree bt)bitree p;p=bt-lchild;*保存左子树指针保存左子树指针*/bt-lchild=NULL;free(p);/*释放左子树空间释放左子树空间*/11/30/202226第26页，本讲稿共75页4.3二叉树的遍历l二叉树遍历：即如何按某条搜索路径巡访树中每个结点，使得每个结点均被访问次而且仅被访问次。l主

7、要有以下几种：l先序遍历 l中序遍历 l后序遍历 l层次遍历 11/30/202227第27页，本讲稿共75页4.3二叉树的遍历l先序遍历若二叉树为空，则空操作，否则，(1)访问根结点；(2)先序遍历左子树；(3)先序遍历右子树 ADEBCFHIGJKL12345678 9101112BDHIEJKGLFCA11/30/202228第28页，本讲稿共75页4.3二叉树的遍历l中序遍历l若二叉树为空，则空操作；否则，(1)中序遍历左子树；(2)访问根结点，(3)中序遍历右子树。ADEBCFHIGJKL12345678 9101112DIBAJEKGCFLH11/30/202229第29页，本讲稿

8、共75页4.3二叉树的遍历l后序遍历 若二叉树为空，则空操作；否则，(1)后序遍历左子树；(2)后序遍历右子树；(3)访问根结点。ADEBCFHIGJKL12345678 9101112IDJKEBLACGFH11/30/202230第30页，本讲稿共75页4.3二叉树的遍历l层次遍历：若二叉树为空，则空操作；否则，从根结点开始，自顶向下访问各层，从左到右访问同一层的结点。ADEBCFHIGJKL12345678 9101112BCDEFGHLKJIA11/30/202231第31页，本讲稿共75页4.3.1 遍历二叉树的递归算法（1）先序遍历二叉链表的递归算法：voidpreorder(bi

9、treebt)if(bt=NULL)return;/*递归结束条件递归结束条件*/elseprintf(“%dt”,bt-data);/*前序遍历左子树前序遍历左子树*/preorder(bt-lchild);/*前序遍历右子树前序遍历右子树*/preorder(bt-rchild);ADEBCFHIGJKL12345678 910111211/30/202232第32页，本讲稿共75页4.3.1 遍历二叉树的递归算法（1）先序遍历二叉链表的递归算法：preorder(A)if(A=NULL)return;else printf(“A”);preorder(B);preorder(C);pre

10、order(B)if(B=NULL)return;else printf(“B”);preorder(D);preorder(E);preorder(D)if(B=NULL)return;else printf(“D”);preorder(H);preorder(I);preorder(H)11/30/202233第33页，本讲稿共75页4.3.1 遍历二叉树的递归算法（2）中序遍历二叉链表的递归算法：voidinorder(bitreebt)if(bt=NULL)return;/*递归结束条件递归结束条件*/else/*中序遍历左子树中序遍历左子树*/inorder(bt-lchild);/

11、*访问根结点访问根结点*/printf(“%dt”,bt-data);/*中序遍历右子树中序遍历右子树*/inorder(bt-rchild);ADEBCFHIGJKL12345678 910111211/30/202234第34页，本讲稿共75页4.3.1 遍历二叉树的递归算法（3 3）后序遍历二叉链表的递归算法：）后序遍历二叉链表的递归算法：voidpostorder(bitreebt)if(bt=NULL)return;/*递归结束条件递归结束条件*/elsepostorder(bt-lchild);/*后序遍历左子树后序遍历左子树*/postorder(bt-rchild);/*后序遍

12、历右子树后序遍历右子树*/printf(“%dt”,bt-data);/*访问根结点访问根结点*/ADEBCFHIGJKL12345678 910111211/30/202235第35页，本讲稿共75页4.3.2 遍历二叉树的非递归算法l使用栈或队列，可以实现二叉树遍历的非递归算法。l（1）先序遍历二叉链表的非递归算法：#defineMAXSIZE100voidnrpreorder(bitreebt)bitreestackMAXSIZE,p;inttop=0;p=bt;dowhile(p!=NULL)printf(“%dt”,p-data);if(p-rchild!=NULL)/*如果右子树不

13、空如果右子树不空*/stack+top=p-rchild;/*右孩子进栈右孩子进栈*/p=p-lchild;if(top0)p=stacktop-;while(top0);/*当栈不空时继续遍历当栈不空时继续遍历*/ADEBCFHIGJKL12345678 9101112思路：沿左子树一直深入，并把所遇到结点的非空右孩子进栈；访问完左孩子后，思路：沿左子树一直深入，并把所遇到结点的非空右孩子进栈；访问完左孩子后，将右孩子出栈遍历其右子树。将右孩子出栈遍历其右子树。11/30/202236第36页，本讲稿共75页4.3.2 遍历二叉树的非递归算法l（2）中序遍历二叉链表的非递归算法：#defin

14、eMAXSIZE100voidnrinorder(bitreebt)bitreestackMAXSIZE,p;inttop=0;p=bt;dowhile(p!=NULL)stack+top=p;/*所遇结点进栈所遇结点进栈*/p=p-lchild;/*继续搜索继续搜索p的左子树的左子树*/if(top0)p=stacktop-;/*出栈一个结点出栈一个结点*/printf(“%dt”,p-data);/*访问结点访问结点*/p=p-rchild;/*继续搜索右子树继续搜索右子树*/while(top0);ADEBCFHIGJKL12345678 9101112思路：与前序遍历类同，只是沿左子树

15、向下搜索的过程中先将所遇结点进栈，思路：与前序遍历类同，只是沿左子树向下搜索的过程中先将所遇结点进栈，待遍历完左子树返回时从栈顶退出结点并访问，然后再遍历右子树。待遍历完左子树返回时从栈顶退出结点并访问，然后再遍历右子树。11/30/202237第37页，本讲稿共75页4.3.2 遍历二叉树的非递归算法（3）二叉树的层次遍历：void layer_travel_bitree(bitree*bt)bitree*p;/初始化队列Q，队列的元素为指向bitree结点的指针类型 init_Queue(Q);/根结点地址入队in_queue(Q,bt);while(!queue_empty(Q)p=ou

16、t_queue(Q);/出队 visit(p);/左孩子结点地址入队 if(p-lp!=NULL)in_queue(Q,p-lp);/右孩子结点地址入队 if(p-rp!=NULL)in_queue(Q,p-rp);ADEBCFHIGJKL12345678 910111211/30/202238第38页，本讲稿共75页4.3.3 遍历序列与二叉树的复原l必需至少提供2个不同的遍历序列，才能复原唯一的二叉树。1.利用前序序列和中序序列恢复二叉树例：前序ABDCEFG 中序DBAFEGC思路：前序序列确定根结点 中序列确定左子树和右子树11/30/202239第39页，本讲稿共75页4.3.3 遍

17、历序列与二叉树的复原2.利用后序序列和中序序列恢复二叉树例：后序DBFGECA 中序DBAFEGC思路：后序序列确定根结点 中序序列确定左子树和右子树11/30/202240第40页，本讲稿共75页4.3.3 遍历序列与二叉树的复原l必需至少提供2个不同的遍历序列，才能复原唯一的二叉树。1.利用前序序列和中序序列恢复二叉树例：前序ABDCEFG 中序DBAFEGC11/30/202241第41页，本讲稿共75页4.3.4 基于遍历的几种二叉树运算的 实现和应用举例1.查找结点x的运算2.求二叉树中的叶子结点数目3.求二叉树的高度11/30/202242第42页，本讲稿共75页1.查找结点x的运

18、算l查找二叉树bt中的结点x，可以结合在四种遍历算法中的任何一个算法中进行。在此我们以前序遍历来实现查找运算的递归算法。bitree search(bitree bt,elemtype x)if(bt!=NULL)if(bt-data=x)return bt;search(bt-lchild,x);/*在左子树中查找*/search(bt-rchild,x);/*在右子树中查找*/else return NULL;11/30/202243第43页，本讲稿共75页2.求二叉树中的叶子结点数目 l在遍历过程中对所遇结点判断是否为叶子结点，若是则统计变量加1，直到遍历完所有结点，叶子结点总数即可求得

19、。下面给出利用中序遍历求叶子结点数的递归算法：int countleaf(bitree bt)int num=0;if(bt!=NULL)if(bt-lchild=NULL)&(bt-rchild=NULL)num+;else num=countleaf(bt-lchild)+countleaf(bt-rchild);return num;11/30/202244第44页，本讲稿共75页3.求二叉树的高度 l可以在二叉树的前序或后序遍历过程中求出，下面给出的算法是在后序遍历过程中求深度的递归算法。int treedepth(bitree bt)int h,lh,rh;if(bt=NULL)h=

20、0;else lh=treedepth(bt-lchild);/*左子树高度赋lh*/rh=treedepth(bt-rchild);/*右子树高度赋rh*/if(lh=rh)h=lh+1;else h=rh+1;return h;11/30/202245第45页，本讲稿共75页4.4线索二叉树l4.4.1 线索二叉树的概念l思考：二叉树的遍历产生了一线性序列,如何不再通过重新遍历二叉树,而能够直接找到任一结点的前驱和后继呢？ABCDEFGHI方法一：结点中增加指向前驱和后继的指针左孩子前驱数据右孩子后继缺点：空间利用率低11/30/202246第46页，本讲稿共75页4.4.1 线索二叉树的

21、概念方法二：增加两个标志位rtag和ltag,利用现有的空指针域，n个结点的二叉树必有n+1个空指针域左孩子ltag数据右孩子rtagABCDEFHI11/30/202247第47页，本讲稿共75页线索二叉树的类型定义ltypedef enum0,1ptrtag;l typedef struct bithnodel elemtype data;l struct bithnode*lchild,*rchild;l ptrtag ltag,rtag;l bithrnode;l typedef bithrnode*bithrtree;11/30/202248第48页，本讲稿共75页4.4.1 线索二

22、叉树的概念中序线索二叉树举例中序序列中序序列DBHEIAFCGA00B00C00D11E00H11I11G11F1101二叉树中序线索后的结果二叉树中序线索后的结果11/30/202249第49页，本讲稿共75页4.4.2线索二叉树的构造算法建立线索二叉树的过程称作对二叉树线索化，线索化需要在遍历的过程中来实现。在对二叉树的某种次序遍历过程中，一边遍历一边建立线索，若当前访问结点的左孩子域为空则建立前趋线索，若右孩子域为空则建立后继线索。为实现这一过程，可设指针pre指向刚刚访问过的结点，指针p指向当前结点，就可以方便前趋和后继线索的填入。11/30/202250第50页，本讲稿共75页4.4

23、.2线索二叉树的构造算法中序遍历线索化二叉链表的算法：中序遍历线索化二叉链表的算法：11/30/202251第51页，本讲稿共75页4.4.3 线索二叉树上的运算实现遍历中序线索二叉树查找结点GA00B00C00D11E00H11I11G11F1101思路：先找到最左结点，然后不断找后继,直到回到头结点;查结点后继时若遇到右孩子不为空时，后继即为右子树的最左下结点。t11/30/202252第52页，本讲稿共75页4.4.3 线索二叉树上的运算实现例：中序线索二叉树的中序遍历：void inorderthr(bithrtree t)bithrtree p;p=t-lchild;while(p!

24、=t)/*空树或遍历结束时p=t*/while(p-ltag=0)p=p-lchild;/*找最左下结点*/printf(“%dt”,p-data);while(p-rtag=1)&(p-rchild!=t)p=p-rchild;printf(“%dt”,p-data);p=p-rchild;11/30/202253第53页，本讲稿共75页4.5树和森林l4.5.1 树和森林的存储结构l1、双亲表示法0 A-11 B02 D03 C04 I15 J16 7 G38 K6ADEBCFHIGJKL11/30/202254第54页，本讲稿共75页4.5.1 树和森林的存储结构l结点定义:typede

25、f struct node elemtp data;int parent;/指示双亲结点的下标 typedef struct node treemaxlen;int num;/结点个数 tree_parent;1、双亲表示法、双亲表示法0A-11B02D03C04I15J167G38K611/30/202255第55页，本讲稿共75页4.5.1 树和森林的存储结构l2、孩子表示法ABDCGKADEBCFHIGJKLBDCIJEFLGH11/30/202256第56页，本讲稿共75页4.5.1 树和森林的存储结构l3、孩子兄弟表示法AADEBCFHGJLBDCJEHFLGtypedef stru

26、ct csnode elemtp data;struct csnode*first,*next;cstree;11/30/202257第57页，本讲稿共75页4.5.2 树和森林与二叉树之间的转换1.森林转换成二叉树例ADEBCFHIGJ方法：方法：依次将每棵树都转换成二叉树；最后将每棵树作为前一依次将每棵树都转换成二叉树；最后将每棵树作为前一棵二叉树的右子树；棵二叉树的右子树；每棵树转换法则：将根结点第一个孩子转为其左孩子，每棵树转换法则：将根结点第一个孩子转为其左孩子，其他孩子转换为第一个孩子的右边孩子；其他孩子转换为第一个孩子的右边孩子；11/30/202258第58页，本讲稿共75页4

27、.5.2 树和森林与二叉树之间的转换2.二叉树转换成森林ACBDEFGHIJ逆过程，主要时将右子树断开，断开的原则时其左孩子不为空11/30/202259第59页，本讲稿共75页4.5.3 树和森林的遍历l由树的结构定义可以引出树的两种遍历：l先（根）序遍历：先访问根结点，然后先序遍历每棵子树；对应于二叉树的先根序遍历。ACBGDHJIFE先根序遍历序列是：先根序遍历序列是：A,B,E,F,C,G,D,H,I,J,KK11/30/202260第60页，本讲稿共75页4.5.3 树和森林的遍历l后（根）序遍历：先依此后序遍历每棵子树，然后访问根结点。对应二叉树的中根序遍历。ACBGDHJIFE先

28、根序遍历序列是：先根序遍历序列是：E,F,B,G,C,I,J,K,H,D,AK11/30/202261第61页，本讲稿共75页4.6哈夫曼树l4.6.1 哈夫曼树的概念及其构造算法10856721.路径和路径长度2.结点的权和带权路径长度3.树的带权路径长度WPL=带权树带权树11/30/202262第62页，本讲稿共75页4.6.1 哈夫曼树的概念及其构造算法l4.哈夫曼树:最优二叉树，带权路径长度最小的树 l例：叶子结点的权为7,5,2,475242475752411/30/202263第63页，本讲稿共75页4.6.1 哈夫曼树的概念及其构造算法l5.哈夫曼算法Huffman给出了一个建

29、立哈夫曼树的算法：例：2，6，6，8，12，142866814122014284811/30/202264第64页，本讲稿共75页4.6.2哈夫曼树的应用哈夫曼编码l传送的电文为ABACCDA(1)定长编码：A,B,C,D编码为00,01,10,11传输的长度为总长14位(2)可变长编码:A,B,C,D编码为0,00,1,01传输的长度为总长9位,但却无法译码(3)使用可变长编码的前缀编码，使每个符号唯一编码,用哈夫曼树构造最短的前缀编码.11/30/202265第65页，本讲稿共75页4.6.2哈夫曼树的应用哈夫曼编码l例：字符集a,b,c,d,e字符出现的次数为6,4,1,10,5，请对它

30、们进行哈夫曼编码1546510101626cbead0111100011/30/202266第66页，本讲稿共75页4.6.3哈夫曼算法的静态实现l1.二叉树的静态链表实现0 A12-11 B3402 C5603 D7814 E-1-116 7 H-1-138 I-1-13ADEBCFHIGLCHILD RCHILDPARENT11/30/202267第67页，本讲稿共75页2.哈夫曼树的静态实现cbaed260 c-1-1511 b-1-1542 e-1-1653 a-1-1764 d-1-171051465652810734816867-126哈夫曼树的静态存储结构哈夫曼树的静态存储结构1

31、6105514610左左右右双亲双亲权权11/30/202268第68页，本讲稿共75页2.哈夫曼树的静态实现0 c-1-1511 b-1-1542 e-1-1653 a-1-1764 d-1-171051465652810734816867-126左左右右双亲双亲权权哈夫曼树的类型定义哈夫曼树的类型定义#define maxnodenumber 100#define maxnodenumber 100typedef structtypedef structint weight;int weight;int parent,lchild,rchild;int parent,lchild,rchi

32、ld;htnode;/*htnode;/*定义结点类型定义结点类型*/定义哈夫曼树类型定义哈夫曼树类型typedef htnode*huffmantree;typedef htnode*huffmantree;定义哈夫曼树的存储区域定义哈夫曼树的存储区域 htnode htmaxnodenumber;htnode htmaxnodenumber;11/30/202269第69页，本讲稿共75页2.哈夫曼树的静态实现0-1-1-101-1-1-102-1-1-103-1-1-104-1-1-105-1-1-106-1-1-107-1-1-108-1-1-10左左右右双亲双亲权权哈夫曼树的创建过程

33、哈夫曼树的创建过程例：a,b,c,d,e:6,4,1,10,56415105215510456616037726678811/30/202270第70页，本讲稿共75页3.哈夫曼编码的实现思考：如何从已知的哈夫曼树得出思考：如何从已知的哈夫曼树得出哈夫曼编码哈夫曼编码 提示：从叶子结点出发找双亲提示：从叶子结点出发找双亲,如果是双亲的做孩子则编码如果是双亲的做孩子则编码0，右，右孩子编码孩子编码1。每个叶子结点编码用一维数组每个叶子结点编码用一维数组存储。存储。N个叶子结点则需要个叶子结点则需要n个相个相同的一维数组同的一维数组0-1-1-101-1-1-102-1-1-103-1-1-104

34、-1-1-105-1-1-106-1-1-107-1-1-108-1-1-10左左右右双亲双亲权权6415105215510456616037726678811/30/202271第71页，本讲稿共75页3.哈夫曼编码的实现（续）l对于每个叶子结点的哈夫曼编码可以考虑用一个一维数组bit从后向前依次保存所求得的各位编码值，并用start记住编码在数组bit中的开始位置。l由此可做如下的类型定义：#define maxbit 10/定义编码最大长度 typedef struct /定义保存一个叶子节点的结构 int bitmaxbit;/*用一维数组保存一个叶子结 点编码*/int start;

35、/开始位置域 hcodetype;Hcodetype cdmaxnodenum;/*定义编码数组，保存所有叶子结点编码，具体使用过程中，只用到n个长度11/30/202272第72页，本讲稿共75页3.哈夫曼编码的实现（续1）1 0 80 0 1 70 0 0 71 1 80 1 8哈夫曼树哈夫曼树哈夫曼树的编码哈夫曼树的编码结果结果编码编码Cd5start0-1-1-101-1-1-102-1-1-103-1-1-104-1-1-105-1-1-106-1-1-107-1-1-108-1-1-10左左右右双亲双亲权权6415105215510456616037726678811/30/202

36、273第73页，本讲稿共75页3.哈夫曼编码的实现（续）hcodetype cdmaxnodenum;hcodetype cdmaxnodenum;void gethuffmancode(int n)void gethuffmancode(int n)int i,j,c,p;int i,j,c,p;for(i=0;in;i+)/for(i=0;in;i+)/对对n n个叶子结点逐一求编码个叶子结点逐一求编码 c=i;j=maxbit;c=i;j=maxbit;doj-;p=htc.parent;doj-;p=htc.parent;if(htp.lchild=c)/*if(htp.lchild=

37、c)/*如果如果c c是是p p的左孩子的左孩子*/cdi.bitj=0;cdi.bitj=0;else else cdi.bitj=1;cdi.bitj=1;c=p;c=p;while(htp.parent!=-1);while(htp.parent!=-1);cdi.start=j;cdi.start=j;for(i=0;in;i+)/for(i=0;in;i+)/输出输出n n个字符编码个字符编码 for(j=cdi.start;jmaxbit;j+)for(j=cdi.start;jmaxbit;j+)printf(printf(“%d%d”,cdi.bitj);,cdi.bitj);printf(printf(“nn”););0-1-1-101-1-1-102-1-1-103-1-1-104-1-1-105-1-1-106-1-1-107-1-1-108-1-1-10左左右右双亲双亲权权6415105215510456616037726678811/30/202274第74页，本讲稿共75页小结l树的基本概念树的基本概念l二叉树二叉树l二叉树的遍历二叉树的遍历l线索二叉树线索二叉树l树和森林树和森林l哈夫曼树哈夫曼树11/30/202275第75页，本讲稿共75页