《第八章树与二叉树.ppt》由会员分享，可在线阅读，更多相关《第八章树与二叉树.ppt（87页珍藏版）》请在三一办公上搜索。
1、,第八章 树与二叉树,1.树的定义及其基本概念,2.二叉树的基本概念和存储结构,3.二叉树的遍历,4.线索二叉树的概念及其遍历,6.哈夫曼树及其构造方法,7.树与森林,5.二叉排序树,8.1 树的概念和基本术语,一、树的定义 树是由 n(n 0)个结点的有限集合。如果 n=0，称为空树；如果 n 0，则 有且仅有一个特定的称之为根(Root)的结点，它只有直接后继，但没有直接前驱；当n 1，除根以外的其它结点划分为 m(m 0)个互不相交的有限集 T1,T2,Tm，其中每个集合本身又是一棵树，并且称为根的子树(SubTree)。,根,子树,特点：树中至少有一个结点根 树中各子树是互不相交的集合
2、,二、树的表示,1树形结构表示法,2.凹入法表示法,3.嵌套集合表示法（文氏图表示法）,4.广义表表示法（括号表现法）对树结构，广义表表示法可表示为：(A(B(E(J，K，L)，F)，C(G)，D(H(M)，I),分支(branch)：结点之间的二元关系（序偶）。结点(node)：一个数据元素及指向其子树的分支。结点的度(degree)：结点拥有的子树个数。叶结点(leaf)：度为零的结点。分支结点(branch node):有后继的结点称为分支结点。儿子(sons)：结点x的子树的根。父亲(parent):结点x的前驱结点称为x的父亲。兄弟(brother)：同一父亲的结点的子女结点。祖先(
3、ancestor)：根到该结点路径上的所有结点。子孙(descendant)：某结点为根的子树上的任意结点。堂兄弟(cousin):父亲是兄弟关系或堂兄弟关系的结点。,结点层次(level)：从根开始，根为第一层，根的子女为第二层，以此类推。树的深度（高度）(depth)：树中结点的最大层次数树的度：一棵树中最大的结点度数。结点按层编号（层中编号）：将树中结点按从上层到下层，同层从左到右的次序排成一个线性序列，依次给他们编以连续的自然数。祖辈（上层）：层号比结点x小的结点，称为x的祖辈。后辈（下层）：层号比结点x大的结点，称为x的后辈。有序树：若一棵树中所有子树从左到右的排序是有顺序的，不能颠
4、倒次序。称该树为有序树。无序树：若一棵树中所有子树的次序无关紧要，则称为无序树。森林(forest)：m(m 0)棵互不相交的树。,三、树的基本术语,1层,2层,4层,3层,height=4,A,C,G,B,D,E,F,K,L,H,M,I,J,结点结点的度叶结点分支结点,子女双亲兄弟,祖先子孙结点层次,树的深度树的度有序树无序树森林,结点A的度：3结点B的度：2结点M的度：0,叶子：K，L，F，G，M，I，J,结点A的孩子：B，C，D结点B的孩子：E，F,结点I的父亲：D结点L的父亲：E,结点B，C，D为兄弟结点K，L为兄弟,树的度：3,结点A的层次：1结点M的层次：4,树的深度：4,结点F，
5、G为堂兄弟结点A是结点F，G的祖先,8.2 二叉树(Binary Tree),定义:,五种形态:,一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。,特点:,每个结点至多只有两棵子树（二叉树中不存在度大于2的结点）,二叉树的基本操作,（1）creat_tree(bt,str)根据二叉树的括号表示法str建立一棵二叉树bt。（2）disptree(bt)以凹入法显示一棵二叉树bt。（3）depth_bttree(bt)求一棵二叉树bt的深度。（4）count_bttree(bt)求一棵二叉树bt的结点个数。（5）leafco
6、unt_bttree(bt)求一棵二叉树bt的叶子结点个数。（6）nleafcount_bttree(bt)求一棵二叉树bt 的非叶子结点个数。,性质1 在二叉树的第 i 层上至多有 2i 1个结点。(i 1)证明用归纳法证明：当i=1时，只有根结点，2 i-1=2 0=1。假设对所有j，ij1，命题成立，即第j层上至多有2 j-1 个结点。由归纳假设第i-1 层上至多有 2i 2个结点。由于二叉树的每个结点的度至多为2，故在第i层上的最大结点数为第i-1层上的最大结点数的2倍，即2*2i 2=2 i-1。,二叉树的性质,性质2 深度为 k 的二叉树至多有 2k-1个结点(k 1)。证明：由性
7、质1可见，深度为k的二叉树的最大结点数为,性质3 对任何一棵二叉树T,如果其叶结点数为 n0,度为2的结点数为 n2,则n0n21.证明：若度为1的结点有 n1 个，总结点个数为 n，总边数为 e，则根据二叉树的定义，n=n0+n1+n2 e=2n2+n1=n-1因此，有 2n2+n1=n0+n1+n2-1 n2=n0-1 n0=n2+1,定义1 满二叉树(Full Binary Tree)一棵深度为k且有2k-1个结点的二叉树称为满二叉树。,两种特殊形态的二叉树,非完全二叉树,定义2 完全二叉树(Complete Binary Tree)若设二叉树的高度为h，则共有h层。除第 h 层外，其它
8、各层(0 h-1)的结点数都达到最大个数，第 h 层从右向左连续缺若干结点，这就是完全二叉树。,完全二叉树,性质4 具有 n(n 0)个结点的完全二叉树的深度为log2(n)1 证明：设完全二叉树的深度为 h，则根据性质2和完全二叉树的定义有2h1-1 n 2h-1或 2h1 n 2h取对数 h1 log2n h，又h是整数，因此有 h=log2(n)1,性质5 如将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号 1,2,n，则有以下关系：若i=1,则 i 无双亲若i 1,则 i 的双亲为(i/2)若2*i n,则 i 无左孩子,否则其左孩子是结点2i.若2*i+1n,则结点
9、i无右孩子,否则其右孩子为结点2*i+1,完全二叉树 一般二叉树的顺序表示 的顺序表示,8.3 二叉树的存储结构,一、顺序表示,二、链表表示,二叉树链表表示的示例,二叉树 二叉链表 三叉链表,typedef struct btnode struct btnode*lchild;int data;struct btnode*rchild;bitnode,*bitree;,二叉链表的定义,若一个二叉树含有n个结点，则它的二叉链表中必含有2n个指针域，其中必有n+1个空链域。证明：边数e=n-1;即非空链域为n-1个，则空链域为2n-(n-1)=n+1个。,三、二叉链表的递归创建及其基本操作的实现,
10、char s=,a,b,c,d,e,f,g,h,I;root=creat_tree(s,1);bitree creat_tree(char*s,int p)bitree new;if(sp=|p15)return NULL;else new=(bitree)malloc(sizeof(bitree);new-data=sp;new-lchild=creat_tree(s,2*p);new-rchile=creat_tree(s,2*p+1);return new;,8.4 二叉树遍历,树的遍历就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。设访问根结点记作 V 遍历根的左子树记
11、作 L 遍历根的右子树记作 R 则可能的遍历次序有 前序 VLR 中序 LVR 后序 LRV,中序遍历二叉树算法的定义：若二叉树为空，则空操作；否则中序遍历左子树(L)；访问根结点(V)；中序遍历右子树(R)。遍历结果 a+b*c-d-e/f,中序遍历(Inorder Traversal),void inorder(bitree bt)if(bt!=NULL)inorder(bt-lchild);printf(“%c”,bt-data);inorder(bt-rchild);,中序遍历二叉树的递归算法,前序遍历二叉树算法的定义：若二叉树为空，则空操作；否则访问根结点(V)；前序遍历左子树(L)
12、；前序遍历右子树(R)。遍历结果-+a*b-c d/e f,前序遍历(Preorder Traversal),前序遍历二叉树的递归算法void preorder(bitree bt)if(bt!=NULL)printf(“%c”,bt-data);preorder(bt-lchild);preorder(bt-rchild);,后序遍历二叉树算法的定义：若二叉树为空，则空操作；否则后序遍历左子树(L)；后序遍历右子树(R)；访问根结点(V)。遍历结果 a b c d-*+e f/-,后序遍历(Postorder Traversal),后序遍历二叉树的递归算法：void postorder(bi
13、tree bt)if(bt!=NULL)postorder(bt-lchild);postorder(bt-rchild);printf(“%c”,bt-data);,非递归实现先序遍历二叉树 利用一个一维数组作为栈，来存储二叉链表中结点，算法思想为：1、从二叉树根结点开始，先将根结点入栈。2、然后将栈顶结点出栈，输出结点的值，同时判断该结点有没有右子树，有则将右子树的根结点入栈；再判断有没有左子树，有则将左子树的根结点入栈。如果栈不空则重复第2步，直到栈为空。,void preorder(bitree root)bitree p,stack100;int top=-1;/top为栈顶指针 i
14、f(root!=NULL)top+;stacktop=root;/将根结点压入栈内 while(top!=-1)p=stacktop;top-;printf(“%d”,p-data);if(p-rchild!=NULL)stack+top=p-rchlid;/压右子树 if(p-lchild!=NULL)stack+top=p-lchild;/压左子树,非递归实现中序遍历二叉树 同样利用一个一维数组作栈，来存贮二叉链表中结点，算法思想为：1、将所指的结点的左子树入栈，其下面的左子树也入栈2、弹出一个结点并输出，判断其是否有右子树，有则入栈，再转到第1步，没有右子树则判断栈是否为空，不空则弹出一
15、个结点，转回第2步，为空则结束。,void inorder(bitree root)bitree p=root,stack100;/s为一个栈，top为栈顶指针 int top=-1;do while(p!=NULL)top+;stacktop=p;p=p-lchild;if(top=0)p=stacktop;top-;printf(“%d”,p-data);p=p-rchild;while(p!=NULL|top=0);,非递归实现后序遍历二叉树 在后序遍历中，当搜索指针指向某一个结点时，不能马上进行访问，而先要遍历左子树，所以此结点应先进栈保存，当遍历完它的左子树后，再次回到该结点，还不能
16、访问它，还需先遍历其右子树,所以该结点还必须再次进栈，只有等它的右子树遍历完后，再次退栈时，才能访问该结点。为了区分同一结点的三次进栈及出栈，引入一个栈次数的标志，一个元素第一次进栈标志为1，第二次进标志为2，第三次进栈标志为3，并将标志同时存入栈中，当出栈的元素的标志为3时，才输出此结点。,struct forpost int sign;bitnode*treenode;void postorder(bitnode*root)forpost stack100,p,q;int top=0,i;p.treenode=root;p.sign=1;stacktop=p;top+;/将根结点入栈,wh
17、ile(top!=0)top-;p=stacktop;if(p.treenode!=NULL)if(p.sign=1)q.treenode=p.treenode;q.sign=2;stacktop+=q;q.treenode=p.treenode-lchild;q.sign=1;stacktop+=q;if(p.sign=2)q.treenode=p.treenode;q.sign=3;stacktop+=q;q.treenode=p.treenode-rchild;q.sign=1;stacktop+=q;if(p.sign=3)printf(“%dt”,p.treenode-data);,
18、线索二叉树的引入：对二叉树遍历的过程实质上是对一个非线性结构进行线性化的操作。以二叉链表为存储结构时,结点的左右孩子可以直接找到,但不能直接找到结点的前驱和后继,而结点的前驱和后继只有在遍历二叉树的过程中才能得到。用二叉链表表示的二叉树中,n个结点的二叉树有n+1个空链域，可利用这些空链域存储结点的前驱或后继。,8.5 线索二叉树(Threaded Binary Tree),ltag=0,lchild为左孩子指针ltag=1,lchild为前驱线索rtag=0,rchild为右孩子指针rtag=1,rchild为后继线索,typedef struct bithrnode elemtype da
19、ta;/*数据域*/struct bithrnode*lchild，*rchild;/*左右指针*/ptrtag ltag,rtag;/*左右标志*/bithrnode,*bithrtree;,线索二叉树 中结点的定义,线索二叉树的创建和遍历,中序构造线索二叉树算法思想:对二叉树一边中序遍历一边建线索,若访问结点的左孩子为空,建立前趋线索;若右孩子为空,建立后继线索。并且在二叉树的线索链表上也添加一个头结点，并令其lchild域的指针指向二叉树的根结点，其rchild域的指针指向中序序列的最后一个结点；反之，令二叉树的中序序列的第一个结点的lchild域指针和最后一个结点rchild域的指针均
20、指向头结点。,先序序列为：ABCD,中序序列为：BADC,后序序列为：BDCA,void inthread(bithrtree p,bithrtree pre)if(p)inthread(p-lchild,pre)/左子树线索化 if(p-lchild=NULL)p-ltag=1;p-lchild=pre;/产生前驱 if(p-rchild=NULL)pre-rtag=1;pre-rchild=p;/产生后继 pre=p;/保持pre指向p的前驱 inthread(p-rchild,pre);/右子树线索化,遍历中序线索二叉树算法思想：先判断指针域是用作线索还是指向子树，再决定是否进行递归调用
21、。bithrtree inorder_thread(bithrtree t)bithrtree thrt,pre,p;thrt=(bithrtree)malloc(sizeof(bithrnode);thrt-ltag=0;thrt-rtag=1;thrt-rchild=thrt;if(t=NULL)thrt-lchild=thrt;else p=thrt-lchild=t;thrt-ltag=0;pre=thrt;inthread(p,pre);pre-rtag=1;thrt-rchild=pre;thrt-rtag=1;return thrt;,8.6 二叉排序树,二叉排序树（二叉查找树）
22、是一种特殊的二叉树，一般二叉树中只区分左、右子树，但不区分结点的顺序，在二叉排序树中，所有结点都是有序的。特征：（1）若它左子树非空，则左子树上的所有结点的关键字均小于根结点的关键字。（2）若它右子树非空，则右子树上所有结点的关键字均大于根结点的关键字。（3）左、右子树本身各又是一个二叉排序树。,利用二叉排序树进行查找，算法比较简单如想查找数据6，先和根5比较，转到右子树上查找，再比较7，转左子树上，就找到了6。即为查找算法中的二分查找法。,二叉查找树的查找 bitree binary_traverse_search(bitree p,int v)while(p!=NULL)if(p-data
23、=value)return p;else if(p-datav)p=p-lchild;else p=p-rchild;return NULL;,main()bitree root=NULL,p;int v,s16=0,5,4,7,2,0,6,8,1,3,0,0,0,0,0,0;root=creat_tree(s,1);printf(“请输入要查找的结点的值：n”);scanf(“%d”,8.7 哈夫曼树(Huffman Tree),一、哈夫曼(Huffman)树,又称最优树,是一类带权路径长度最短的树1路径和路径长度在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为路径。通路中
24、分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。2结点的权及带权路径长度若将树中结点赋予一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。,3树的带权路径长度树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为wpl=，其中n 为叶子结点数目，wi为第i 个叶子结点的权值，li 为第i 个叶子结点的路径长度。,WPL=2*2+WPL=2*1+WPL=7*1+4*2+5*2+4*2+5*3+5*2+2*3+7*2=36 7*3=46 4*3=35,带权路径长度达到最小,哈夫曼树
25、,树的带权路径长度达到最小的二叉树即为哈夫曼树。在哈夫曼树中，权值大的结点离根最近。,(1)由给定的 n 个权值 w0,w1,w2,wn-1，构造具有 n 棵扩充二叉树的森林 F=T0,T1,T2,Tn-1，其中每棵扩充二叉树 Ti 只有一 个带权值 wi 的根结点,其左、右子树均为空。,二、哈夫曼树的构造算法,(2)重复以下步骤,直到 F 中仅剩下一棵树为止：在 F 中选取两棵根结点的权值最小的扩充二叉树,做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。在 F 中删去这两棵二叉树。把新的二叉树加入 F。,哈夫曼树的构造过程,例 w=5,29,7,
26、8,14,23,3,11,三、哈夫曼树的应用-哈夫曼编码,在传送电文时,总是希望传送的时间尽可能短，如果每个字符设计长度不等的编码，且能让出现频率高的采用尽可能短的编码，则传送的电文长度就会缩短。例如：需要传送的电文为“ABACCDA”,如果设计A、B、C、D的编码分别为0、00、1和01，则上述7个字符的电文就转换成为长度为9个字符串“000011010”。,前缀编码：设计长短不等的编码，必须使任何一个字符都不是另一个字符的前缀，这样保证译码的唯一性。,哈夫曼编码,主要用途是实现数据压缩。,设给出一段报文：CAST CAST SAT AT A TASA字符集合是 C,A,S,T，各字符出现概
27、率为 C:2/18,A:7/18,S:4/18,T:5/18,化整为 2,7,4,5。若给每个字符以等长编码 A:00 T:10 C:01 S:11则总编码长度为(2+7+4+5)*2=36.,若按各个字符出现的概率不同而给予不等长编码，尽可能减少总编码长度。各字符出现概率为 2,7,4,5。以它们为各叶结点上的权值,建立哈夫曼树。左分支赋 0，右分支赋 1，得哈夫曼编码(变长编码)。,CAST CAST SAT AT A TASA A:0 T:10 C:110 S:111它的总编码长度：7*1+5*2+(2+4)*3=35。比等长编码的情形要短。总编码长度正好等于哈夫曼树的带权路径长度WPL
28、。哈夫曼编码是一种无前缀编码(都由叶结点组成,路径不会重复)。解码时不会混淆。哈夫曼编码:A:0 T:10 C:110 S:111110011110 11001111011101001001001110等长编码:A:00 T:10 C:01 S:11010011100100111011001000100010001100,#define MAX 50 typedef struct char data;int weight;int parent;int left;int right;int flag;huffnode;huffnode ht2*MAX;,int select(int i)int
29、k=32767,j,q;for(j=0;j=i;j+)if(htj.weightk,void creat_hufftree(int n)int i,k,l,r;for(i=0;i2*n-1;i+)hti.parent=hti.left=hti.right=hti.flag=-1;for(i=n;i2*n-1;i+)l=select(i-1);r=select(i-1);htl.parent=i;htr.parent=i;hti.weight=htl.weight+htr.weight;hti.left=l;hti.right=r;,哈夫曼编码算法：在建好的哈夫曼树中求哈夫曼编码，实质上就是从叶
30、结点开始，沿结点的双亲链域回退到根结点，每回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值。这样求得的码是从低位到高位，可以设置一结构体数组huffcode来存放各字符的哈夫曼编码。其结构如下：,其中cd是一维数组用来存放编码，start表示该编码在数组cd中的开始位置。对于第i个字符，它的编码存放在huffcodei.cd中的从huffcodei.start到n的分量上。,typedef struct char cdMAX;int start;huffcode;huffcode hcdMAX;,w parent l r flag,0 1 2 3 4 5 6,creat_huffc
31、ode(int n)int i,f,c;huffcode d;for(i=0;in;i+)d.start=n+1;c=i;f=hti.parent;while(f!=-1)if(htf.left=c)d.cd-d.start=0;else d.cd-d.start=1;c=f;f=htf.parent;hcdi=d;,void display_huffcode(int n)int i,k;printf(“输出哈夫曼编码：n”);for(i=0;in;i+)printf(“%c:”,hti.data);for(k=hcdi.start;k=n;k+)printf(“%c”,hcdi.cdk);p
32、rintf(“n”);,一、树的存储结构1、双亲表示：以一组连续空间存储树的结点，同时在结点中附设一个指针，存放双亲结点在链表中的位置。该方法利用每个结点只有一个双亲的特点，可以很方便求结点的双亲，但不方便求结点的孩子。,8.8 树与森林,用双亲表示实现的树定义,typedef struct char data;int parent;ptnode;typedef struct ptnode nodesMAXSIZE;int nodenum;pttree;,A,B,C,D,E,F,G,2、孩子表示法(多重链表),第一种解决方案 等数量的链域(d为树的度),第二种解决方案 孩子链表,将每个结点的孩
33、子链在该结点之后组成链表，再将所有头结点组成一个线性表。,孩子表示法的存储结构类型定义,typedef struct cnode int child;struct cnode*next;childlink;typedef struct char data;childlink*headptr;ctnode;/*表头向量中结点结构*/typedef struct ctnode nodesMAXSIZE;/*表头向量*/int nodenum,rootset;/*树中结点个数和根结点所在位置序号*/cttree;,结点结构,空链域n+1个,3、树的孩子兄弟表示法（二叉链表表示）,用孩子兄弟表示法实现
34、的优缺点,这种树的存储结构的最大优点是结点结构统一，和二叉树的表示完全一样，因此可利用二叉树的算法来实现对树的操作。在这个结构上，易于实现查找某结点孩子的操作。在这个结构上查找某结点的双亲结点的算法不很方便，如果为每一个结点增设一个parent域，则查找某结点的双亲的操作也很方便。,1、将树转换成二叉树 对于一棵无序树，树中结点的各孩子次序是无关紧要的，而二叉树中结点的左、右孩子是有区别的。为了避免混淆，我们约定树中每一个结点的孩子结点按从左到右的顺序编号，也就是说，把树作为有序树看待。,二、森林与二叉树的转换,1、加线：在兄弟之间加一连线2、抹线：对每个结点，除了其左孩子外，去 除其与其余孩
35、子之间的关系3、旋转：以树的根结点为轴心，将整树顺时 针转45,将一棵树转换为二叉树的方法是：,结点A有三个孩子B、C、E，可以认为结点B为A的第一个孩子，结点E为A的第三个孩子。,树转换成的二叉树其右子树一定为空,2、森林转换成二叉树,3、将二叉树转换成树加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都与p的双亲用线连起来抹线：抹掉原二叉树中双亲与右孩子之间的连线调整：将结点按层次排列，形成树结构,4、二叉树转换成森林抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树还原：将孤立的二叉树还原成树,
36、当树非空访问根结点 依次先序遍历根的各棵子树树先序遍历 ABEFCDG对应二叉树前序遍历 ABEFCDG树的先序遍历结果与其对应二叉树 表示的前序遍历结果相同树的先序遍历可以借助对应二叉树的前序遍历算法实现,树的先序遍历,树的后序遍历:,当树非空时依次后序遍历根的各棵子树访问根结点树后序遍历 EFBCGDA对应二叉树中序遍历 EFBCGDA树的后序遍历结果与其对应二叉树 表示的中序遍历结果相同树的后序遍历可以借助对应二叉树的中序遍历算法实现,森林的遍历,森林也有前序和后序两种遍历运算。森林的前序遍历就是从左到右对组成森林的各树进行前序遍历,也等价于对相应的二叉树进行前序遍历。森林的后序遍历也是从左到右对组成森林的各树进行后序遍历，也等价于对相应的二叉树进行中序遍历。,本章小结,1.掌握树及其二叉树的定义和基本概念,2.掌握二叉树的遍历算法3.掌握线索二叉树的建立和遍历算法,4.掌握树的存储结构及其与森林、二叉树之间的转换,5.掌握哈夫曼树的构造和编码算法,
