数据结构 树和二叉树PPT课件

1、 树（树（TreeTree）是）是n n（n0n0）个结点的有限集合。在任意）个结点的有限集合。在任意一棵非空树中：一棵非空树中： （1 1）有且仅有一个特定的称为根（）有且仅有一个特定的称为根（RootRoot）的结点；）的结点； （2 2）当）当n n 1 1时，其余结点可分为时，其余结点可分为m m（m m 0 0）个互不相交）个互不相交的有限集合的有限集合T T1 1，T T2 2，T Tm m，其中每一个集合本身又是，其中每一个集合本身又是一棵树，并且称为根的子树（一棵树，并且称为根的子树（SubtreeSubtree）。）。 第1页/共104页树形结构示例树形结构示例 ACDIHG

2、BFEMJKLA只有一个根结点的树只有一个根结点的树这是一个这是一个有有13个结点的树，其中个结点的树，其中A是根结点，其是根结点，其余结点分成三个互不相交的结点的子集：余结点分成三个互不相交的结点的子集： T1=B，E，F，K，L， T2=C，G， T3=D，H，I，J，M。T1、T2、T3都是都是A的子树，且它们本身也是一棵树的子树，且它们本身也是一棵树第2页/共104页树的基本术语 结点的度：结点的度： 一个结点所拥有的一个结点所拥有的子树子树的的个数个数。 例：例：结点结点A的度为的度为3，结点，结点E的度为的度为2，结点，结点M的度为的度为0。 树的度： 树中所有结点的度的最大值。即

3、MAX结点的度。 例：右图所示树的度为3。ACDIHGBFEMJKL第3页/共104页树的基本术语 叶子结点：叶子结点： 度为度为0 0的结点称为叶子的结点称为叶子结点或终端结点。结点或终端结点。 例：右图所示树中的例：右图所示树中的结点结点K K、L L、F F、G G、M M、I I、J J为叶子结点。为叶子结点。ACDIHGBFEMJKL分支结点：分支结点： 度不为度不为0 0的结点称为非的结点称为非终端结点或分支结点。除终端结点或分支结点。除根结点外，分支结点也称根结点外，分支结点也称为内部结点。为内部结点。第4页/共104页树的基本术语树的基本术语 孩子结点和孩子结点和父父结点（双亲

4、结点）：结点（双亲结点）： 一个结点的子树的根称为该结一个结点的子树的根称为该结点的孩子（点的孩子（Child）。相应的，该）。相应的，该结点称为孩子的双亲（结点称为孩子的双亲（ParentsParents）或父结点。或父结点。ACDIHGBFEMJKL兄弟结点：兄弟结点： 同一个双亲的孩子之间同一个双亲的孩子之间互称为兄弟（互称为兄弟（SiblingSibling）。）。第5页/共104页树的基本术语 ACDIHGBFEMJKL祖先结点： 从根到一个结点的路径上的所有结点称为该结点的祖先结点。子孙结点： 以某结点为根的子树中的所有结点都是该结点的子孙。第6页/共104页树的基本术语 树的深度

5、树的深度 树中所有结点的层次的最大树中所有结点的层次的最大值称为树的深度或高度。即值称为树的深度或高度。即MAXMAX结结点的层次点的层次 。 例：例：右图所示树的深度为右图所示树的深度为4 4 。ACDIHGBFEMJKL结点的层次：结点的层次： 一棵树从根开始定义，根为第一棵树从根开始定义，根为第一层，根的孩子为第二层，一层，根的孩子为第二层，依，依此类推。若某结点在第此类推。若某结点在第i i层，则其层，则其子树的根就在第子树的根就在第i i1 1层。层。第7页/共104页树的基本术语 森林（Forest）： m（m0）棵互不相交的树的集合称为森林。对树中每个结点而言，其子树的集合即为森

6、林。CDIHGBFEMJKL第8页/共104页课堂思考 u 下面两个叙述是否正确？下面两个叙述是否正确？1.1. 根结点也可以是叶子结点。根结点也可以是叶子结点。2.2. 度为度为0 0的结点就是叶子结点。的结点就是叶子结点。u 判断右边判断右边(a)(a)、(b)(b)所示所示图形是否树？图形是否树？BFEKLCDHGMJ(b)(a)第9页/共104页 因为树是一种非线性结构，所以不能简单地用一维数组或单链因为树是一种非线性结构，所以不能简单地用一维数组或单链表来存储树。为了存储树，必须把树中每个结点之间存在的关系反表来存储树。为了存储树，必须把树中每个结点之间存在的关系反映在存储结构之中，

7、才能如实的表现一棵树。映在存储结构之中，才能如实的表现一棵树。 树的存储结构有多种表示方法，下面介绍常用的三种。树的存储结构有多种表示方法，下面介绍常用的三种。 这种表示法要求用一维数组来存储树的有关信息，这种表示法要求用一维数组来存储树的有关信息，每个结点每个结点对应一个数组元素对应一个数组元素，它包含两个域：一个是，它包含两个域：一个是数据域数据域（datadata），存），存放该结点所包含的数据；一个是放该结点所包含的数据；一个是指针域指针域（parentparent），指出该结点），指出该结点的双亲结点的位置（整数）。的双亲结点的位置（整数）。第10页/共104页RBCFHAEDGK0

8、R-11A02B03C04D15E16F37G68H69K6数据域数据域指针域指针域 在树的双亲表示法在树的双亲表示法中，求某个结点的双亲中，求某个结点的双亲结点是非常容易的，但结点是非常容易的，但求某个结点的孩子结点求某个结点的孩子结点比较困难，需要比较困难，需要遍历整遍历整个结构个结构。 第11页/共104页 方法之一：把每个结点的孩子结点排列起来，构成一个单链表，方法之一：把每个结点的孩子结点排列起来，构成一个单链表，则则n n个结点有个结点有n n个孩子链表（叶子结点的孩子链表为空）。而个孩子链表（叶子结点的孩子链表为空）。而n n个头个头指针又组成一个线性表，采用顺序存储结构存储。每

9、个结点只要掌指针又组成一个线性表，采用顺序存储结构存储。每个结点只要掌握了这个单链表的表头，就容易找到它的全部孩子。握了这个单链表的表头，就容易找到它的全部孩子。 0R1A2B3C4D5E6F7G8H9K716245893RBCFHAEDGK第12页/共104页 在树的孩子表示法中，寻找任意结点的孩子是比较容易的，在树的孩子表示法中，寻找任意结点的孩子是比较容易的，但寻找它的双亲却比较困难。我们可以将双亲表示法和孩子表示但寻找它的双亲却比较困难。我们可以将双亲表示法和孩子表示法合在一起。法合在一起。 0-1R10A20B30C41D51E63F76G86H96K716245893RBCFHAE

10、DGK第13页/共104页 又称为二叉链表表示法又称为二叉链表表示法( (或二叉树表示法或二叉树表示法) )。即以二。即以二叉链表作为树的存储结构，叉链表作为树的存储结构，链表中每个结点设有两个链链表中每个结点设有两个链域，一个指向该结点的域，一个指向该结点的第一第一个孩子个孩子，一个指向该结点的，一个指向该结点的下一个兄弟下一个兄弟结点。结点类型结点。结点类型定义如下：定义如下：struct node anytype data； struct node *firstchild，*nextsibling； ； 第14页/共104页1二叉树的定义二叉树的定义 二叉树二叉树的特点是每个结点至多只有

11、两棵子树（即二叉树中不的特点是每个结点至多只有两棵子树（即二叉树中不存在度大于存在度大于2 2的结点），并且，二叉树的子树有左右之分，其次序的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。二叉树有五种基本形态：不能任意颠倒。二叉树有五种基本形态： 二叉树二叉树（Binary treeBinary tree）是树形结构中一种最典型、最常用的）是树形结构中一种最典型、最常用的结构，处理起来也比一般树简单，因此，在实际应用中，通常将结构，处理起来也比一般树简单，因此，在实际应用中，通常将一般树形结构转化为二叉树进行处理。一般树形结构转化为二叉树进行处理。第15页/共104页2二叉树的基本

12、性质二叉树的基本性质 性质性质1 1 在二叉树的第在二叉树的第i i层上至多有层上至多有2 2i-1i-1个结点（个结点（i1i1）。）。第一层 21-1第二层 22-1第三层 23-1ACFBEDK第16页/共104页2二叉树的基本性质二叉树的基本性质 性质性质2 2 深度为深度为k k的二叉树至多有的二叉树至多有2 2k k1 1个结点个结点(k1)(k1)。深度1 21-1深度2 22-1深度3 23-1ACFBEDK第17页/共104页2二叉树的基本性质二叉树的基本性质 性质性质3 3 对任何一棵二叉树对任何一棵二叉树T T，设，设n n0 0、n n2 2分别是叶子结点个数分别是叶子

13、结点个数 和度为和度为2 2的结点个数，则：的结点个数，则：n n0 0n n2 21 1。n0：3n2：2ACFBED第18页/共104页证明：证明： 在二叉树中有在二叉树中有 n n0 0n n2 21 1。 从结点的度来看，二叉树中只有三种结点：度为从结点的度来看，二叉树中只有三种结点：度为0 0、1 1、2 2的结点。的结点。 假设二叉树中，度为假设二叉树中，度为0 0的结点有的结点有n n0 0个，个， 度为度为1 1的结点有的结点有n n1 1个，度为个，度为2 2的的结点有结点有n n2 2个，则结点总数：个，则结点总数： n=n0+n1+n2 - (1) 二叉树中除根结点外，其

14、余结点都由分支引入，则二叉树中除根结点外，其余结点都由分支引入，则 n=n=1 1+ +分支总数分支总数 - (2) 分支总数分支总数与结点的度有关与结点的度有关：度为：度为0 0的结点不发出分支；一个度为的结点不发出分支；一个度为1 1的结的结点发出点发出1 1条分支，则度为条分支，则度为1 1的结点共发出分支的结点共发出分支n n1 1* *1 1条。条。一个度为一个度为2 2的结点发的结点发出出2 2条分支，则度为条分支，则度为2 2的结点共发出分支的结点共发出分支n n2 2* *2 2条。条。 分支总数分支总数=n=n1 1* *1 1+ +n n2 2 * *2 2 - (3) 由

15、（由（2 2）、（）、（3 3）得：）得： n= 1+ n1 1*1+n2 2 *2 - (4) 由（由（1 1）、（）、（4 4）得：）得： n n0 0+n+n1 1+n+n2 2 = = 1 1+ + n n1 1* *1 1+n+n2 2 * *2 2 即：即： n0 0= n2 2+1+1第19页/共104页课堂练习 设树设树T T的度为的度为4 4，其中度为，其中度为1 1、2 2、3 3、4 4的结点个数分别为的结点个数分别为4 4、2 2、1 1、1 1。问。问T T中有中有多少个叶子结点？多少个叶子结点？答案答案 树的分支数为树的分支数为15，结点数，结点数=分支数分支数+1

16、=16 叶子结点的个数叶子结点的个数=16-8=8个个第20页/共104页满二叉树与完全二叉树满二叉树与完全二叉树 m(深度)：3 ，结点数： 2m-1=7一棵深度为一棵深度为k k且有且有2 2k k1 1个结点的二叉树称为个结点的二叉树称为满二叉树满二叉树。ACFBEDK满二叉树的特点：满二叉树的特点：每一层上的结点数都是最大结点数。每一层上的结点数都是最大结点数。第21页/共104页深度为深度为k k的、有的、有n n个结点的二叉树，当且仅当其每一个结个结点的二叉树，当且仅当其每一个结点都与深度为点都与深度为k k的满二叉树中编号从的满二叉树中编号从1 1至至n n的结点一一对应的结点一

17、一对应时，称之为时，称之为完全二叉树完全二叉树。满二叉树与完全二叉树满二叉树与完全二叉树 ACFBEDK1234567完全二叉树的特点：完全二叉树的特点：1)1)叶子结点只可能在层次最大叶子结点只可能在层次最大的两层上出现。的两层上出现。2)2)对任一结点，若其右分支的对任一结点，若其右分支的子孙的最大层次为子孙的最大层次为L L，则其左，则其左分支的子孙的最大层次为分支的子孙的最大层次为L L或或L+1L+1。3)3)满二叉树一定是完全二叉树，满二叉树一定是完全二叉树，反之不成立。反之不成立。第22页/共104页2二叉树的基本性质二叉树的基本性质 性质性质4 4 具有具有n n个结点的完全二

18、叉树的深度为个结点的完全二叉树的深度为 loglog2 2n n 1 1。 假设二叉树的深度为假设二叉树的深度为k k，则根据性质，则根据性质2 2和完全二叉和完全二叉树的定义有：树的定义有： 2 2k-1k-1-1n2-1n2k k-1-1 或或 2 2k-1k-1n2n2k k 于是于是 k-1logk-1log2 2nkndata=ch; t-lchild=creattree(); /*建立它的左子树的二叉链表建立它的左子树的二叉链表*/ t-rchild=creattree(); /*建立它的右子树的二叉链表建立它的右子树的二叉链表*/ return t;生成二叉树链表的算法生成二叉树

19、链表的算法:第33页/共104页 所谓遍历二叉树（所谓遍历二叉树（Traversing Binary TreeTraversing Binary Tree），），就是指按一定的规则和次序访问树中的每个结点，使每就是指按一定的规则和次序访问树中的每个结点，使每个结点被访问且仅只被访问一次。个结点被访问且仅只被访问一次。 遍历二叉树是以一定规则将二叉树中的结点排列成遍历二叉树是以一定规则将二叉树中的结点排列成一个线性序列一个线性序列。实质上是对一个非线性结构进行线性化。实质上是对一个非线性结构进行线性化操作，使每个结点（除第一个和最后一个之外）在这些操作，使每个结点（除第一个和最后一个之外）在这些

20、线性序列中有且仅有一个直接前趋和直接后继。线性序列中有且仅有一个直接前趋和直接后继。 第34页/共104页若二叉树为空，则返回。否则：若二叉树为空，则返回。否则： （1 1）访问根结点；）访问根结点； （2 2）先根遍历左子树；）先根遍历左子树； （3 3）先根遍历右子树；）先根遍历右子树； （4 4）返回。）返回。 例如，对下图(a)所示的二叉树进行先根遍历所得到的先根次序的结点序列是ABCDEF。 同一先根序列可对应多棵二叉树。例如，图(b)所示的二叉树的先根序列仍然是ABCDEF。可见，由先根序列不能唯一确定二叉树。第35页/共104页 void preorder(struct node

21、 *t) /* t为指向二叉树根结点的指针 */ if (t!=NULL) visit ( t-data )；/* printf(“%c ”, t-data ) ;*/ preorder( t-lchild ); preorder( t-rchild ); 先根遍历的递归算法如下：第36页/共104页void preorder(struct node *bt ) if ( bt!=NULL) printf(“%d ”,bt-data); preorder( bt-lchild ); preorder( bt-rchild ); return;ABEC遍历算法遍历算法bt第37页/共104页AB

22、EC遍历算法遍历算法btAvoid preorder(struct node *bt ) if ( bt!=NULL) printf(“%d ”,bt-data); preorder( bt-lchild ); preorder( bt-rchild ); return;第38页/共104页ABEC遍历算法遍历算法btAvoid preorder(struct node *bt ) if ( bt!=NULL) printf(“%d ”,bt-data); preorder( bt-lchild ); preorder( bt-rchild ); return;第39页/共104页ABEC遍历

23、算法遍历算法btAvoid preorder(struct node *bt ) if ( bt!=NULL) printf(“%d ”,bt-data); preorder( bt-lchild ); preorder( bt-rchild ); return;第40页/共104页ABEC遍历算法遍历算法btA Bvoid preorder(struct node *bt ) if ( bt!=NULL) printf(“%d ”,bt-data); preorder( bt-lchild ); preorder( bt-rchild ); return;第41页/共104页ABEC遍历算法

24、遍历算法btA Bvoid preorder(struct node *bt ) if ( bt!=NULL) printf(“%d ”,bt-data); preorder( bt-lchild ); preorder( bt-rchild ); return;第42页/共104页ABEC遍历算法遍历算法bt： A Bvoid preorder(struct node *bt ) if ( bt!=NULL) printf(“%d ”,bt-data); preorder( bt-lchild ); preorder( bt-rchild ); return;第43页/共104页ABEC遍历

25、算法遍历算法btA Bvoid preorder(struct node *bt ) if ( bt!=NULL) printf(“%d ”,bt-data); preorder( bt-lchild ); preorder( bt-rchild ); return;第44页/共104页ABEC遍历算法遍历算法bt： A Bvoid preorder(struct node *bt ) if ( bt!=NULL) printf(“%d ”,bt-data); preorder( bt-lchild ); preorder( bt-rchild ); return;第45页/共104页ABEC

26、遍历算法遍历算法btA Bvoid preorder(struct node *bt ) if ( bt!=NULL) printf(“%d ”,bt-data); preorder( bt-lchild ); preorder( bt-rchild ); return;第46页/共104页ABEC遍历算法遍历算法btA Bvoid preorder(struct node *bt ) if ( bt!=NULL) printf(“%d ”,bt-data); preorder( bt-lchild ); preorder( bt-rchild ); return;第47页/共104页ABEC

27、遍历算法遍历算法btA B Evoid preorder(struct node *bt ) if ( bt!=NULL) printf(“%d ”,bt-data); preorder( bt-lchild ); preorder( bt-rchild ); return;第48页/共104页ABEC遍历算法遍历算法btA B Evoid preorder(struct node *bt ) if ( bt!=NULL) printf(“%d ”,bt-data); preorder( bt-lchild ); preorder( bt-rchild ); return;第49页/共104页

28、ABEC遍历算法遍历算法btA B Evoid preorder(struct node *bt ) if ( bt!=NULL) printf(“%d ”,bt-data); preorder( bt-lchild ); preorder( bt-rchild ); return;第50页/共104页ABEC遍历算法遍历算法btA B E Cvoid preorder(struct node *bt ) if ( bt!=NULL) printf(“%d ”,bt-data); preorder( bt-lchild ); preorder( bt-rchild ); return;第51页

29、/共104页ABEC遍历算法遍历算法btA B E Cvoid preorder(struct node *bt ) if ( bt!=NULL) printf(“%d ”,bt-data); preorder( bt-lchild ); preorder( bt-rchild ); return;第52页/共104页ABEC遍历算法遍历算法bt: A B E Cvoid preorder(struct node *bt ) if ( bt!=NULL) printf(“%d ”,bt-data); preorder( bt-lchild ); preorder( bt-rchild ); r

30、eturn;第53页/共104页ABEC遍历算法遍历算法btA B E Cvoid preorder(struct node *bt ) if ( bt!=NULL) printf(“%d ”,bt-data); preorder( bt-lchild ); preorder( bt-rchild ); return;第54页/共104页ABEC遍历算法遍历算法bt: A B E Cvoid preorder(struct node *bt ) if ( bt!=NULL) printf(“%d ”,bt-data); preorder( bt-lchild ); preorder( bt-r

31、child ); return;第55页/共104页ABEC遍历算法遍历算法btA B E Cvoid preorder(struct node *bt ) if ( bt!=NULL) printf(“%d ”,bt-data); preorder( bt-lchild ); preorder( bt-rchild ); return;第56页/共104页ABEC遍历算法遍历算法bt: A B E Cvoid preorder(struct node *bt ) if ( bt!=NULL) printf(“%d ”,bt-data); preorder( bt-lchild ); preo

32、rder( bt-rchild ); return;第57页/共104页ABEC遍历算法遍历算法btA B E Cvoid preorder(struct node *bt ) if ( bt!=NULL) printf(“%d ”,bt-data); preorder( bt-lchild ); preorder( bt-rchild ); return;第58页/共104页若二叉树为空，则返回。否则：若二叉树为空，则返回。否则： （1 1）中根遍历左子树；）中根遍历左子树； （2 2）访问根结点；）访问根结点； （3 3）中根遍历右子树；）中根遍历右子树； （4 4）返回。）返回。 例如，

33、对下图(a)所示的二叉树进行中根遍历所得到的中根序列是ABCDEF。 同一中根序列可对应多棵二叉树。例如，图(b)所示的二叉树的中根序列仍然是ABCDEF。可见，由中根序列不能唯一确定二叉树。第59页/共104页 中中根遍历的递归算法根遍历的递归算法: void inorder(struct node *t) /* t为指向二叉树根结构的指针为指向二叉树根结构的指针*/ if ( t ! = NULL ) inorder (t -lchild ); visit ( t -data ); /* printf(“%c ”, t-data ) ;*/ inorder ( t-rchild ) ; 第

34、60页/共104页若二叉树为空，则返回。否则：若二叉树为空，则返回。否则： （1 1）按后根次序遍历左子树；）按后根次序遍历左子树； （2 2）按后根次序遍历右子树；）按后根次序遍历右子树； （3 3）访问根结点；）访问根结点； （4 4）返回。）返回。 例如，对下图(a)所示的二叉树进行后根遍历所得到的后根序列是ABCDEF。 同一后根序列可对应多棵二叉树。例如，图(b)所示的二叉树的后根序列仍然是ABCDEF。可见，由后根序列不能唯一确定二叉树。第61页/共104页void postorder (struct node *t ) if (t!=NULL) postorder (tlchil

35、d)； postorder(trchild)； visit( tdata) ； /* printf(“%c ”, t-data ) ;*/ 后根遍历的递归算法：第62页/共104页例 已知某二叉树的前根序列为ABCDEFG，中根序列为CBDAEFG。求该二叉树的后根序列。 由前根序列可以推断：A是二叉树的根结点。 根据中根遍历的规则可知：在中根序列中，A左侧的C、B、D三个结点构成了A的左子树，而A右侧的E、F、G三个结点构成了A的右子树。 A的左子树：前根序列为BCD，中根序列为CBD。 A的右子树：前根序列为EFG，中根序列为EFG。此时，确定的二叉树如右图所示。 A的左子树： 根结点：B

36、 B的左子树：仅包含C，即C是B的左孩子。 B的右子树：仅包含D，即D是B的右孩子。A的左子树分析完毕。如右图所示。第63页/共104页A的右子树： 根结点：E E的左子树：空。 E的右子树：前序序列为FG，中序序列为FG。如下左图所示。 根结点：F F的左子树：空。 F的右子树：仅包含G，即G是F的右孩子。 E的右子树分析完毕。A的右子树分析完毕。如下右图所示。 二叉树的后根序列:CBDGFEA第64页/共104页二叉树操作实例 #include alloc.h#include stdio.hstruct node char data; struct node *lchild; struct

37、 node *rchild; ;struct node *creattree() /*建立二叉链表建立二叉链表*/ char ch; struct node *t; scanf(%c,&ch); if (ch=#) t=NULL; else t=(struct node *)malloc(sizeof(struct node); if (t=NULL) printf(out of memoryn); exit(0); t-data=ch; t-lchild=creattree(); t-rchild=creattree(); return t; 第65页/共104页void preor

38、der(struct node *t) /*前根遍历二叉树前根遍历二叉树*/ if (t!=NULL) printf(%3c,t-data); preorder(t-lchild); preorder(t-rchild); void inorder(struct node *t) /*中根遍历二叉树中根遍历二叉树*/ if (t!=NULL) inorder(t-lchild); printf(%3c,t-data); inorder(t-rchild); void postorder(struct node *t) /*后根遍历二叉树后根遍历二叉树*/ if (t!=NULL) postor

39、der(t-lchild); postorder(t-rchild); printf(%3c,t-data); 第66页/共104页void main() struct node *root; printf(建立二叉树建立二叉树,按先根次序输入结点序列按先根次序输入结点序列n); root= creattree(); printf(n先根遍历次序为先根遍历次序为:n); preorder(root); getchar(); printf(n中根遍历次序为中根遍历次序为:n); inorder(root); printf(n后根遍历次序为后根遍历次序为:n); postorder(root);

40、getchar();第67页/共104页 一个有一个有n n个结点的二叉树，其二叉链表共有个结点的二叉树，其二叉链表共有2n2n个指针域，其中个指针域，其中用于指向孩子结点（左、右子树用于指向孩子结点（左、右子树）的指针域只有的指针域只有n-1n-1个，而另外个，而另外2n-2n-(n-1)=(n-1)=n n1 1个指针域是空（个指针域是空（NULLNULL）的，可以利用这些空指针域来指）的，可以利用这些空指针域来指向结点在遍历序列的前趋或后继结点。其中，用树中向结点在遍历序列的前趋或后继结点。其中，用树中空的左指针空的左指针指指向该结点的向该结点的前趋结点前趋结点，空的右指针空的右指针指向

41、该结点的指向该结点的后继结点后继结点。 线索：线索：指向遍历序列中的前趋结点或后继结点的指针。指向遍历序列中的前趋结点或后继结点的指针。 线索化：线索化：对二叉树以某种次序进行遍历并加上线索的过程称为对二叉树以某种次序进行遍历并加上线索的过程称为线索化。线索化。 线索二叉树：线索二叉树：经过线索化后生成的二叉树称为线索二叉树。经过线索化后生成的二叉树称为线索二叉树。 第68页/共104页 为了区分结点指针是线索指针还是子树指针，在每个为了区分结点指针是线索指针还是子树指针，在每个结点的指针中增加两个标志域结点的指针中增加两个标志域 Lt 和和 Rt： 0 0 指向子树（孩子）的指针指向子树（孩

42、子）的指针 LtLt（或（或RtRt）= = 1 1 指向前趋或后继结点的线索指向前趋或后继结点的线索LtlchilddatarchildRt线索树的结点结构线索树的结点结构线索树的二叉链表的结点类型定义为:struct node anytype data； struct node *lchild； struct node *rchild； int Lt, Rt; ；第69页/共104页ABCDFEBT前根线索树示例前根遍历序列：ABDFCE000111011110第70页/共104页ABCDFEBT中根线索树示例中根遍历序列： BFDACE000001111111第71页/共104页ABCD

43、FEBT后根线索树示例后根遍历序列： FDBECA111111100000第72页/共104页inthread (struct node *T) struct node *p，*pr； /* pr指向指向p的前趋结点的前趋结点 */ int top； /* top为栈指针为栈指针 */ struct node *sMAX_TREE_SIZE； pr =NULL；top=-1；p=T； 建立中根线索树的非递归算法为：建立中根线索树的非递归算法为： 线索树的建立实质是将二叉链表中的空指针指向遍历线索树的建立实质是将二叉链表中的空指针指向遍历序列的前趋结点、后继结点序列的前趋结点、后继结点。 建立中

44、根线索树，实际上是建立中根线索树，实际上是在中根遍历的过程中修改在中根遍历的过程中修改空指针空指针，即在访问结点的同时，将空指针域逐个用线索替，即在访问结点的同时，将空指针域逐个用线索替代，并将其标志位置代，并将其标志位置1 1。第73页/共104页do while( p!=NULL ) /*沿左孩子指针将结点依次入栈沿左孩子指针将结点依次入栈*/ top=top+1； stop=p； p=p-lchild； if ( top!=-1 ) p=stop；top=top-1； /*弹出栈顶结点，访问该结点弹出栈顶结点，访问该结点*/ visit(p-data )； if (p-lchild=NU

45、LL ) /*该结点无左孩子该结点无左孩子*/ p-Lt=1；p-lchild=pr； /* 建左线索，使左指针指向前趋建左线索，使左指针指向前趋*/ else p-Lt=0; if (pr!=NULL ) if (pr-rchild =NULL ) pr-rchild= p； /*建右线索，使前趋结点的右指针指向建右线索，使前趋结点的右指针指向p*/ pr-Rt=1； else pr-Rt=0； pr=p； p=p-rchild； while (p!=NULL | top!=-1)； pr-Rt=1； 第74页/共104页1求结点求结点Q的前趋的前趋 若给定结点若给定结点Q Q的左标志位的左

46、标志位LtLt1 1，则，则Q Q的左指针所指的的左指针所指的是是Q Q的前趋结点，若的前趋结点，若LtLt0 0，则取，则取Q Q的左子树的根（左孩的左子树的根（左孩子），设为子），设为P P，并作如下讨论：，并作如下讨论： (1)(1)若若P P没有右子树没有右子树，即，即RtRt1 1，则，则P P为为Q Q的前趋结点。的前趋结点。 (2)(2)若若P P有右子树有右子树，则必须连续不断地沿着右子树的，则必须连续不断地沿着右子树的右指针，查询右孩子的标志位，若右指针，查询右孩子的标志位，若RtRt0 0，则通过右指针，则通过右指针找下一个结点（右孩子），若找下一个结点（右孩子），若RtR

47、t1 1，则该结点就是，则该结点就是Q Q的的前趋结点。前趋结点。注意：在连续不断地向右子树查询中，不能注意：在连续不断地向右子树查询中，不能转向左子树。转向左子树。 第75页/共104页ABCDFEBT结点F的Lt=1，其左指针指向的结点B即为它的前趋结点。中根遍历序列： BFDACE000001111111结点A的Lt=0，取其左子树的根结点B，B有右子树，沿着B的右指针查询到D结点的Rt=1，则D结点即为A的前趋结点。结点D的Lt=0，取其左子树的根结点F，F没有右子树，则F结点即为D的前趋结点。第76页/共104页2求结点求结点Q的后继的后继 若给定结点若给定结点Q Q的右标志位的右标

48、志位RtRt1 1，则，则Q Q的右指针所指的的右指针所指的是是Q Q的后继结点；若的后继结点；若RtRt0 0，则取，则取Q Q的右子树的根（右孩的右子树的根（右孩子），设为子），设为P P。 (1)(1)若若P P没有左子树没有左子树，即，即LtLt1 1，则，则P P是是Q Q的后继结点。的后继结点。 (2)(2)若若P P有左子树有左子树，则必须连续不断地沿着左子树的，则必须连续不断地沿着左子树的左指针，查询左孩子的标志位，若左指针，查询左孩子的标志位，若LtLt0 0，则通过左指针，则通过左指针找下一个结点（左孩子），若找下一个结点（左孩子），若LtLt1 1，则该结点就是，则该结点

49、就是Q Q的的后继结点。后继结点。注意：在连续不断地向左子树查询中，不能注意：在连续不断地向左子树查询中，不能转向右子树转向右子树。第77页/共104页ABCDFEBT结点F的Rt=1，其右指针指向的结点D即为它的后继结点。中根遍历序列： BFDACE000001111111结点A的Rt=0，取其右子树的根结点C，C没有左子树，则C结点即为A的后继结点。结点B的Rt=0，取其右子树的根结点D，D有左子树，沿着D的左指针查询到F结点的Lt=1，则F结点即为B的后继结点。第78页/共104页 在实际应用中，树的形态多种多样，其中每个结点的在实际应用中，树的形态多种多样，其中每个结点的度都可以是任意

50、的，这就给一般树的存储与研究带来了一度都可以是任意的，这就给一般树的存储与研究带来了一定的复杂性。为了处理的方便，通常需将一般树转化为二定的复杂性。为了处理的方便，通常需将一般树转化为二叉树进行处理。叉树进行处理。 1树与二叉树的转化树与二叉树的转化 将一棵树将一棵树T T转化为二叉树转化为二叉树BTBT的规则如下：的规则如下： (1)(1)若若T T为空，则为空，则BTBT为空；为空； (2)(2)树树T T的根作为二叉树的根作为二叉树BTBT的根；的根； (3)(3)将树将树T T中结点的第一个子结点中结点的第一个子结点( (即最左边的子结点即最左边的子结点) )，作为二叉树作为二叉树BT

51、BT中对应结点的左子结点；中对应结点的左子结点；T T中该结点的其他子结中该结点的其他子结点，则依次作为前一结点的右子结点出现在点，则依次作为前一结点的右子结点出现在BTBT中。中。 第79页/共104页2森林转化为二叉树森林转化为二叉树 设设F=TF=T1 1，T T2 2，T Tm m 是森林，可按如下规则将其转换成是森林，可按如下规则将其转换成一棵二叉树一棵二叉树BTBT=(root=(root，LBLB，RB)RB)。 (1)(1)若若F F为空，即为空，即m=0m=0，则，则BTBT为空；为空； (2)(2)若若F F非空，则非空，则BTBT的根的根rootroot即为森林中第一棵树

52、的根；即为森林中第一棵树的根；BTBT的左子树的左子树LBLB是从是从T T1 1中根结点的子结点转换而成的二叉树；中根结点的子结点转换而成的二叉树；其右子树其右子树RBRB是从森林是从森林F F中除去中除去T T1 1以后的子森林转换而成的。以后的子森林转换而成的。 第80页/共104页第81页/共104页 结点的路径长度：从二叉树的根结点到该结点之间的所有分支数目。 例如，下图(a)所示的二叉树中，a、b、c三个叶子结点的路径长度分别为1、2、2。 结点的带权路径长度：指该结点的路径长度与该结点的权值的乘积。 例如，图(a)中结点c的带权路径长度是27=14。 有时我们为二叉树的结点分配一

53、个数值，称为结点的权值。例如，左图(a)中，a、b、c三个结点的权值分别为9、3、7。第82页/共104页二叉树的带权路径长度：是指所有叶子结点的带权路径长度之和，记为WPL。nkkkpwWPL1 其中，n为叶子结点的个数，wk为第k个叶子结点的权值，pk为第k个叶子结点的路径长度。例如，图(a)中的二叉树共有三个叶子结点，其带权路径长度计算如下：WPL=w1p1+ w2p2+ w3p3 =91+32+72=29 第83页/共104页 哈夫曼树（最优二叉树） 在具有n个带权叶子结点的所有二叉树中，带权路径长度WPL最小的二叉树称为哈夫曼树（或最优二叉树）。 例如，下图所示的三棵二叉树，都有三个

54、权值相同的带权叶子结点。经计算，它们的带权路径长度分别为29、38、44。其中(a)树的WPL最小。可以验证，它恰好是最优二叉树，即在具有三个权值分别为9、3、7的带权叶子结点的所有二叉树中，它是带权路径长度最小的二叉树。第84页/共104页 假设给定了假设给定了n n个结点个结点d dk k（k=1k=1，2 2，n n），其权值分别为），其权值分别为ww1 1，w w2 2，w wn n ，构造哈夫曼树的过程如下：构造哈夫曼树的过程如下： (1)(1) 根据给定的根据给定的n n个权值个权值ww1 1，w w2 2，w wn n 构造构造n n棵二叉树的棵二叉树的集合集合F= TF= T1

55、 1，T T2 2，T Tn n ，其中每棵二叉树，其中每棵二叉树T Ti i中只有一个带权中只有一个带权为为w wi i的根结点，其左右子树均为空；的根结点，其左右子树均为空； (2)(2) 在在F F中选取两棵根结点的权值最小的树作为左右子树构中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新二叉树的根结点的权值为其左、右子造一棵新的二叉树，且置新二叉树的根结点的权值为其左、右子树上根结点的权值之和；树上根结点的权值之和； (3)(3) 在在F F中删除这两棵树，同时将新得到的二叉树加入中删除这两棵树，同时将新得到的二叉树加入F F中。中。 (4)(4) 重复重复(2)(

56、2)和和(3)(3)，直到直到F F只含一棵树为止只含一棵树为止。这棵树就是哈。这棵树就是哈夫曼树。夫曼树。 第85页/共104页 例：例： 假设给定了假设给定了5 5个结点个结点a a、b b、c c、d d、e e，其权值分别为，其权值分别为4 4、8 8、4 4、2 2、7 7。试构造以这。试构造以这5 5个结点为叶子结点的哈夫曼树个结点为叶子结点的哈夫曼树, ,并计并计算它的带权路径长度。要求左子树根结点的权值不大于右子树算它的带权路径长度。要求左子树根结点的权值不大于右子树根结点的权值。根结点的权值。 下图展示了此哈夫曼树的构造过程：下图展示了此哈夫曼树的构造过程：带权路径长度为：W

57、PL=(7+8)2+52+(2+4)3 =58第86页/共104页 哈夫曼树可用于编码问题哈夫曼树可用于编码问题。在进行远距离快速通信时，。在进行远距离快速通信时，通常要将需要传送的文字转换成由二进制数字组成的字符串。通常要将需要传送的文字转换成由二进制数字组成的字符串。假设需要传送电文假设需要传送电文“ABACCDAABACCDA”，这其中只用到，这其中只用到A A、B B、C C、D D四四种字符，可以用两位二进制数字分别对字符种字符，可以用两位二进制数字分别对字符A A、B B、C C、D D编码编码为为0000、0101、1010、1111，则实际传送的电文为，则实际传送的电文为“00

58、01001010110000010010101100” ，总长，总长1414位，在接收端可按两位一分进位，在接收端可按两位一分进行译码。行译码。 在实际应用中，总是希望电文的总长度尽可能短，这就在实际应用中，总是希望电文的总长度尽可能短，这就需要对电文中的各种字符设计长度不等的编码，并需要对电文中的各种字符设计长度不等的编码，并对电文中对电文中出现次数较多的字符采用尽可能短的编码出现次数较多的字符采用尽可能短的编码。 第87页/共104页 对应到二叉树上，若n种字符为二叉树的叶子结点，wk为叶子结点的权值，pk为叶子结点的路径长度，则 恰好为二叉树的带权路径长度。因此，设计电文总长最短的二进制

59、编码的问题，实际上就是设计哈夫曼树的问题。 设电文中共有设电文中共有n n种不同的字符，每种字符在电文中种不同的字符，每种字符在电文中出现的频率为出现的频率为w wi i ，其编码长度为，其编码长度为p pk k，则电文总长为：，则电文总长为：nkkkpw1nkkkpw1第88页/共104页 设电文中共有设电文中共有n n种不同的字符，每种字符在电文中出现的频种不同的字符，每种字符在电文中出现的频率为率为w wi i。将这。将这n n个字符作为二叉树的叶子结点，构造一棵具有个字符作为二叉树的叶子结点，构造一棵具有n n个叶子结点的哈夫曼树，然后对叶子结点进行编码，便可满足个叶子结点的哈夫曼树，

60、然后对叶子结点进行编码，便可满足以上编码的要求。以上编码的要求。 在对哈夫曼树上的叶子结点进行编码时，有如下在对哈夫曼树上的叶子结点进行编码时，有如下约定：约定： 所有所有左分支左分支表示二进制数字表示二进制数字“0 0”，右分支右分支表示二进制数字表示二进制数字“1 1”，则从根结点到叶子结点的路径上各分支的二进制数字顺，则从根结点到叶子结点的路径上各分支的二进制数字顺序组成的串称为该序组成的串称为该叶子结点的编码叶子结点的编码。 设电文为设电文为“ABACCDAABACCDA”，则利用哈夫曼树设计的电文则利用哈夫曼树设计的电文中各字符的编码如右图所示。中各字符的编码如右图所示。 第89页/共104页 我们知道，