第五树和二叉树-ppt课件

1、5.1树与树林5.2树和树林的存储表示 5.3二 叉 树 5.4二叉树的存储表示5.5哈夫曼算法及其运用线性构造和非线性构造。 树形构造是以分支关系定义的层次构造，在现实世界中广泛存在，在计算机领域中也有广泛运用。 本章重点讨论二叉树的存储构造及其各种操作，并研讨树和森林与二叉树之间的转换关系。 5.1.1 5.1.1 树的定义树的定义 5.1.2 5.1.2 根本术语根本术语 5.1.3 5.1.3 树林树林 5.1.4 5.1.4 树的根本运算树的根本运算 5.1.5 5.1.5 树的周游树的周游 5.1.6 5.1.6 树林的周游树林的周游树树(Tree)的例子：一个家族。的例子：一个家

2、族。A有子女有子女B,C； B和和 C分别有子女分别有子女D,E,F和和G,H;E有有 子女子女I , J。 T=(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树形表示ABCDEFIJGH(A(B(D)(E(I)(J)(C(G)(H)(d) 嵌套括号表示法CDEIJFGHAB(b) 文氏图 树树(Tree)：是包括：是包括n(n=0)个结点的有限集个结点的有限集T。当。当T非空时，满足：非空时，满足：1有且仅有一个特别标出的

3、称为根的有且仅有一个特别标出的称为根的 结点；结点；2除根结点外，其他结点可分为除根结点外，其他结点可分为mm=0 个互不相交非空的有限集个互不相交非空的有限集T1, T2, , Tm, 其中其中 每一个集合本身又是一棵树，称为根的子树每一个集合本身又是一棵树，称为根的子树 (Subtree)。树的递归定义：树的递归定义：空树：不包括任何结点的树。空树：不包括任何结点的树。树构造的特点：树构造的特点：1树的根的结点没前驱结点，除了根结树的根的结点没前驱结点，除了根结点之外点之外 的一切结点都有且只需一个前驱结点；的一切结点都有且只需一个前驱结点；2树的结点可以有零个或多个后继结点。树的结点可以

4、有零个或多个后继结点。 树构造描画的是层次关系。树构造描画的是层次关系。 (a) 树t (b) 树t 图5.2 树t和树t 父结点，子结点，边父结点，子结点，边 假设结点假设结点y是结点是结点x的一棵子树的根，那么的一棵子树的根，那么x称作称作y的的父结点或父母；父结点或父母；y称作称作x的子结点或子女；有的子结点或子女；有序对序对称作从称作从x到到y的边。的边。例如树例如树t中，中，C是是E的父结点，的父结点，E是是C的子结点，的子结点，是从是从C到到E的边它对应着图中的有向线段的边它对应着图中的有向线段CE。 兄弟结点兄弟结点具有同一父母的结点彼此称作兄弟。具有同一父母的结点彼此称作兄弟。

5、树树t中中B，C，D互为兄弟，互为兄弟，F，G互为兄弟，等等。留互为兄弟，等等。留意，意，E和和F并不是兄弟。并不是兄弟。 祖先，子孙祖先，子孙假设结点假设结点y在以结点在以结点x为根的一个子树或树中，为根的一个子树或树中，且且yx，那么称，那么称x是是y的祖先，的祖先，y是是x的子孙。的子孙。例如树例如树t中，中，A是其它各结点的祖先；是其它各结点的祖先；C是是E，H，I，J的祖先。的祖先。 途径，途径长度途径，途径长度假设假设x是是y的一个祖先，又有的一个祖先，又有xx0，x1，xny，满足满足xii0，1，n-1为为xi+1的父结点，那么称的父结点，那么称x0，x1，xn为从为从x到到y

6、的一条途径。的一条途径。n称为这条途称为这条途径的长度。途径中相邻的两个结点可以表示成一条边。径的长度。途径中相邻的两个结点可以表示成一条边。 例如树例如树t中中A，C，E，I，J是从是从A到到J的一条途径，其的一条途径，其长度为长度为4。 结点的层数结点的层数规定根的层数为规定根的层数为0，其他结点的层数等于其父母结点，其他结点的层数等于其父母结点的层数加的层数加1。例如例如t中，中，0层的结点是层的结点是A，1层的结点有层的结点有B，C，D，4层的结点是层的结点是J。 树的深度或高度树的深度或高度树中结点的最大层数称为树的深度或树的高度。树中结点的最大层数称为树的深度或树的高度。 例如树例

7、如树t中，树的深度为中，树的深度为4。 结点的度数、树的度数结点的度数、树的度数结点的子女个数叫作结点的度数。树中度数最大的结点的子女个数叫作结点的度数。树中度数最大的结点的度数叫作树的度数。结点的度数叫作树的度数。例如例如t中中A，C，E，J的度数分别为的度数分别为3，1，2，0；t的的度数为度数为3 树叶、分支结点树叶、分支结点度数为度数为0的结点称作树叶或终端结点；度数大于的结点称作树叶或终端结点；度数大于0的的结点称作分支结点或非终端结点。结点称作分支结点或非终端结点。例如树例如树t中中B，F，G，H，J都是树叶，其他结点都是都是树叶，其他结点都是分支结点。分支结点。 无序树、有序树无

8、序树、有序树对子树的次序不加区别的树叫作无序树。对子树之对子树的次序不加区别的树叫作无序树。对子树之间的次序加以区别的树叫作有序树。间的次序加以区别的树叫作有序树。例如在图例如在图5.2中，按无序树的概念中，按无序树的概念t和和t是同一棵树，是同一棵树，按有序树的概念那么是不同的树，本章讨论的树普通按有序树的概念那么是不同的树，本章讨论的树普通是有序树。是有序树。 结点的次序结点的次序 在有序树中可以从左到右地规定结点的次序。按从在有序树中可以从左到右地规定结点的次序。按从左到右的顺序，我们可以把一个结点的最左边的子结左到右的顺序，我们可以把一个结点的最左边的子结点简称为最左子结点，或直接称为

9、长子，而把长子右点简称为最左子结点，或直接称为长子，而把长子右边的结点称为次子。边的结点称为次子。例如在例如在t t中结点中结点B B是结点是结点A A的长子，结点的长子，结点C C是结点是结点A A的次的次子，是结点子，是结点B B的兄弟。的兄弟。 树林：是树林：是mm=0棵互不相交的树所组成棵互不相交的树所组成的集合。的集合。就逻辑构造而言，任何一棵树是一个二元组就逻辑构造而言，任何一棵树是一个二元组Tree=(root,F) , 其中其中root称为树的根结点，称为树的根结点，F是是mm0棵子树构成的树林，棵子树构成的树林，F=(T1, T2,Tm), 其中其中Ti=(ri,Fi)称作根

10、称作根root的第的第i棵子棵子树；当树；当m0时，在树根和其子树林之间存在以时，在树根和其子树林之间存在以下关系下关系: RF= | i=1,2,m, m0创建一棵空树Tree 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 ) 求树中某个指定结点的最左子结点，当指定结点为树叶时，

11、前往一特殊值Node leftChild ( Node p ) 求树中某个指定结点的右兄弟结点，当指定结点没有右兄弟时，前往一特殊值Node rightSibling ( Node p ) 树的周游：即按某种方式访问树中的一切结点，并使每个结点恰好被访问一次。1. 周游的定义:按某一规律系统的访问树中的一切 结点，并使每个结点恰好被访问一次。2. 周游的方法：按深度方向和按宽度方向周游。 I按深度方向以右图为例a. 先根次序b. 中根次序c. 后根次序a. 先根次序 (1,2,3,5,8,9,6,10,4,7) 1 访问根结点； 2从左到右按先根次序周游根结点的每棵子树。 b. 中根次序 (2

12、,1,8,5,9,3,10,6,7,4) 1按中根次序周游根结点的最左子树； 2访问根结点； 3从左到右按中根次序周游根结点的其它各子树。c. 后根次序 (2,8,9,5,10,6,3,7,4,1) 1从左到右按后根次序周游根结点的每棵子树; 2访问根结点。II按宽度方向周游 先访问层数为0的结点，然后从左到右逐个访 问层数为1的结点，依此类推，直到访问完树中 的全部结点。 层次序列1，2，3，4，5，6，7，8，9，101. 先根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.1.6 树林

13、的周游树林的周游 5.2.1 5.2.1 树的存储表示树的存储表示 5.2.2 5.2.2 树林的存储表示树林的存储表示 5.2.3 5.2.3 树和树林的其它表示法树和树林的其它表示法* *5.2.1 5.2.1 树的存储表示树的存储表示 树的父指针表示法 树的子表表示法 树的长子-兄弟表示法struct ParTreeNode/* 树中结点构造 */ DataTypeinfo; /* 结点中的元素 */intparent; /* 结点的父结点位置 */;struct ParTree struct ParTreeNode nodelistMAXNUM; /* 存放树中的结点 */ int n

14、; /* 树中结点的个数 */; typedef struct ParTree *PParTree;树的父指针表示法用一组延续空间存储树的结点，并附设一个指示器指示其双亲结点的位置。构造类型如下： 优点：a)容易找到父结点及其一切的祖先； b)能找到结点的子女和兄弟； 缺陷：a)没有表示出结点之间的左右次序； b)找结点的子女和兄弟比较费事。改良方法：按一种周游次序在数组中存放结点,。常见的一种方法是依次存放树的先根序列，如以下图：(a) (b) 图5.5 一棵树的父指针表示 结点表中的每一元素又包含一个子表，存放该结点的一切子结点。结点表顺序存放，子表用链接表示。struct EdgeNod

15、e /* 子表中节点的构造 */intnodeposition;struct EdgeNode*link;struct ChiTreeNode /* 结点表中节点的构造 */DataTypeinfo;struct EdgeNode*children;子表表示的树构造定义如下：struct ChiTree /* 树构造 */ struct ChiTreeNode nodelistMAXNUM; introot; /* 根结点的位置 */ intn; /* 结点的个数 */typedef struct ChiTree * PChiTree; 求某个结点的最左子女运算很容易实现，找到结点的全部子女也

16、很容易，但求某个结点的父母和右兄弟实现起来比较费事。另一个缺陷是：合并假设干个子树构成一个新树时createTree_chitree操作也要思索多个结点表的合并问题，由于这些结点表通常用顺序方式表示，所以合并起来比较费事。 info parent 0 a 1 b 2 d 3 e 4 h 5 i 6 j 7 c 8 f 9 g 1 7 2 3 4 6 8 9 5 图5.6 树的子表表示法 在树的每个结点中，除信息域外，添加指向其最左子女和右兄弟的指针。struct CSNode; /* 树中结点构造 */typedef struct CSNode *PCSNode;/* 结点的指针类型 */st

17、ruct 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 5.2.2 树林的存储表示树林的存储表示 父指针表示法 子表表示法 长子-兄弟表示法树林的父结点表示方法 info parent 0 A 1 B 2 C 3 K 4 D 5 E

18、6 H 7 F 8 J 9 G 1 2 3 5 9 8 6 7 树林的子表表示法 t A B D C E H J K F G 树林的长子兄弟表示法 5.3.1 5.3.1 二叉树的根本概念二叉树的根本概念 5.3.2 5.3.2 二叉树的性质二叉树的性质 5.3.3 5.3.3 二叉树的根本运算二叉树的根本运算 5.3.4 5.3.4 二叉树的周游二叉树的周游 5.3.5 5.3.5 树、树林与二叉树的转换树、树林与二叉树的转换二叉树： 它是结点的有限集合，这个集合或者为空集或者由一个根及两棵不相交的分别称作这个根的“左子树和“右子树的二叉树组成。 它的每一个结点至多有两棵子树，并且子树有左右

19、之分，不能随意颠倒。二叉树的根本形状：左子树右子树右子树左子树1空二叉树2只需一个根结点3有根结点 和左子树4有根结点 和右子树5有根结点 和左，右子树 二叉树不是树的特殊情形，它们是两个概念。 树和二叉树之间最主要的差别是：二叉树中结点的子树要区分为左子树和右子树，即使在结点只需一棵子树的情况下也要明确指出该子树是左子树还是右子树。 3和4是两棵不同的二叉树，但作为树，它们是一样的。 在二叉树中可定义类似树中的概念。 满二叉树：假设一棵二叉树的任何结点满二叉树：假设一棵二叉树的任何结点或者是树叶，或者有两棵非空子树，那么此或者是树叶，或者有两棵非空子树，那么此二叉树称作二叉树称作“满二叉树。

20、满二叉树。 完全二叉树：假设一棵二叉树至多只需完全二叉树：假设一棵二叉树至多只需最下面的两层结点度数可以小于最下面的两层结点度数可以小于2 2，并且最，并且最下面一层的结点都集中在该层最左边的假设下面一层的结点都集中在该层最左边的假设干位置上，那么此二叉树称为干位置上，那么此二叉树称为“完全二叉树完全二叉树。完全二叉树不一定是满二叉树。完全二叉树不一定是满二叉树。满二叉树完全二叉树扩展二叉树扩展二叉树 ： 把原二叉树的结点都变为度数为把原二叉树的结点都变为度数为2 2的分支结点，的分支结点，也就是说，假设原结点的度数为也就是说，假设原结点的度数为2 2，那么不变，度数，那么不变，度数为为1 1

21、，那么添加一个分支，度数为，那么添加一个分支，度数为0 0树叶添加两树叶添加两个分支。个分支。 在扩展的二叉树里，新添加的外部结点的个数比原来的内部结点个数多1。 “外部途径长度E：在扩展的二叉树里从根到每个外部结点的途径长度之和。“内部途径长度I：在扩展的二叉树里从根到每个内部结点的途径长度之和。 E = I + 2n 其中，n是内部结点的个数。证明：当n=1时，I=0, E=2, 此等式成立。 设有n个内部结点的扩展二叉树，下式成立。 En=In+2n (1) 对于 n+1 个内部结点的扩展二叉树，去掉一个 作为原来二叉树途径长度为K的内部结点，内部途径长度变为： In=In+1-K (2

22、) 外部途径长度变为：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 代入2abceef性质性质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

23、 0。 K k M= mi 2i = 2k+1-1 i=0 i=0 20 + 21 + 22 + 2k性质性质3. 对任何一棵非空二叉树对任何一棵非空二叉树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 性质性质

24、5. 假设对一棵有假设对一棵有n个结点的完全二叉树按层次次个结点的完全二叉树按层次次序序 从从1开场编号，那么对任一结点开场编号，那么对任一结点i1 in)，有：有： 1i=1，序号结点，序号结点i是根；是根；i1, 其双亲结点是其双亲结点是 i/2 。 22i n，序号为，序号为i的结点的左子女结点的序号为的结点的左子女结点的序号为2i； 2in ,序号为序号为i的结点无左子女。的结点无左子女。 32i+1 n，序号为，序号为i的结点的右子女结点的序的结点的右子女结点的序号号 为为2i+1; 2i+1 n,序号为序号为i的结点无右子女。的结点无右子女。性质5的证明：对于2和3 当i=1时，

25、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. 完全二叉树的层次序列，反映了它的构造。123jj+1 2j 2j+1 2(j+1) 2(j+1)+1创建一棵空二叉树；判别某棵二叉树能否为空；求二叉树的根结点，假设为空，那么前往一特殊值；求二叉树中某个指定结点的父结点，当指定结点为根时，前往一特殊值；求二叉树中某个指定结点的左子女结点，当指定结点没有左子女时，

26、前往一特殊值；求二叉树中某个指定结点的右子女结点，当指定结点没有右子女时，前往一特殊值；二叉树的周游。二叉树的周游二叉树的周游(Traversing Binary Tree)： 按某条搜索途径访问二叉树中的一切结点按某条搜索途径访问二叉树中的一切结点 ，使得每个结点被访问一次且仅被访问一次。使得每个结点被访问一次且仅被访问一次。三种方式：三种方式： 先根次序先根次序 (DLR) 对称序对称序 (LDR) 后根次序后根次序 (LRD)DLRABDCEFIHG 图5.15 二叉树先根次序A B D C E G F H I 后根次序D B G E H I F C A 对称序中根次序D B A E G

27、 C H F I 对右图进展先根、后根和中根次序周游得到如下的结点序列： 先根：-ab+cd 前缀表示 后根：ab-cd+ 后缀表示 (波兰表示法) 对称序：a-b c+d 中缀表示-+abcd图 5.16 表达式的二叉树表示递归算法先根次序中根次序后根次序二. 非递归算法 (用自定义的栈来替代系统的栈)先根次序中根次序后根次序 1 2 1. 树、树林转换为二叉树树、树林转换为二叉树执行步骤：执行步骤：1在一切相邻的兄弟结点之间连一条线；在一切相邻的兄弟结点之间连一条线；2对每个非终端结点，只保管它到其最左子女的对每个非终端结点，只保管它到其最左子女的 连线，删去它与其它子女的连线；连线，删去

28、它与其它子女的连线；3以根结点为轴心，将整棵树进展旋转。以根结点为轴心，将整棵树进展旋转。树、树林树、树林 二叉树二叉树ABCKDEFGHJ图5.20 树林转换为二叉树执行步骤：1假设某结点是其父母的左子女，那么把该结点 的右子女，右子女的右子女， ,都与 该结点的父母用线衔接起来； 2去掉原二叉树中一切父母到右子女的连线。ABDCEKHFJG图 5.22 二叉树转换为树林 5.4.1 5.4.1 顺序表示顺序表示 5.4.2 5.4.2 链接表示链接表示 5.4.3 5.4.3 二叉树的生成二叉树的生成 5.4.4 5.4.4 线索二叉树线索二叉树* * 用一组地址延续的存储单元按层次次序依

29、次存储完全二叉树的结点。完全二叉树的层次序列反映了它的层次构造。ABCGFEDHIJ 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; 二叉树的链接表示是指用一个链表来存储

30、一棵二叉树，二叉树中的每一个结点用链表中的一个链结点来存储，最常用的链接表示方式是左-右指针表示法llink-rlink表示法，也称做二叉链表，这种表示法在每个链结点中除存储结点本身的数据外，再设置两个指针字段：llink和rlink，分别存放结点的左子女和右子女所在链结点的存储地址，当结点的某个子女为空时，那么相应的指针为空指针。 struct BinTreeNode;/* 二叉树中结点 */typedef struct BinTreeNode *PBinTreeNode;/* 结点的指针类型 */struct BinTreeNode DataType info;/* 数据域 */PBinT

31、reeNode llink;/* 指向左子女 */PBinTreeNode rlink;/* 指向右子女 */;typedef struct BinTreeNode *BinTree; typedef BinTree *PBinTree; ABDCEFIHGt A B C E F I H G D 图5.15 二叉树的二叉链表表示tA B D C E F I H G 图5.15 三叉链表表示 周游是二叉树各种操作的根底，可以在周游过程中进展各种操作，如可以在周游过程中生成结点，从而建立一棵二叉树。 例：读入字符序列： ABDCEGFHI建立图5.13所示的二叉树，其中，表示空结点。算法5.5 按

32、先根序列创建二叉树t A B C E F I H G D 图5.15 二叉树的二叉链表表示保管遍历过程中得到的信息以供某些操作运用1添加两个指针2利用构造中的空链域，并设立标志。线索：指向结点前驱或后继的指针。线索二叉树：加上线索的二叉树。线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程。按对称序线索化二叉树:按对称序周游二叉树，周游到那个结点对那个结点加线索。按对称序周游对称序穿线树:沿线索周游。struct ThrTreeNode;typedef struct ThrTreeNode*PThrTreeNode;struct ThrTreeNode /*结点类型*/ DataType

33、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 按对称序周游对称序穿线树 对称序穿线树里的线索总是指向二叉树中更高层的结点，也就是说是“向上指的(如以下图。利用该“向上指的线索我们可以在对称序穿线树里找出指定结点在先根下的后继结点和后根下的前驱结点。 5.5.1 5.5.1 哈夫曼树哈夫曼树 5.5.2 5.5.2 哈夫曼哈夫曼(Huffman)(Huffman)算法算法 5.5.3 5.5.3 哈夫曼编