《第02章树与二叉树(0928).ppt》由会员分享，可在线阅读，更多相关《第02章树与二叉树(0928).ppt（68页珍藏版）》请在三一办公上搜索。
1、第 1 页,本单元涉及的内容,2.5树与二叉树树的基本概念二叉树及其基本性质特殊二叉树的表示及性质二叉树的遍历操作及有关算法树、二叉树的存储结构树、森林、二叉树的转换树的典型应用,第 2 页,一、树的基本概念,基本概念包括：树的定义树的基本术语结点、根、叶、路径、结点度、树的度结点的层次、子结点、父结点有序、无序,第 3 页,树形结构,树形结构是以分支关系来定义的层次结构。在客观世界中树形结构广泛存在，并应用于：人类社会的族谱、家谱、行政区域划分管理；各种社会组织机构；在计算机领域中，用树表示源程序的语法结构；在OS中，文件系统、目录等组织结构也是用树来表示的。,第 4 页,树的定义（逻辑结构
2、）,树是一种数据结构，可用二元组表示为：Tree=（D，R）其中：D 是具有相同特性的数据元素的集合；R 是数据元素间逻辑关系的集合，且满足：在D中存在唯一的称为根的数据元素，没有前趋；D中其余数据元素都有且只有一个前趋；D中所有元素，或有若干个互不相同的后继（子树），或无后继（叶结点）；则称Tree为树。,第 5 页,树的定义（递归定义）,树是一个或多个结点组成的有限集合T，有一个特定结点称为根，其余结点分为m（m0）个互不相交的集合T1，T2，,Tm。且每个集合又是一棵树，它们称为这个根的子树。树是一种递归结构。,第 6 页,树结构举例,书目录 目录树 树结构C1（章）BOOK 1.1(节
3、)1.2 C1 C2 C3 C2 2.1 1.1 1.2 2.1 2.2 2.3 2.11 2.12 2.2 2.1.1 2.1.2 2.3C3,第 7 页,树的表示形式,(1)一般形式(2)嵌套形式(3)凹入形式(4)广义表形式,第 8 页,树的表示(一般形式),A,B,C,D,E,F,K,L,G,H,I,J,M,A,(a),(b),(a)只有根结点的树,(b)一般的树,第 9 页,树的表示(嵌套形式),A,C,G,B,F,E,K,L,M,H,D,J,I,第 10 页,树的表示(缩进形式),A B E,KL,C,D,F,G,H,I,J,M,第 11 页,树的表示(广义表形式),(A(B(E(
4、K,L),F),C(G),D(H(M),I,J),第 12 页,树的基本术语,1层,2层,4层,3层,height=4,A,C,G,B,D,E,F,K,L,H,M,I,J,结点结点的度叶结点分支结点,子女双亲兄弟,祖先子孙结点层次,树的深度树的度森林,第 13 页,二、二叉树及其基本性质,1、定义二叉树是另一种树形结构：Binary_Tree=(D,R)其中:D 是具有相同性质的数据元素的集合;R 是在D上某个两元关系的集合,且满足:D中存在唯一称为根的数据元素,没有前趋;D中其余元素都有且仅有一个前趋;每个结点至多只有两个子树;D中元素,或有两个互不相交后继,或无后继;左、右子树分别又是一棵
5、二叉树（所有子树均有左右之分）。,第 14 页,二叉树的五种基本形态,（a）（b）（c）,（d）（e）,O 空树,O 仅有根结点,右子树为空的二叉树,左子树为空的二叉树,左、右子树非空的二叉树,第 15 页,二叉树与树的区别,表达形式（对3个结点）普通树 二叉树（a）（b）（c）（d）（e）,O,O,O,O,O,O,有两种不同形式,（a）,（b）,O,O,O,O,O,O,O,O,O,O,O,O,O,O,O,有五种不同形式,第 16 页,二叉树与树的区别（二）,二叉树的子树有顺序关系，分左子树和右子树，而树则无此区分；二叉树的分支度一定为0、1或2，而树的度可大于2,第 17 页,2、二叉树的性
6、质,性质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。,第 18 页,二叉树的性质（二）,性质2 深度为 k 的二叉树至多有 2 k-1个结点(k 1)。证明：由性质1可见，深度为k的二叉树的最大结点数为,第 19 页,性质3 对任何一棵二叉树T,如果其叶结点数为 n0,度为2的结点
7、数为 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,二叉树的性质（三）,第 20 页,性质4 具有 n 个结点的二叉树，其深度至少为log2n 1 证明略。,二叉树的性质（四）,第 21 页,定义1 满二叉树(Full Binary Tree)一棵深度为k且有2 k-1个结点的二叉树称为满二叉树。（a）满二叉树（b）非满二叉树,两种特殊形态的二叉树,第 22 页,定义2 完全二叉树(Complete Binary
8、 Tree)若设二叉树的高度为h，则共有h层。除第 h 层外，其它各层(0 h-1)的结点数都达到最大个数，第 h 层从右向左连续缺若干结点，这就是完全二叉树。（a）完全二叉树（b）非完全二叉树,两种特殊形态的二叉树,第 23 页,性质5 具有 n(n 0)个结点的完全二叉树的深度为log2n 1 证明：设完全二叉树的深度为 h，则根据性质2和完全二叉树的定义有2h1-1 n 2h-1或 2h1 n 2h取对数 h1 log2n h，又h是整数，因此有 h=log2n 1,二叉树的性质（五）,第 24 页,二叉树的性质（六）,性质6 在编号的完全二叉树中，各结点的编号之间关系为：编号为i 的结
9、点，若存在左孩子，则其编号为2i;若存在右孩子，则其编号为2i+1;若存在父结点，则其编号为i/2。这是一个重要的性质，在后面讨论的顺序存储结构和排序算法中都要用到。例：已知完全二叉树有100个结点，则该二叉树有多少叶子结点？,第 25 页,3、二叉树的存储结构,顺序存储（一维数组）链式存储结构二叉链表三叉链表,第 26 页,顺序存储法（一维数组）,若一个二叉树的树高为n，则对一个满二叉树，其结点个数为2n-1。存入时按从左到右，从低阶层到高阶层的顺序存放。,A B C D E F G,0 1 2 3 4 5 6 7,A,B,C,D,E,F,G,0 1 2 3 4 5 6 7,A B E,A,
10、B,E,满树,非满树,第 27 页,顺序存储（一维数组）,存储描述为：#define MAXSIZE 100；typedef TElemType SBTreeMAXSIZE；SBTree bt；适用于满二叉树。,a1 a2 a3 a4.an,第 28 页,二叉链表存储结构,data,leftp,rightp,左指针 数据 右指针,A,B,C,D,E,F,G,A,B,D,C,E,F,G,特点:找子易,找父难.,第 29 页,三叉链表存储结构,parent,data,rightp,左指针 数据 父结点 右指针,A,B,C,D,E,F,G,C,特点:找子、找父都易。,leftp,A,B,D,E,G,
11、F,第 30 页,4.二叉树的遍历,遍历（Traversing）是树形结构的一种重要运算，即按一定的次序系统地访问树中的所有结点，使每个结点只被访问一次。遍历二叉树的实质：把二叉树的结点进行线性排列的过程。访问结点：指对结点进行的各种操作，如查找结点数据域的内容，或输出它的值，或找结点的位置等。,第 31 页,二叉树的遍历,遍历的方法很多，常用的有：前序法（PreOrder）中序法（InOrder）后序法（PostOrder）,第 32 页,前序法（PreOrder）,方法描述：访问根结点先序遍历左子树先序遍历右子树即：,ABDEGCFHI,根,左子树,右子树,第 33 页,中序法（InOrd
12、er）,方法描述：中序遍历左子树访问根结点中序遍历右子树 即：,DBGEACHFI,根,左子树,右子树,第 34 页,后序法（PostOrder）,方法描述：后序遍历左子树后序遍历右子树访问根结点即：,DGEBHIFCA,根,左子数,右子树,第 35 页,二叉树遍历算法,二叉树遍历方法分为：递归算法非递归算法递归算法和非递归算法中又分：前序法中序法后序法,第 36 页,二叉树遍历算法（递归算法）,二叉链表的C语言描述：struct tnode chardata；struct tnode*lchild，*rchild；typedef struct tnode TNODE;,第 37 页,二叉树遍
13、历算法（递归、前序法程序）,void preorder_t(TNODE*root)if(root!=NULL)printf(“%d n”,root-data);proorder_t(root-lc);proorder_t(root-rc);前序遍历二叉树的序列为：A B C D E F,A,B,C,D,E,F,第 38 页,二叉树遍历算法（递归、前序法程序验证）,打印A取A.左子(B)打印B取B.左子(C)打印C取C.左子(空)取C.右子(空)取B.右子(D)打印D取D.左子(E)打印E取E.左子(空)取E.右子(空)取D.右子(F)打印F取F.左子(空)取F.右子(空)取A.右子(空)结束,
14、A,B,C,D,E,F,A,B,C,D,E,F,A B C D E F,第 39 页,二叉树遍历算法（非递归算法-前序法）,算法步骤:step1 初始化,置栈为空(top=-1),工作变量p指向root;step2 p非空(p!=NULL)或栈非空(top!=-1)循环;step3 p非空循环;访问p(打印p-data);step4 当前元素进栈,p取p-lc(进左子树);执行step3；step5 p为空，栈非空，则出栈，p取p-rc(进右子树),返回step2.,第 40 页,二叉树遍历算法（非递归算法-前序法程序）,#define N mvoid preorder_t(TNODE*roo
15、t)TNODE*p,*stackN;int top=-1;/初始化，初始栈为空，p指向树根 p=root;while(p!=NULL)|(top!=-1)while(P!=NULL)printf(“%dn”,p-data);/访问根结点 top+;stacktop=p;/进栈 p=p-lc;/进左子树 if(top!=-1)p=stacktop;top-;/出栈 p=p-rc;/进右子树,第 41 页,二叉树遍历算法（非递归、前序法程序验证）,打印AA进栈，取A.左子(B)打印BB进栈，取B.左子(C)打印 CC 进栈，取C.左子(空)C 退栈，取C.右子(空)B 退栈，取 B.右子(D)打印
16、 D D进栈，取D.左子(E)打印EE进栈，取E.左子(空)E退栈，取E.右子(空)D退栈，取D.右子(F)打印FF进栈，取F.左子(空)F退栈，取F.右子(空)A退栈，取A.右子(空)结束,F,E,D,C,B,A,A,B,C,D,E,F,A B C D E F,第 42 页,建立二叉树(法1：按先序序列建立二叉树),#include#include struct tnode char data;struct tnode*lchild,*rchild;typedef struct tnode*TNODE;void Create_t(TNODE bt)char ch;printf(“input
17、ch:”);scanf(“%c”,ABC.DE.F.,第 43 页,建立二叉树(续）,void preOrder_t(struct tnode*root)if(root!=NULL)printf(“%d n”,root-data);preOrder_t(root-lchild);preOrder_t(root-rchild);main()TNODE root;Create_t(root);preOrder_t(root);,第 44 页,建立二叉树(法2：利用二叉树的性质6),二叉树的性质6：在编号的完全二叉树中，编号为i的结点如果存在左孩子，则其编号为2i；若其存在右孩子，则其编号为2i+1
18、；若存在父结点，则其编号为i/2取整算法思路：对任意二叉树，先按满二叉树对其进行编号，算法中使用一个辅助向量s来存放指向树结点的指针。如si中存放编号为i的结点的指针，即为该结点的地址。,第 45 页,建立二叉树(法2：利用二叉树的性质6),当结点编号i=1时，所产生的结点为根结点，同时将指向该结点的指针存入s1。当结点编号i1时，产生一个新的结点后，也要将指向该结点的指针存入si，由性质6知：j=i/2为它的双亲结点编号。若i为偶数，则它是双亲结点的左孩子，即让sj-lch=si；若i为奇数，则它是双亲结点的右孩子，即让sj-rch=si。这样就将新输入的结点逐一与其双亲结点相连，生成二叉树
19、。,第 46 页,struct Tnode char data;struct tnode*lchild,*rchild;typedef struct Tnode BiTnode;BiTnode*Creat()int i,x;BiTnode*q,*t,*s20；/q指向新生成的结点 printf(“i,x=”);scanf(“%d%d”,/返回根结点,建立二叉树(法2：利用二叉树的性质6),第 47 页,5.树的实现(存储结构),数组实现方法（双亲表示法）链表实现方式（孩子表示法）二叉链表实现方式（孩子兄弟表示法）,第 48 页,双亲表示法举例,1,2,3,4,5,6,7,8,9,结点序号,1
20、2 3 4 5 6 7 8 9,1 2 3 4 5 6 7 8 9,0 1 1 2 2 3 5 5 5,方法特点：找根容易，找子结点难，要遍历整个数组。,第 49 页,双亲表示法描述,用数组存储树的结点信息，在每个结点中附设一个指示器指示其双亲结点在数组中的位置,也称为数组实现方法。结构描述：#define MAXSIZE 100 typedef struct PTNode TElemType data；int parent；PTNode；typedef struc PTNode nodesMAXSIZE；int n；Ptree；,第 50 页,孩子表示法举例,1,2,3,4,5,6,7,8,
21、9,123456789,2,3,4,5,6,7,8,9,方法特点:便于实现对孩子的操作,却不便于对父亲的操作。,第 51 页,孩子表示法描述,把每个结点的孩子结点排列起来，组成一个线性表，且以单链表作为存储结构，则n个结点有n个孩子链表。结构描述为：typedef struct CTNode typedef struct int child；CTBox nodesMAXSIZE；struct CTNode*next：int n，r；*Childptr；Ctree；typedef struct TElemType data；Childptr firstchild；CTBox；,第 52 页,孩子
22、兄弟表示法举例,1,2,3,4,5,6,7,8,9,1,2,3,7,4,5,6,8,9,方法特点:这种存储结构便于实现各种树的操作。,第 53 页,孩子兄弟表示法描述,二叉链表实现方式（孩子兄弟表示法）以二叉链表作为树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。结构描述为：typedefstruct CSNode ElemType data；struct CSNode*firstchild，*netsibling；CSNode，*CSTree；,第 54 页,6.树、森林与二叉树的转换,由于二叉树的存储结构比较简单，处理起来也比较方便，所以有时需要把复杂的树
23、，转换为简单的二叉树后再作处理。树转换成二叉树森林转换成二叉树,第 55 页,树转换成二叉树,操作算法：保留一个结点的最左子结点；抹掉其余兄弟结点与上级结点的连线；将兄弟结点连在一起；以根为轴，顺时针旋转一个角度。举例：,第 56 页,森林转换成二叉树,操作算法：将森林中每棵树的树根连接起来；将每棵树转换成对应的二叉树；以森林中第一棵树的根为轴顺时针旋转一个角度。举例,第 57 页,将二叉树还原成树,将二叉树还原成树的操作步骤为：step1 若某结点是其双亲的左子，则把该结点的右子、右子的右子、,都与该结点的双亲结点用线连起来；step2 删除原二叉树中所有的双亲结点与右子结点的连线；step
24、3 整理1、2两步所得到的树或森林，使之结构层次分明。,第 58 页,举例,第 59 页,7.树的典型应用,Huffman树的定义构造Huffman树Huffman编码Huffman编码的译码,Huffman(哈夫曼）树及其应用,第 60 页,Huffman树的定义,Huffman树也称为最优树，是一类带权路径最短的二叉树。树的带权路径长度定义为：,其中：n 是树中叶结点的个数 wi 是第i个结点的权值 li 是第i个结点的路径长度,第 61 页,Huffman树举例,以下有三棵树：,（a）,（b）,（c）,a,b,c,d,a,b,c,d,a,c,b,d,7,7,7,5,5,5,2,2,2,4
25、,4,4,WPLa=7x2+5x2+2x2+4x2=36,WPLb=7x3+5x3+2x1+4x2=46,WPLc=7x1+5x2+2x3+4x3=35,事实证明按哈夫曼树构造二叉树，可得到很好的特性，应用于实际问题，可提高处理效率。,第 62 页,应用举例,由统计规律可知，考试成绩的分布符合正态分布：,-1,1,0,分数 059 60 69 70 79 80 89 90 100,比例数 0.05 0.15 0.40 0.3 0.10,根据正态分布规律，在6090之间的分数占85%，而不及格和优秀是少数。,第 63 页,将百分制转换成五分制,判定树比较：,a60?,a70?,a80?,a90?
26、,不及格,及格,中等,良好,优秀,Y,Y,Y,Y,N,N,N,N,a80?,a70?,a90?,a60?,不及格,优秀,良好,中等,中等,及格,不及格,Y,Y,Y,N,N,N,N,Y,Y,(A),(B),若输入1万个数据，按A的判定过程进行操作，约需比较3.2万次，而按B比较,则仅需2.2万次。,第 64 页,构造Huffman树,构造Huffman树算法步骤：Step1 将n个带权值wi（in）的结点构成n棵二叉树的集合T=T1，T2，Tn，每棵二叉树只有一个根结点。Step2 在T中选取两个权值最小的结点作为左右子树，构成一个新的二叉树，其根结点的权值取左右子树权值之和；Step3 在T中
27、删除这两棵树，将新构成的树加入到T中；Step4 重复2）、3）步的操作，直到T中只含一棵树为止，该树就是Huffman树。,第 65 页,构造Huffman树举例,以权值分别为7，5，2，4的结点a、b、c、d构造Huffman树。T=a b c d,（d）T=T1,（c）T=a T2,（b）T=a b T3,（a）T=a b c d,示例,第 66 页,Huffman编码,编码：用二进制数的不同组合来表示字符的方法。前缀编码：一种非等长度的编码(任一个字符的编码都不是另一个字符编码的前缀)。,a,0,b,0,1,c,d,0,1,1,编码：a（0）b（10）c（110）d（111）,方法约定
28、：1）左分支为02）右分支为13）由根到叶路径上字符组成的二进制串就是该叶结点的编码。,Huffman编码：一种非等长度的编码。以给定权值的结点构造Huffman树，按二进制前缀编码的方式构成的编码为Huffman编码。,第 67 页,Huffman编码举例,在某系统的通信联络中可能出现8种字符，其频率分别为0.05、0.29、0.07、0.08、0.14、0.23、0.03、0.11，设权值分别为5，29，7，8，14，23，3，11，n=8，其Huffman树为：,第 68 页,Huffman编码存储结构,由于Huffman树中没有度为1的结点，则n个叶结点的Huffman树共有2n-1个结点。例如，4个结点的Huffman树，共有7个结点。因此可以用长度为2n-1的一维数组存放。求Huffman编码：从根到叶的编码。因此要知道每个结点的父结点。,
