第9章--树-----零基础学数据结构.ppt

1、第9章 树,从第3章到第8章介绍的线性表、栈、队列、串、数组和广义表都属于线性结构。本章要介绍的树和下一章要介绍的图都属于非线性数据结构。线性数据结构中的每个元素有唯一的前驱元素和唯一的后继元素，即前驱元素和后继元素是一对一的关系。,9.1 树,树是一种非线性的数据结构，树中的元素之间的关系是一对多的层次关系。本节主要介绍树的定义和树的抽象数据类型。,9.1.1 树的定义,树是n(n0)个结点的有限序列。其中，n=0时，称为空树。当n0时，称为非空树，满足以下条件： （1）有且只有一个称为根的结点。 （2）当n1时，其余n-1个结点可以划分为m个有限集合T1，T2，Tm，且这m个有限集合不相交

2、，其中Ti（1im）又是一棵树，称为根的子树。,9.1.2 树的逻辑表示,树的逻辑表示方法可以分为四种：树形表示法、文氏图表示法、广义表表示法和凹入表示法。,9.1.2 树的抽象数据类型,1数据对象集合 2基本操作集合,9.2 二叉树,在对一般树进行深入的学习之前，先学习一下一种比较简单的树二叉树。本节的主要学习内容包括二叉树的定义、基本性质及二叉树的抽象数据类型。,9.2.1 二叉树的定义,二叉树是由n(n0)个结点构成的另外一种树结构。二叉树中的每个结点最多只有两棵子树，并且二叉树中的每个结点都有左右次序之分，即次序不能颠倒。,9.2.1 二叉树的定义,9.2.2 二叉树的性质,二叉树具有

3、以下重要的性质。 性质1 在二叉树中，第m(m1)层上至多有2m-1个结点（规定根结点为第一层）。 性质2 深度为k(k1)的二叉树至多有2k-1个结点。 性质3 对任何一棵二叉树T，如果叶子结点总数为n0，度为2的结点总数为n2，则有n0=n2+1。 性质4 如果完全二叉树有n个结点，则深度为 。符号 表示不大于x的最大整数。 性质5 如果完全二叉树有n个结点，按照从上到下，从左到右的顺序对二叉树中的每个结点从1到n进行编号，则对于任意结点i有以下性质：,9.2.2 二叉树的性质,（1）如果i=1，则序号i对应的结点就是根结点，该结点没有双亲结点。 （2）如果2in，则序号为i的结点没有左孩

4、子结点。 （3）如果2i+1n，则序号为i的结点没有右孩子结点。,9.2.3 二叉树的抽象数据类型,1数据对象集合 2基本操作集合,9.3 二叉树的存储表示与实现,二叉树的存储结构有两种：顺序存储表示和链式存储表示。本节的主要学习内容包括二叉树的顺序存储表示、二叉树的链式存储表示及二叉树的基本操作实现。,9.3.1 二叉树的顺序存储,我们已经知道，完全二叉树中每个结点的编号可以通过公式计算得到，因此，完全二叉树的存储可以按照从上到下、从左到右的顺序依次存储在一维数组中。,9.3.1 二叉树的顺序存储,9.3.2 二叉树的链式存储,在二叉树中，每个结点有一个双亲结点和两个孩子结点。从一棵二叉树的

5、根结点开始，通过结点的左右孩子地址就可以找到二叉树的每一个结点。因此二叉树的链式存储结构包括三个域：数据域、左孩子指针域和右孩子指针域。其中，数据域存放结点的值，左孩子指针域指向左孩子结点，右孩子指针域指向右孩子的结点。,9.3.2 二叉树的链式存储,9.3.2 二叉树的链式存储,二叉链表存储结构的类型定义描述如下： typedef struct Node/*二叉链表存储结构类型定义*/ DataType data; /*数据域*/ struct Node *lchild; /*指向左孩子结点*/ struct Node *rchild; /*指向右孩子结点*/ *BiTree,BitNode

6、;,9.3.3 二叉树的基本运算,采用二叉链表存储结构表示的二叉树的基本运算实现如下所示。以下算法的实现保存在文件“LinkBiTree.h”中。 （1）二叉树的初始化操作。 void InitBitTree(BiTree *T) /*二叉树的初始化操作*/ *T=NULL; ,9.3.3 二叉树的基本运算,（2）二叉树的销毁操作。 void DestroyBitTree(BiTree *T) /*销毁二叉树操作*/ if(*T) /*如果是非空二叉树*/ if(*T)-lchild) DestroyBitTree( ,9.3.3 二叉树的基本运算,（3）创建二叉树操作。 void Creat

7、eBitTree(BiTree *T) /*递归创建二叉树*/ DataType ch; scanf(“%c”, /*构造右子树*/ ,9.3.3 二叉树的基本运算,（4）二叉树的左插入操作。 int InsertLeftChild(BiTree p,BiTree c) /*二叉树的左插入操作*/ if(p) /*如果指针p不空*/ c-rchild=p-lchild; /*p的原来的左子树成为c的右子树*/ p-lchild=c; /*子树c作为p的左子树*/ return 1; return 0; ,9.3.3 二叉树的基本运算,（5）二叉树的右插入操作。 int InsertRightC

8、hild(BiTree p,BiTree c) /*二叉树的右插入操作*/ if(p) /*如果指针p不空*/ c-rchild=p-rchild; /*p的原来的右子树作为c的右子树*/ p-rchild=c; /*子树c作为p的右子树*/ return 1; return 0; ,9.3.3 二叉树的基本运算,（6）返回二叉树结点的指针操作。 （7）返回二叉树的结点的左孩子元素值操作。 （8）返回二叉树的结点的右孩子元素值操作。 （9二叉树的左删除操作。 （10）二叉树的右删除操作。,9.4 二叉树的遍历,在二叉树的应用中，常常需要对二叉树中每个结点进行访问，即二叉树的遍历。本节的主要学习

9、内容包括二叉树的先序遍历、二叉树的中序遍历及二叉树的后序遍历。,9.4.1 二叉树遍历的定义,二叉树的遍历，即按照某种规律对二叉树的每个结点进行访问，使得每个结点仅被访问一次的操作。这里的访问，可以是对结点的输出、统计结点的个数等。 二叉树的遍历过程其实也是将二叉树的非线性序列转换成一个线性序列的过程。二叉树是一种非线性的结构，通过遍历二叉树，按照某种规律对二叉树中的每个结点进行访问，且仅访问一次，得到一个顺序序列。,9.4.2 二叉树的先序遍历,二叉树的先序遍历的递归定义如下： 如果二叉树为空，则执行空操作。如果二叉树非空，则执行以下操作： （1）访问根结点。 （2）先序遍历左子树。 （3）

10、先序遍历右子树。,9.4.2 二叉树的先序遍历,最后得到结点A的左子树先序序列：B、D、G、E、H、I、C、F、J。,9.4.2 二叉树的先序遍历,void PreOrderTraverse(BiTree T) /*先序遍历二叉树的递归实现*/ if(T)/*如果二叉树不为空*/ printf(“%2c”,T-data); /*访问根结点*/ PreOrderTraverse(T-lchild);/*先序遍历左子树*/ PreOrderTraverse(T-rchild); /*先序遍历右子树*/ ,9.4.2 二叉树的先序遍历,先序遍历的非递归实现,9.4.3 二叉树的中序遍历,二叉树的中序

11、遍历的递归定义如下： 如果二叉树为空，则执行空操作。如果二叉树非空，则执行以下操作： （1）中序遍历左子树。 （2）访问根结点。 （3）中序遍历右子树。,9.4.3 二叉树的中序遍历,二叉树的中序序列为：D、G、B、H、E、I、A、F、J、C。,9.4.3 二叉树的中序遍历,void InOrderTraverse(BiTree T) /*中序遍历二叉树的递归实现*/ if(T)/*如果二叉树不为空*/ InOrderTraverse(T-lchild);/*中序遍历左子树*/ printf(“%2c”,T-data); /*访问根结点*/ InOrderTraverse(T-rchild);

12、 /*中序遍历右子树*/ ,9.4.3 二叉树的中序遍历,二叉树的中序遍历非递归算法实现,9.4.4 二叉树的后序遍历,二叉树的后序遍历的递归定义如下： 如果二叉树为空，则执行空操作。如果二叉树非空，则执行以下操作： （1）后序遍历左子树。 （2）后序遍历右子树。 （3）访问根结点。,9.4.4 二叉树的后序遍历,二叉树的后序序列为：G、D、H、I、E、B、J、F、C、A。,9.4.4 二叉树的后序遍历,void PostOrderTraverse(BiTree T) /*后序遍历二叉树的递归实现*/ if(T)/*如果二叉树不为空*/ PostOrderTraverse(T-lchild);

13、/*后序遍历左子树*/ PostOrderTraverse(T-rchild); /*后序遍历右子树*/ printf(“%2c”,T-data); /*访问根结点*/ ,9.4.4 二叉树的后序遍历,后序遍历的非递归实现,9.5 二叉树的遍历的应用举例,二叉树的遍历应用非常广泛，本节主要通过几个例子来说明二叉树遍历的典型应用。本节的主要学习内容包括利用二叉树的遍历思想，进行二叉树的创建、二叉树的输出、二叉树的结点的计数。,9.5.1 二叉树的创建,例9_1 编写算法，创建一个如图9.16所示的二叉树，并按照先序遍历、中序遍历和后序遍历的方式输出二叉树的每个结点的值。 1创建二叉树 2测试代码

14、部分,9.5.2 二叉树的输出,二叉树的打印输出方式，除了按照先序遍历、中序遍历和后序遍历的输出方式外，还有按照层次输出和树状输出的方式。下面具体介绍这两种输出方式的实现算法。,9.5.2 二叉树的输出,例9_2 创建一个二叉树，并按照层次输出二叉树的每个结点，并按照树状打印二叉树。例如，一棵二叉树如图9.22所示，按照层次输出的序列为：A、B、C、D、E、F、G、H、I，按照树状输出的二叉树如图9.23所示。 1按层次输出二叉树的结点 2按树状打印二叉树 3测试代码部分,9.5.2 二叉树的输出,9.5.2 二叉树的输出,按层次输出结点程序流程图,9.5.3 二叉树的计数,二叉树的遍历也常常

15、用来对二叉树进行计数。下面通过实例说明统计二叉树的叶子结点数目、非叶子结点数目等应用。 1统计二叉树的叶子结点个数 2统计二叉树的非叶子结点个数 3计算二叉树的深度 4测试代码部分,9.5.3 二叉树的计数,例9_3 创建一个二叉树，计算二叉树的叶子结点数目、非叶子结点数目和二叉树的深度。例如，图9.26所示的二叉树的叶子结点数目为5个，非叶子结点数目为7个，深度为5。,9.5.3 二叉树的计数,1统计二叉树的叶子结点个数,9.5.3 二叉树的计数,2统计二叉树的非叶子结点个数,9.5.3 二叉树的计数,3计算二叉树的深度,9.6 二叉树的线索化,在二叉树中，采用二叉链表作为存储结构，只能找到

16、结点的左孩子结点和右孩子结点，不能找到该结点的直接前驱结点和后继结点信息。要找到结点的直接前驱或者直接后继，必须对二叉树进行遍历，,9.6.1 二叉树的线索化定义,为了能够在二叉树的遍历过程中，直接能够找到结点的直接前驱结点或者直接后继结点，可以在结点的定义中再增加两个指针域：一个用来指示结点的前驱，另一个用来指向结点的后继。 在二叉链表的存储结构中，具有n个结点的二叉链表有n+1个空指针域（根据二叉树的分支特点可以证明）。由此，可以利用这些空指针域存放结点的直接前驱和直接后继的信息。,9.6.1 二叉树的线索化定义,9.6.1 二叉树的线索化定义,typedef enum Link,Thre

17、adPointerTag; /*Link=0表示指向孩子结点，Thread=1表示指向前驱结点或后继结点*/ typedef struct Node/*线索二叉树存储结构类型定义*/ DataType data; /*数据域*/ struct Node *lchild,rchild; /*指向左孩子结点的指针和右孩子结点的指针*/ PointerTag ltag,rtag; /*标志域*/ *BiThrTree,BiThrNode;,9.6.2 二叉树的线索化,二叉树的线索化就是利用二叉树中结点的空指针域表示结点的前驱或后继信息。而要得到结点的前驱信息和后继信息，需要对二叉树进行遍历，同时将结

18、点的空指针域修改为其直接前驱或直接后继信息。因此，二叉树的线索化就是对二叉树的遍历过程。,9.6.2 二叉树的线索化,9.6.3 线索二叉树的遍历,1查找指定结点的中序直接前驱 2查找指定结点的中序直接后继 3中序遍历线索二叉树,9.6.4 线索二叉树的应用举例,例9_4 建立如图9.30所示的二叉树，并将其中序线索化。任给一个结点，找到结点的中序前驱和中序后继。例如，结点D的中序直接前驱是G，其中序直接后继是A。 1二叉树的线索化 2测试代码部分,9.7 树、森林与二叉树,树、森林和二叉树本身都是树的一种，它们之间是可以相互转换的。本节的主要学习内容包括树的存储结构、森林与二叉树的转换、树与

19、森林的遍历。,9.7.1 树的存储结构,1双亲表示法,9.7.1 树的存储结构,树的双亲表示法存储表示描述如下。 #define MaxSize 200 typedef struct PNode/*双亲表示法的结点定义*/ DataType data; int parent; /*指示结点的双亲*/ PNode; typedef struct/*双亲表示法的类型定义*/ PNode nodeMaxSize; int num; /*结点的个数*/ PTree;,9.7.1 树的存储结构,2孩子表示法,9.7.1 树的存储结构,树的孩子表示法的类型定义如下。 #define MaxSize 200

20、 typedef struct CNode/*孩子结点的类型定义*/ int child; struct CNode*next; /*指向下一个结点*/ ChildNode; typedef struct/*n个结点数据与孩子链表的指针构成一个结构*/ DataType data; ChildNode *firstchild; /*孩子链表的指针*/ DataNode; typedef struct/*孩子表示法类型定义*/ DataNode nodeMaxSize; int num,root; /*结点的个数，根结点在顺序表中的位置*/ CTree;,9.7.1 树的存储结构,3孩子兄弟表示

21、法,9.7.1 树的存储结构,树的孩子兄弟表示法的类型定义如下。 typedef struct CSNode/*孩子兄弟表示法的类型定义*/ DataType data; struct CSNode*firstchild,*nextsibling; /*指向第一个孩子和下一个兄弟*/ CSNode,*CSTree;,9.7.2 树转换为二叉树,从树的孩子兄弟表示和二叉树的二叉链表表示来看，它们在物理上的存储方式是相同的，也就是说，从它们的相同的物理结构可以得到一棵树，也可以得到一棵二叉树。因此，树与二叉树存在着一种对应关系。 树中双亲结点的孩子结点是无序的，二叉树中的左右孩子是有序的。按照以下

22、步骤，可以将一棵树转换为对应的二叉树。 （1）在树中的兄弟结点之间加一条连线。 （2）在树中，只保留双亲结点与第一个孩子结点之间的连线，将双亲结点与其它孩子结点的连线删除。 （3）将树中的各个分支，以某个结点为中心进行旋转，子树以根结点成对称形状。,9.7.2 树转换为二叉树,9.7.2 树转换为二叉树,9.7.3 森林转换为二叉树,森林是由若干棵树组成的集合，树可以转换为二叉树，那么森林也可以转换为对应的二叉树。森林转换为对应的二叉树的步骤如下： （1）把森林中的所有树都转换为对应的二叉树。 （2）从第二棵树开始，将转换后的二叉树作为前一棵树根结点的右孩子，插入到前一棵树中。然后将转换后的二

23、叉树进行相应的旋转。,9.7.3 森林转换为二叉树,9.7.4 二叉树转换为树和森林,二叉树转换为树或者森林，就是将树和森林转换为二叉树的逆过程。将一棵二叉树转换为树或者森林的步骤如下： （1）在二叉树中，将某结点的所有右孩子结点、右孩子的右孩子结点都与该结点的双亲结点用线条连接。 （2）删除掉二叉树中双亲结点与右孩子结点的原来的连线。 （3）调整转换后的树或森林，使结点的所有孩子结点处于同一层次。,9.7.4 二叉树转换为树和森林,9.7.5 树和森林的遍历,1树的遍历 2森林的遍历,9.8 哈夫曼树,哈夫曼树，也称最优二叉树。它是一种带权路径长度最短的树，应用非常广泛。本节的主要学习内容包

24、括哈夫曼树的定义、哈夫曼编码及哈夫曼编码算法的实现。,9.8.1 哈夫曼树的定义,1路径和路径长度 2树的带权路径长度 3哈夫曼树,9.8.1 哈夫曼树的定义,例如，假设给定一组权值1,3,6,9，按照哈夫曼构造的算法对集合的权重构造哈夫曼树的过程如图9.42所示。,9.8.2 哈夫曼编码,哈夫曼编码常应用在数据通信中，在数据传送时，需要将字符转换为二进制的字符串。 在传送电文时，希望电文的代码尽可能的短。如果按照每个字符进行长度不等进行编码，将出现频率高的字符采用尽可能短的编码，则电文的代码长度就会减少。,9.8.3 哈夫曼编码算法的实现,下面利用哈夫曼编码的设计思想，通过一个实例实现哈夫曼编码的算法实现。 例9_5 假设一个字符序列为A