《树与二叉树 》PPT课件.ppt

,第八章 树与二叉树,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)。,根,子树,特点：树中至少有一个结点根 树中各子树是互不相交的集合,二、树的表示,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)：同一父亲的结点的子女结点。 祖先(ancestor)：根到该结点路径上的所有结点。 子孙(descendant)：某结点为根的子树上的任意结点。 堂兄弟(cousin):父亲是兄弟关系或堂兄弟关系的结点。,结点层次(level)：从根开始，根为第一层，根的子女为第二层，以此类推。 树的深度（高度）(depth)：树中结点的最大层次数 树的度：一棵树中最大的结点度数。 结点按层编号（层中编号）：将树中结点按从上层到下层，同层从左到右的次序排成一个线性序列，依次给他们编以连续的自然数。 祖辈（上层）：层号比结点x小的结点，称为x的祖辈。 后辈（下层）：层号比结点x大的结点，称为x的后辈。 有序树：若一棵树中所有子树从左到右的排序是有顺序的，不能颠倒次序。称该树为有序树。 无序树：若一棵树中所有子树的次序无关紧要，则称为无序树。 森林(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，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）leafcount_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)。 证明：由性质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 层外，其它各层 (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,则结点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个。,三、二叉链表的递归创建及其基本操作的实现,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 遍历根的左子树记作 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)； 前序遍历右子树 (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 (bitree 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为栈顶指针 if(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步，没有右子树则判断栈是否为空，不空则弹出一个结点，转回第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); ,非递归实现后序遍历二叉树 在后序遍历中，当搜索指针指向某一个结点时，不能马上进行访问，而先要遍历左子树，所以此结点应先进栈保存，当遍历完它的左子树后，再次回到该结点，还不能访问它，还需先遍历其右子树,所以该结点还必须再次进栈，只有等它的右子树遍历完后，再次退栈时，才能访问该结点。 为了区分同一结点的三次进栈及出栈，引入一个栈次数的标志，一个元素第一次进栈标志为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+;/将根结点入栈,while(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); ,线索二叉树的引入： 对二叉树遍历的过程实质上是对一个非线性结构进行线性化的操作。以二叉链表为存储结构时,结点的左右孩子可以直接找到,但不能直接找到结点的前驱和后继,而结点的前驱和后继只有在遍历二叉树的过程中才能得到。 用二叉链表表示的二叉树中,n个结点的二叉树有n+1个空链域，可利用这些空链域存储结点的前驱或后继。,8.5 线索二叉树 (Threaded Binary Tree),ltag=0, lchild为左孩子指针 ltag=1, lchild为前驱线索 rtag=0, rchild为右孩子指针 rtag=1, rchild为后继线索,typedef struct bithrnode elemtype data; /*数据域*/ struct bithrnode *lchild，*rchild; /*左右指针*/ ptrtag ltag,rtag;/*左右标志*/ bithrnode,*bithrtree;,线索二叉树 中结点的定义,线索二叉树的创建和遍历,中序构造线索二叉树算法思想: 对二叉树一边中序遍历一边建线索,若访问结点的左孩子为空,建立前趋线索;若右孩子为空,建立后继线索。 并且在二叉树的线索链表上也添加一个头结点，并令其lchild域的指针指向二叉树的根结点，其rchild域的指针指向中序序列的最后一个结点；反之，令二叉树的中序序列的第一个结点的lchild域指针和最后一个结点rchild域的指针均指向头结点。,先序序列为：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);/右子树线索化 ,遍历中序线索二叉树算法思想： 先判断指针域是用作线索还是指向子树，再决定是否进行递归调用。 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 二叉排序树,二叉排序树（二叉查找树）是一种特殊的二叉树，一般二叉树中只区分左、右子树，但不区分结点的顺序，在二叉排序树中，所有结点都是有序的。 特征： （1）若它左子树非空，则左子树上的所有结点的关键字均小于根结点的关键字。 （2）若它右子树非空，则右子树上所有结点的关键字均大于根结点的关键字。 （3）左、右子树本身各又是一个二叉排序树。,利用二叉排序树进行查找，算法比较简单 如想查找数据6，先和根5比较，转到右子树上查找，再比较7，转左子树上，就找到了6。即为查找算法中的二分查找法。,二叉查找树的查找 bitree binary_traverse_search(bitree p,int v) while(p!=NULL) if(p-data=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路径和路径长度 在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为路径。通路中分支的数目称为路径长度。 若规定根结点的层数为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,带权路径长度达到最小,哈夫曼树,树的带权路径长度达到最小的二叉树即为哈夫曼树。 在哈夫曼树中，权值大的结点离根最近。,(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, 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 ，各字符出现概率为 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。 哈夫曼编码是一种无前缀 编码(都由叶结点组成,路径 不会重复)。解码时不会混淆。 哈夫曼编码: A : 0 T : 10 C : 110 S : 111 110011110 11001111011101001001001110 等长编码: A : 00 T : 10 C : 01 S : 11 010011100100111011001000100010001100,#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 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; ,哈夫曼编码算法： 在建好的哈夫曼树中求哈夫曼编码，实质上就是从叶结点开始，沿结点的双亲链域回退到根结点，每回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值。 这样求得的码是从低位到高位，可以设置一结构体数组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_huffcode(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); printf(“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为树的度),第二种解决方案 孩子链表,将每个结点的孩子链在该结点之后组成链表，再将所有头结点组成一个线性表。,孩子表示法的存储结构类型定义,typedef struct cnode int child; struct cnode *next; childlink; typedef struct char data; childlink *headptr; ctnode; /*表头向量中结点结构*/ typedef struct ctnode nodesMAXSIZE; /*表头向