《树和二叉树.ppt》由会员分享，可在线阅读，更多相关《树和二叉树.ppt（83页珍藏版）》请在三一办公上搜索。
1、第五章 树和二叉树,5.1树与树林5.2树和树林的存储表示 5.3二 叉 树 5.4二叉树的存储表示5.5哈夫曼算法及其应用,线性结构和非线性结构。树形结构是以分支关系定义的层次结构，在现实世界中广泛存在，在计算机领域中也有广泛应用。本章重点讨论二叉树的存储结构及其各种操作，并研究树和森林与二叉树之间的转换关系。,5.1 树与树林,5.1.1 树的定义 5.1.2 基本术语 5.1.3 树林 5.1.4 树的基本运算 5.1.5 树的周游 5.1.6 树林的周游,5.1.1 树的定义,树(Tree)的例子：一个家族。A有子女B,C；B和 C分别有子女D,E,F和G,H;E有 子女I,J。T=(
2、N,R),其中 N=A,B,C,D,E,F,G,H,I,J R=A,B,A,C,B,D,B,E,B,F,C,G,C,H,E,I,E,J,树的表示方法：,(c)凹入表,（a）树形表示,A,B,C,D,E,F,I,J,G,H,(A(B(D)(E(I)(J)(C(G)(H)(d)嵌套括号表示法,C,D,E,I,J,F,G,H,A,B,(b)文氏图,树(Tree)：是包括n(n=0)个结点的有限集T。当T非空时，满足：（1）有且仅有一个特别标出的称为根的 结点；（2）除根结点外，其余结点可分为m（m=0）个互不相交非空的有限集T1,T2,Tm,其中 每一个集合本身又是一棵树，称为根的子树(Subtre
3、e)。,树的递归定义：,空树：不包括任何结点的树。,树结构的特点：（1）树的根的结点没前驱结点，除了根结点之外 的所有结点都有且只有一个前驱结点；（2）树的结点可以有零个或多个后继结点。树结构描述的是层次关系。,5.1.2 基本术语,(a)树t(b)树t 图5.2 树t和树t,父结点，子结点，边 若结点y是结点x的一棵子树的根，则x称作y的父结点（或父母）；y称作x的子结点（或子女）；有序对称作从x到y的边。例如树t中，C是E的父结点，E是C的子结点，是从C到E的边（它对应着图中的有向线段CE）。,兄弟结点具有同一父母的结点彼此称作兄弟。树t中B，C，D互为兄弟，F，G互为兄弟，等等。注意，E
4、和F并不是兄弟。,祖先，子孙若结点y在以结点x为根的一个子树（或树）中，且yx，则称x是y的祖先，y是x的子孙。例如树t中，A是其它各结点的祖先；C是E，H，I，J的祖先。,路径，路径长度如果x是y的一个祖先，又有xx0，x1，xny，满足xi（i0，1，n-1）为xi+1的父结点，则称x0，x1，xn为从x到y的一条路径。n称为这条路径的长度。路径中相邻的两个结点可以表示成一条边。例如树t中A，C，E，I，J是从A到J的一条路径，其长度为4。,结点的层数规定根的层数为0，其余结点的层数等于其父母结点的层数加1。例如t中，0层的结点是A，1层的结点有B，C，D，4层的结点是J。,树的深度或高度
5、树中结点的最大层数称为树的深度或树的高度。例如树t中，树的深度为4。,结点的度数、树的度数结点的子女个数叫作结点的度数。树中度数最大的结点的度数叫作树的度数。例如t中A，C，E，J的度数分别为3，1，2，0；t的度数为3,树叶、分支结点度数为0的结点称作树叶或终端结点；度数大于0的结点称作分支结点或非终端结点。例如树t中B，F，G，H，J都是树叶，其余结点都是分支结点。,无序树、有序树对子树的次序不加区别的树叫作无序树。对子树之间的次序加以区别的树叫作有序树。例如在图5.2中，按无序树的概念t和t是同一棵树，按有序树的概念则是不同的树，本章讨论的树一般是有序树。,结点的次序 在有序树中可以从左
6、到右地规定结点的次序。按从左到右的顺序，我们可以把一个结点的最左边的子结点简称为最左子结点，或直接称为长子，而把长子右边的结点称为次子。例如在t中结点B是结点A的长子，结点C是结点A的次子，是结点B的兄弟。,树林：是m（m=0）棵互不相交的树所组成的集合。就逻辑结构而言，任何一棵树是一个二元组Tree=(root,F),其中root称为树的根结点，F是m（m0）棵子树构成的树林，F=(T1,T2,Tm),其中Ti=(ri,Fi)称作根root的第i棵子树；当m0时，在树根和其子树林之间存在下列关系:RF=|i=1,2,m,m0,5.1.3 树林,5.1.4 树的基本运算,创建一棵空树Tree
7、createTree(Node p,Tree t1,Tree t2,Tree ti)i=1,2,3,判断某棵树是否为空int isNull(Tree t)求树中的根结点，若为空树，则返回一特殊值Node root(Tree t)求某个指定结点的父结点，当指定结点为根时，返回一特殊值Node parent(Node p),求树中某个指定结点的最左子结点，当指定结点为树叶时，返回一特殊值Node leftChild(Node p)求树中某个指定结点的右兄弟结点，当指定结点没有右兄弟时，返回一特殊值Node rightSibling(Node p)树的周游：即按某种方式访问树中的所有结点，并使每个结
8、点恰好被访问一次。,5.1.5 树的周游,1.周游的定义:按某一规律系统的访问树中的所有 结点，并使每个结点恰好被访问一次。2.周游的方法：按深度方向和按宽度方向周游。（I）按深度方向（以右图为例）a.先根次序b.中根次序c.后根次序,a.先根次序(1,2,3,5,8,9,6,10,4,7)（1）访问根结点；（2）从左到右按先根次序周游根结点的每棵子树。b.中根次序(2,1,8,5,9,3,10,6,7,4)（1）按中根次序周游根结点的最左子树；（2）访问根结点；（3）从左到右按中根次序周游根结点的其它各子树。c.后根次序(2,8,9,5,10,6,3,7,4,1)（1）从左到右按后根次序周游
9、根结点的每棵子树;（2）访问根结点。,（II）按宽度方向周游 先访问层数为0的结点，然后从左到右逐个访 问层数为1的结点，依此类推，直到访问完树中 的全部结点。层次序列（1，2，3，4，5，6，7，8，9，10）,1.先根（A,B,C,K,D,E,H,F,J,G)2.后根(B,K,C,A,H,E,J,F,G,D),5.1.6 树林的周游,5.2 树和树林的存储表示,5.2.1 树的存储表示 5.2.2 树林的存储表示 5.2.3 树和树林的其它表示法*,5.2.1 树的存储表示,树的父指针表示法 树的子表表示法 树的长子-兄弟表示法,struct ParTreeNode/*树中结点结构*/Da
10、taTypeinfo;/*结点中的元素*/intparent;/*结点的父结点位置*/;struct ParTree struct ParTreeNode nodelistMAXNUM;/*存放树中的结点*/int n;/*树中结点的个数*/;typedef struct ParTree*PParTree;,树的父指针表示法,用一组连续空间存储树的结点，并附设一个指示器指示其双亲结点的位置。结构类型如下：,优点：a)容易找到父结点及其所有的祖先；b)能找到结点的子女和兄弟；缺点：a)没有表示出结点之间的左右次序；b)找结点的子女和兄弟比较费事。,改进方法：按一种周游次序在数组中存放结点,。常见
11、的一种方法是依次存放树的先根序列，如下图：,(a)(b)图5.5 一棵树的父指针表示,树的子表表示法,结点表中的每一元素又包含一个子表，存放该结点的所有子结点。结点表顺序存放，子表用链接表示。struct EdgeNode/*子表中节点的结构*/intnodeposition;struct EdgeNode*link;struct ChiTreeNode/*结点表中节点的结构*/DataTypeinfo;struct EdgeNode*children;,子表表示的树结构定义如下：struct ChiTree/*树结构*/struct ChiTreeNode nodelistMAXNUM;in
12、troot;/*根结点的位置*/intn;/*结点的个数*/typedef struct ChiTree*PChiTree;,求某个结点的最左子女运算很容易实现，找到结点的全部子女也很容易，但求某个结点的父母和右兄弟实现起来比较费事。另一个缺点是：合并若干个子树构成一个新树时（createTree_chitree操作）也要考虑多个结点表的合并问题，由于这些结点表通常用顺序方式表示，所以合并起来比较麻烦。,1,7,2,3,4,6,8,9,5,图5.6 树的子表表示法,在树的每个结点中，除信息域外，增加指向其最左子女和右兄弟的指针。struct CSNode;/*树中结点结构*/typedef s
13、truct CSNode*PCSNode;/*结点的指针类型*/struct CSNode/*结点结构定义*/DataType info;/*结点中的元素*/PCSNode lchild;/*结点的最左子女的指针*/PCSNode rsibling;/*结点的右兄弟的指针*/;typedef struct CSNode*CSTree;/*树类型定义*/,树的长子-兄弟表示法,t,a,b,d,c,e,h,i,j,f,g,图5.7 树的长子兄弟表法,5.2.2 树林的存储表示,父指针表示法 子表表示法 长子-兄弟表示法,树林的父结点表示方法,1,2,3,5,9,8,6,7,树林的子表表示法,t,A
14、,B,D,C,E,H,J,K,F,G,树林的长子兄弟表示法,5.3 二叉树,5.3.1 二叉树的基本概念 5.3.2 二叉树的性质 5.3.3 二叉树的基本运算 5.3.4 二叉树的周游 5.3.5 树、树林与二叉树的转换,二叉树：它是结点的有限集合，这个集合或者为空集或者由一个根及两棵不相交的分别称作这个根的“左子树”和“右子树”的二叉树组成。它的每一个结点至多有两棵子树，并且子树有左右之分，不能随意颠倒。,5.3.1 二叉树的基本概念,二叉树的基本形态：,左子树,右子树,右子树,左子树,（1）空二叉树,（2）只有一个根结点,（3）有根结点 和左子树,（4）有根结点 和右子树,（5）有根结点
15、 和左，右子树,二叉树不是树的特殊情形，它们是两个概念。树和二叉树之间最主要的差别是：二叉树中结点的子树要区分为左子树和右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。（3）和（4）是两棵不同的二叉树，但作为树，它们是相同的。在二叉树中可定义类似树中的概念。,满二叉树：如果一棵二叉树的任何结点或者是树叶，或者有两棵非空子树，则此二叉树称作“满二叉树”。完全二叉树：如果一棵二叉树至多只有最下面的两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则此二叉树称为“完全二叉树”。完全二叉树不一定是满二叉树。,满二叉树,完全二叉树,扩充二叉树：把原二
16、叉树的结点都变为度数为2的分支结点，也就是说，如果原结点的度数为2，则不变，度数为1，则增加一个分支，度数为0（树叶）增加两个分支。,在扩充的二叉树里，新增加的外部结点的个数比原来的内部结点个数多1。“外部路径长度”E：在扩充的二叉树里从根到每个外部结点的路径长度之和。“内部路径长度”I：在扩充的二叉树里从根到每个内部结点的路径长度之和。E=I+2n 其中，n是内部结点的个数。,证明：当n=1时，I=0,E=2,此等式成立。设有n个内部结点的扩充二叉树，下式成立。En=In+2n(1)对于 n+1 个内部结点的扩充二叉树，去掉一个 作为原来二叉树路径长度为K的内部结点，内部路径长度变为：In=
17、In+1-K(2)外部路径长度变为：En=En+1-2(K+1)+K=En+1-K-2 即：En+1=En+K+2 En+1=(In+2n)+K+2=(In+1-K)+2n+K+2=In+1+2(n+1)代入（1）代入（2）,a,b,c,e,e,f,性质1.在非空二叉树的第i层上至多有2i个结点（i0）。归纳：i=0,结点数=1=20.假设对于j(0j i),结点数至多有2j.对于i=j+1,结点数至多为 2*2j=2j+1.性质2.深度为k的二叉树至多有2k+1-1个结点（k 0）。K k M=mi 2i=2k+1-1 i=0 i=0 20+21+22+2k,5.3.2 二叉树的性质,性质3
18、.对任何一棵非空二叉树T，如果叶结点数 为n0，度为2的结点数为n2，则n0=n2+1。n0+n1+n2=所有 结点的度数和+1=n1+2*n2+1 性质4.具有n个结点的完全二叉树的深度k为log2n.n=20+21+22+2k-1+mk=2k-1+mk 2k-1n 2k+1-1 2k n 2k+1 k log2n k+1 k=log2n,性质5.如果对一棵有n个结点的完全二叉树按层次次序 从1开始编号，则对任一结点i（1 in)，有：1）i=1，序号结点i是根；i1,其双亲结点是 i/2。2）2i n，序号为i的结点的左子女结点的序号为2i；2in,序号为i的结点无左子女。3）2i+1 n
19、，序号为i的结点的右子女结点的序号 为2i+1;2i+1 n,序号为i的结点无右子女。,性质5的证明：对于（2）和（3）当i=1时，2i=2 n，左子女结点的序号为2。2i+1=3 n，右子女结点的序号为3。假设对于序号为j的结点，命题成立。对于i=j+1，其左子女结点的序号等于j的右子女结点的序号加1，即：2j+1+1=2(j+1)其右子女结点的序号等于：2(j+1)+1根据（2）和（3），知的父结点为i/2.完全二叉树的层次序列，反映了它的结构。,1,2,3,j,j+1,2j 2j+1 2(j+1)2(j+1)+1,5.3.3 二叉树的基本运算,创建一棵空二叉树；判断某棵二叉树是否为空；求
20、二叉树的根结点，若为空，则返回一特殊值；求二叉树中某个指定结点的父结点，当指定结点为根时，返回一特殊值；求二叉树中某个指定结点的左子女结点，当指定结点没有左子女时，返回一特殊值；求二叉树中某个指定结点的右子女结点，当指定结点没有右子女时，返回一特殊值；二叉树的周游。,5.3.4 二叉树的周游,二叉树的周游(Traversing Binary Tree)：按某条搜索路径访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。三种方式：先根次序(DLR)对称序(LDR)后根次序(LRD),D,L,R,A,B,D,C,E,F,I,H,G,图5.15 二叉树,先根次序A B D C E G F
21、H I 后根次序D B G E H I F C A 对称序（中根次序）D B A E G C H F I,对右图进行先根、后根和中根次序周游得到如下的结点序列：先根：-ab+cd 前缀表示 后根：ab-cd+后缀表示(波兰表示法)对称序：a-b c+d 中缀表示,-,+,a,b,c,d,图 5.16 表达式的二叉树表示,二叉树的周游算法,递归算法先根次序中根次序后根次序二.非递归算法(用自定义的栈来代替系统的栈)先根次序中根次序后根次序 1 2,5.3.5 树、树林与二叉树的转换,1.树、树林转换为二叉树执行步骤：（1）在所有相邻的兄弟结点之间连一条线；（2）对每个非终端结点，只保留它到其最左
22、子女的 连线，删去它与其它子女的连线；（3）以根结点为轴心，将整棵树进行旋转。,树、树林 二叉树,A,B,C,K,D,E,F,G,H,J,图5.20 树林转换为二叉树,2.二叉树转换为树、树林,执行步骤：（1）若某结点是其父母的左子女，则把该结点 的右子女，右子女的右子女，,都与 该结点的父母用线连接起来；（2）去掉原二叉树中所有父母到右子女的连线。,A,B,D,C,E,K,H,F,J,G,图 5.22 二叉树转换为树林,5.4 二叉树的存储表示,5.4.1 顺序表示 5.4.2 链接表示 5.4.3 二叉树的生成 5.4.4 线索二叉树*,用一组地址连续的存储单元按层次次序依次存储完全二叉树
23、的结点。完全二叉树的层次序列反映了它的层次结构。,5.4.1 顺序表示,A,B,C,G,F,E,D,H,I,J,A B C D E F G H I J,下标 0 1 2 3 4 5 6 7 8 9,对于一般二叉树，则应将其每个结点与完全二叉树上的结点相对照，存储在一维数组的相应分量中。,图514 一般二叉树及其顺序表示,采用顺序表示，类型声明如下：struct SeqBTree/*顺序树类型定义*/DataType nodelistMAXNODE;int n;/*改造成完全二叉树后，结点的个数*/；typedef struct SeqBTree*PSeqBTree;,5.4.2 链接表示,二叉
24、树的链接表示是指用一个链表来存储一棵二叉树，二叉树中的每一个结点用链表中的一个链结点来存储，最常用的链接表示方式是左-右指针表示法（llink-rlink表示法，也称做二叉链表），这种表示法在每个链结点中除存储结点本身的数据外，再设置两个指针字段：llink和rlink，分别存放结点的左子女和右子女所在链结点的存储地址，当结点的某个子女为空时，则相应的指针为空指针。,struct BinTreeNode;/*二叉树中结点*/typedef struct BinTreeNode*PBinTreeNode;/*结点的指针类型*/struct BinTreeNode DataType info;/*
25、数据域*/PBinTreeNode llink;/*指向左子女*/PBinTreeNode rlink;/*指向右子女*/;typedef struct BinTreeNode*BinTree;typedef BinTree*PBinTree;,A,B,D,C,E,F,I,H,G,t,A,B,C,E,F,I,H,G,D,图5.15 二叉树的二叉链表表示,t,A,B,D,C,E,F,I,H,G,图5.15 三叉链表表示,5.4.3 二叉树的生成,周游是二叉树各种操作的基础，可以在周游过程中进行各种操作，如可以在周游过程中生成结点，从而建立一棵二叉树。例：读入字符序列：ABDCEGFHI建立图5.
26、13所示的二叉树，其中，表示空结点。算法5.5 按先根序列创建二叉树,t,A,B,C,E,F,I,H,G,D,图5.15 二叉树的二叉链表表示,5.4.4 线索二叉树*,保存遍历过程中得到的信息以供某些操作使用（1增加两个指针（2利用结构中的空链域，并设立标志。线索：指向结点前驱或后继的指针。线索二叉树：加上线索的二叉树。线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程。按对称序线索化二叉树:按对称序周游二叉树，周游到那个结点对那个结点加线索。按对称序周游对称序穿线树:沿线索周游。,struct ThrTreeNode;typedef struct ThrTreeNode*PThrTre
27、eNode;struct ThrTreeNode/*结点类型*/DataType info;PThrTreeNode llink,rlink;int ltag,rtag;typedef struct ThrTreeNode*ThrTree,/*树类型*/typedef ThrTree*PThrTree;/*类型的指针类型*/,Struct SeqStack/*栈元素的类型为PThrTreeNode*/PThrTreeNode sMAXNODE;int t;typedef Struct SeqStack*PSeqStack;算法5.6 按对称序线索化二叉树算法5.7 按对称序周游对称序穿线树,对
28、称序穿线树里的线索总是指向二叉树中更高层的结点，也就是说是“向上”指的(如下图）。利用该“向上”指的线索我们可以在对称序穿线树里找出指定结点在先根下的后继结点和后根下的前驱结点。,5.5 哈夫曼算法及其应用,5.5.1 哈夫曼树 5.5.2 哈夫曼(Huffman)算法 5.5.3 哈夫曼编码,5.5.1 哈夫曼树,扩充二叉树的外部路径长度：其中：li为从根到第i个外部结点的路径长度，m为外部结点的个数,扩充二叉树的带权的外部路径长度 其中：wi是第i个外部结点的权值，li为从根到第i个外部结点的路径长度，m为外部结点的个数。,哈夫曼树 假设有一组（无序）实数w1,w2,w3,wm，现要构造一
29、棵以wi（i=1,2,，m）为权的m个外部结点的扩充的二叉树，使得带权的外部路径长度WPL最小。满足这一要求的扩充二叉树就称为哈夫曼树或最优二叉树。例如：2,3,4,11,11,4,2,3,2,3,4,11,2,11,3,4,（1）由给定的m个权值w1,w2,wm构造成m棵二叉树集F=T1,T2,Tm，其中每一棵二叉树Ti中只有一个带权为wi的根结点，且根结点的权值为wi；（2）在F中选取两棵权值最小的树作为左右子树以构造一棵新的二叉树，且新二叉树的根结点的权值为其左右子树根结点权值之和；（3）在F中删除这两棵树，同时将新得到的二叉树加入F中；（4）重复（2）和（3），直到F中只含一棵树为止。
30、,5.5.2 哈夫曼算法,2,3,4,11,2,3,4,11,5,2,3,9,4,20,11,哈夫曼(huffman)算法的实现 存储结构：struct HtNode/*哈夫曼树结点的结构*/int ww;int parent,llink,rlink;struct HtTree/*哈夫曼树定义*/struct HtNode htMAXNODE;int root;/*哈夫曼树根在数组中的下标*/;typedef struct HtTree*PHtTree;,设 d=d1,d2,dn w=w1,w2,wn d为要编码的字符集合，w为d中各种字符出现的频率。要求：（1）编码总长最短；（2）若di d
31、j,di编码不是dj编码的前缀。,5.5.3 哈夫曼编码,用构造哈夫曼树以完成哈夫曼编码：把d1,d2,dn 作为外部结点，把w1,w2,.,wn作为外部结点的权，构造哈夫曼树。在哈夫曼树中把从每个结点引向其左子女的边上标上0；把从每个结点引向其右子女的边上标上1。从根结点到叶子结点的路径上的数字拼接起来就是这个叶子结点字符的编码。,例：d=a,b,c,d,e w=50,35,25,20,30,50,35,25,20,30,a,b,c,d,e,25,20,c,d,45,30,e,35,b,65,50,a,95,160,0,1,0,1,0,1,0,1,a:00 b:10 c:010d:011 e:11,小 结,树、树林、二叉树的一些基本概念和术语；二叉链表存储结构树、二叉树的周游哈夫曼树的构造方法及应用,
