《树零基础学数据结构.pptx》由会员分享，可在线阅读，更多相关《树零基础学数据结构.pptx（84页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、9.1 9.1 树树树是一种非线性的数据结构，树中的元素之间的关系是一对多的层次关系。本节主要介绍树的定义和树的抽象数据类型。第1页/共84页9.1.1 9.1.1 树的定义树的定义树是n(n0)个结点的有限序列。其中，n=0时，称为空树。当n0时，称为非空树，满足以下条件：（1）有且只有一个称为根的结点。（2）当n1时，其余n-1个结点可以划分为m个有限集合T1，T2，Tm，且这m个有限集合不相交，其中Ti（1im）又是一棵树，称为根的子树。第2页/共84页9.1.2 9.1.2 树的逻辑表示树的逻辑表示树的逻辑表示方法可以分为四种：树形表示法、文氏图表示法、广义表表示法和凹入表示法。第3页
2、/共84页9.1.2 9.1.2 树的抽象数据类型树的抽象数据类型1数据对象集合2基本操作集合第4页/共84页9.2 9.2 二叉树二叉树在对一般树进行深入的学习之前，先学习一下一种比较简单的树二叉树。本节的主要学习内容包括二叉树的定义、基本性质及二叉树的抽象数据类型。第5页/共84页9.2.1 9.2.1 二叉树的定义二叉树的定义二叉树是由n(n0)个结点构成的另外一种树结构。二叉树中的每个结点最多只有两棵子树，并且二叉树中的每个结点都有左右次序之分，即次序不能颠倒。第6页/共84页9.2.1 9.2.1 二叉树的定义二叉树的定义第7页/共84页9.2.2 9.2.2 二叉树的性质二叉树的性
3、质二叉树具有以下重要的性质。l性质1 在二叉树中，第m(m1)层上至多有2m-1个结点（规定根结点为第一层）。l性质2 深度为k(k1)的二叉树至多有2k-1个结点。l性质3 对任何一棵二叉树T，如果叶子结点总数为n0，度为2的结点总数为n2，则有n0=n2+1。l性质4 如果完全二叉树有n个结点，则深度为 。符号 表示不大于x的最大整数。l性质5 如果完全二叉树有n个结点，按照从上到下，从左到右的顺序对二叉树中的每个结点从1到n进行编号，则对于任意结点i有以下性质：第8页/共84页9.2.2 9.2.2 二叉树的性质二叉树的性质（1）如果i=1，则序号i对应的结点就是根结点，该结点没有双亲结
4、点。（2）如果2in，则序号为i的结点没有左孩子结点。（3）如果2i+1n，则序号为i的结点没有右孩子结点。第9页/共84页9.2.3 9.2.3 二叉树的抽象数据类型二叉树的抽象数据类型1数据对象集合2基本操作集合第10页/共84页9.3 9.3 二叉树的存储表示与实现二叉树的存储表示与实现二叉树的存储结构有两种：顺序存储表示和链式存储表示。本节的主要学习内容包括二叉树的顺序存储表示、二叉树的链式存储表示及二叉树的基本操作实现。第11页/共84页9.3.1 9.3.1 二叉树的顺序存储二叉树的顺序存储我们已经知道，完全二叉树中每个结点的编号可以通过公式计算得到，因此，完全二叉树的存储可以按照
5、从上到下、从左到右的顺序依次存储在一维数组中。第12页/共84页9.3.1 9.3.1 二叉树的顺序存储二叉树的顺序存储第13页/共84页9.3.2 9.3.2 二叉树的链式存储二叉树的链式存储在二叉树中，每个结点有一个双亲结点和两个孩子结点。从一棵二叉树的根结点开始，通过结点的左右孩子地址就可以找到二叉树的每一个结点。因此二叉树的链式存储结构包括三个域：数据域、左孩子指针域和右孩子指针域。其中，数据域存放结点的值，左孩子指针域指向左孩子结点，右孩子指针域指向右孩子的结点。第14页/共84页9.3.2 9.3.2 二叉树的链式存储二叉树的链式存储第15页/共84页9.3.2 9.3.2 二叉树
6、的链式存储二叉树的链式存储二叉链表存储结构的类型定义描述如下：typedef struct Node/*二叉链表存储结构类型定义*/DataType data;/*数据域*/struct Node*lchild;/*指向左孩子结点*/struct Node*rchild;/*指向右孩子结点*/*BiTree,BitNode;第16页/共84页9.3.3 9.3.3 二叉树的基本运算二叉树的基本运算采用二叉链表存储结构表示的二叉树的基本运算实现如下所示。以下算法的实现保存在文件“LinkBiTree.h”中。（1）二叉树的初始化操作。void InitBitTree(BiTree*T)/*二叉树
7、的初始化操作*/*T=NULL;第17页/共84页9.3.3 9.3.3 二叉树的基本运算二叉树的基本运算（2）二叉树的销毁操作。void DestroyBitTree(BiTree*T)/*销毁二叉树操作*/if(*T)/*如果是非空二叉树*/if(*T)-lchild)DestroyBitTree(&(*T)-lchild);if(*T)-rchild)DestroyBitTree(&(*T)-rchild);free(*T);*T=NULL;第18页/共84页9.3.3 9.3.3 二叉树的基本运算二叉树的基本运算（3）创建二叉树操作。void CreateBitTree(BiTree*
8、T)/*递归创建二叉树*/DataType ch;scanf(“%c”,&ch);if(ch=#)*T=NULL;else *T=(BiTree)malloc(sizeof(BitNode);/*生成根结点*/if(!(*T)exit(-1);(*T)-data=ch;CreateBitTree(&(*T)-lchild);/*构造左子树*/CreateBitTree(&(*T)-rchild);/*构造右子树*/第19页/共84页9.3.3 9.3.3 二叉树的基本运算二叉树的基本运算（4）二叉树的左插入操作。int InsertLeftChild(BiTree p,BiTree c)/*二
9、叉树的左插入操作*/if(p)/*如果指针p不空*/c-rchild=p-lchild;/*p的原来的左子树成为c的右子树*/p-lchild=c;/*子树c作为p的左子树*/return 1;return 0;第20页/共84页9.3.3 9.3.3 二叉树的基本运算二叉树的基本运算（5）二叉树的右插入操作。int InsertRightChild(BiTree p,BiTree c)/*二叉树的右插入操作*/if(p)/*如果指针p不空*/c-rchild=p-rchild;/*p的原来的右子树作为c的右子树*/p-rchild=c;/*子树c作为p的右子树*/return 1;retur
10、n 0;第21页/共84页9.3.3 9.3.3 二叉树的基本运算二叉树的基本运算（6）返回二叉树结点的指针操作。（7）返回二叉树的结点的左孩子元素值操作。（8）返回二叉树的结点的右孩子元素值操作。（9二叉树的左删除操作。（10）二叉树的右删除操作。第22页/共84页9.4 9.4 二叉树的遍历二叉树的遍历在二叉树的应用中，常常需要对二叉树中每个结点进行访问，即二叉树的遍历。本节的主要学习内容包括二叉树的先序遍历、二叉树的中序遍历及二叉树的后序遍历。第23页/共84页9.4.1 9.4.1 二叉树遍历的定义二叉树遍历的定义二叉树的遍历，即按照某种规律对二叉树的每个结点进行访问，使得每个结点仅被
11、访问一次的操作。这里的访问，可以是对结点的输出、统计结点的个数等。二叉树的遍历过程其实也是将二叉树的非线性序列转换成一个线性序列的过程。二叉树是一种非线性的结构，通过遍历二叉树，按照某种规律对二叉树中的每个结点进行访问，且仅访问一次，得到一个顺序序列。第24页/共84页9.4.2 9.4.2 二叉树的先序遍历二叉树的先序遍历二叉树的先序遍历的递归定义如下：如果二叉树为空，则执行空操作。如果二叉树非空，则执行以下操作：（1）访问根结点。（2）先序遍历左子树。（3）先序遍历右子树。第25页/共84页9.4.2 9.4.2 二叉树的先序遍历二叉树的先序遍历最后得到结点A的左子树先序序列：B、D、G、
12、E、H、I、C、F、J。第26页/共84页9.4.2 9.4.2 二叉树的先序遍历二叉树的先序遍历void PreOrderTraverse(BiTree T)/*先序遍历二叉树的递归实现*/if(T)/*如果二叉树不为空*/printf(“%2c”,T-data);/*访问根结点*/PreOrderTraverse(T-lchild);/*先序遍历左子树*/PreOrderTraverse(T-rchild);/*先序遍历右子树*/第27页/共84页9.4.2 9.4.2 二叉树的先序遍历二叉树的先序遍历先序遍历的非递归实现第28页/共84页9.4.3 9.4.3 二叉树的中序遍历二叉树的中
13、序遍历二叉树的中序遍历的递归定义如下：如果二叉树为空，则执行空操作。如果二叉树非空，则执行以下操作：（1）中序遍历左子树。（2）访问根结点。（3）中序遍历右子树。第29页/共84页9.4.3 9.4.3 二叉树的中序遍历二叉树的中序遍历二叉树的中序序列为：D、G、B、H、E、I、A、F、J、C。第30页/共84页9.4.3 9.4.3 二叉树的中序遍历二叉树的中序遍历void InOrderTraverse(BiTree T)/*中序遍历二叉树的递归实现*/if(T)/*如果二叉树不为空*/InOrderTraverse(T-lchild);/*中序遍历左子树*/printf(“%2c”,T-
14、data);/*访问根结点*/InOrderTraverse(T-rchild);/*中序遍历右子树*/第31页/共84页9.4.3 9.4.3 二叉树的中序遍历二叉树的中序遍历二叉树的中序遍历非递归算法实现 第32页/共84页9.4.4 9.4.4 二叉树的后序遍历二叉树的后序遍历二叉树的后序遍历的递归定义如下：如果二叉树为空，则执行空操作。如果二叉树非空，则执行以下操作：（1）后序遍历左子树。（2）后序遍历右子树。（3）访问根结点。第33页/共84页9.4.4 9.4.4 二叉树的后序遍历二叉树的后序遍历二叉树的后序序列为：G、D、H、I、E、B、J、F、C、A。第34页/共84页9.4.
15、4 9.4.4 二叉树的后序遍历二叉树的后序遍历void PostOrderTraverse(BiTree T)/*后序遍历二叉树的递归实现*/if(T)/*如果二叉树不为空*/PostOrderTraverse(T-lchild);/*后序遍历左子树*/PostOrderTraverse(T-rchild);/*后序遍历右子树*/printf(“%2c”,T-data);/*访问根结点*/第35页/共84页9.4.4 9.4.4 二叉树的后序遍历二叉树的后序遍历后序遍历的非递归实现第36页/共84页9.5 9.5 二叉树的遍历的应用举例二叉树的遍历的应用举例二叉树的遍历应用非常广泛，本节主要
16、通过几个例子来说明二叉树遍历的典型应用。本节的主要学习内容包括利用二叉树的遍历思想，进行二叉树的创建、二叉树的输出、二叉树的结点的计数。第37页/共84页9.5.1 9.5.1 二叉树的创建二叉树的创建例9_1 编写算法，创建一个如图9.16所示的二叉树，并按照先序遍历、中序遍历和后序遍历的方式输出二叉树的每个结点的值。1创建二叉树2测试代码部分第38页/共84页9.5.2 9.5.2 二叉树的输出二叉树的输出二叉树的打印输出方式，除了按照先序遍历、中序遍历和后序遍历的输出方式外，还有按照层次输出和树状输出的方式。下面具体介绍这两种输出方式的实现算法。第39页/共84页9.5.2 9.5.2
17、二叉树的输出二叉树的输出例9_2 创建一个二叉树，并按照层次输出二叉树的每个结点，并按照树状打印二叉树。例如，一棵二叉树如图9.22所示，按照层次输出的序列为：A、B、C、D、E、F、G、H、I，按照树状输出的二叉树如图9.23所示。1按层次输出二叉树的结点2按树状打印二叉树3测试代码部分第40页/共84页9.5.2 9.5.2 二叉树的输出二叉树的输出第41页/共84页9.5.2 9.5.2 二叉树的输出二叉树的输出按层次输出结点程序流程图第42页/共84页9.5.3 9.5.3 二叉树的计数二叉树的计数二叉树的遍历也常常用来对二叉树进行计数。下面通过实例说明统计二叉树的叶子结点数目、非叶子
18、结点数目等应用。1统计二叉树的叶子结点个数2统计二叉树的非叶子结点个数3计算二叉树的深度4测试代码部分第43页/共84页9.5.3 9.5.3 二叉树的计数二叉树的计数例9_3 创建一个二叉树，计算二叉树的叶子结点数目、非叶子结点数目和二叉树的深度。例如，图9.26所示的二叉树的叶子结点数目为5个，非叶子结点数目为7个，深度为5。第44页/共84页9.5.3 9.5.3 二叉树的计数二叉树的计数1统计二叉树的叶子结点个数第45页/共84页9.5.3 9.5.3 二叉树的计数二叉树的计数2统计二叉树的非叶子结点个数第46页/共84页9.5.3 9.5.3 二叉树的计数二叉树的计数3计算二叉树的深
19、度第47页/共84页9.6 9.6 二叉树的线索化二叉树的线索化在二叉树中，采用二叉链表作为存储结构，只能找到结点的左孩子结点和右孩子结点，不能找到该结点的直接前驱结点和后继结点信息。要找到结点的直接前驱或者直接后继，必须对二叉树进行遍历，第48页/共84页9.6.1 9.6.1 二叉树的线索化定义二叉树的线索化定义为了能够在二叉树的遍历过程中，直接能够找到结点的直接前驱结点或者直接后继结点，可以在结点的定义中再增加两个指针域：一个用来指示结点的前驱，另一个用来指向结点的后继。在二叉链表的存储结构中，具有n个结点的二叉链表有n+1个空指针域（根据二叉树的分支特点可以证明）。由此，可以利用这些空
20、指针域存放结点的直接前驱和直接后继的信息。第49页/共84页9.6.1 9.6.1 二叉树的线索化定义二叉树的线索化定义第50页/共84页9.6.1 9.6.1 二叉树的线索化定义二叉树的线索化定义typedef enum Link,ThreadPointerTag;/*Link=0 表示指向孩子结点，Thread=1表示指向前驱结点或后继结点*/typedef struct Node/*线索二叉树存储结构类型定义*/DataType data;/*数据域*/struct Node*lchild,rchild;/*指向左孩子结点的指针和右孩子结点的指针*/PointerTag ltag,rta
21、g;/*标志域*/*BiThrTree,BiThrNode;第51页/共84页9.6.2 9.6.2 二叉树的线索化二叉树的线索化二叉树的线索化就是利用二叉树中结点的空指针域表示结点的前驱或后继信息。而要得到结点的前驱信息和后继信息，需要对二叉树进行遍历，同时将结点的空指针域修改为其直接前驱或直接后继信息。因此，二叉树的线索化就是对二叉树的遍历过程。第52页/共84页9.6.2 9.6.2 二叉树的线索化二叉树的线索化第53页/共84页9.6.3 9.6.3 线索二叉树的遍历线索二叉树的遍历1查找指定结点的中序直接前驱2查找指定结点的中序直接后继3中序遍历线索二叉树第54页/共84页9.6.4
22、 9.6.4 线索二叉树的应用举例线索二叉树的应用举例例9_4 建立如图9.30所示的二叉树，并将其中序线索化。任给一个结点，找到结点的中序前驱和中序后继。例如，结点D的中序直接前驱是G，其中序直接后继是A。1二叉树的线索化2测试代码部分第55页/共84页9.7 9.7 树、森林与二叉树树、森林与二叉树树、森林和二叉树本身都是树的一种，它们之间是可以相互转换的。本节的主要学习内容包括树的存储结构、森林与二叉树的转换、树与森林的遍历。第56页/共84页9.7.1 9.7.1 树的存储结构树的存储结构1双亲表示法第57页/共84页9.7.1 9.7.1 树的存储结构树的存储结构树的双亲表示法存储表
23、示描述如下。#define MaxSize 200typedef struct PNode/*双亲表示法的结点定义*/DataType data;int parent;/*指示结点的双亲*/PNode;typedef struct/*双亲表示法的类型定义*/PNode nodeMaxSize;int num;/*结点的个数*/PTree;第58页/共84页9.7.1 9.7.1 树的存储结构树的存储结构2孩子表示法第59页/共84页9.7.1 9.7.1 树的存储结构树的存储结构树的孩子表示法的类型定义如下。#define MaxSize 200typedef struct CNode/*孩子
24、结点的类型定义*/int child;struct CNode*next;/*指向下一个结点*/ChildNode;typedef struct/*n个结点数据与孩子链表的指针构成一个结构*/DataType data;ChildNode*firstchild;/*孩子链表的指针*/DataNode;typedef struct/*孩子表示法类型定义*/DataNode nodeMaxSize;int num,root;/*结点的个数，根结点在顺序表中的位置*/CTree;第60页/共84页9.7.1 9.7.1 树的存储结构树的存储结构3孩子兄弟表示法第61页/共84页9.7.1 9.7.1
25、 树的存储结构树的存储结构树的孩子兄弟表示法的类型定义如下。typedef struct CSNode/*孩子兄弟表示法的类型定义*/DataType data;struct CSNode*firstchild,*nextsibling;/*指向第一个孩子和下一个兄弟*/CSNode,*CSTree;第62页/共84页9.7.2 9.7.2 树转换为二叉树树转换为二叉树从树的孩子兄弟表示和二叉树的二叉链表表示来看，它们在物理上的存储方式是相同的，也就是说，从它们的相同的物理结构可以得到一棵树，也可以得到一棵二叉树。因此，树与二叉树存在着一种对应关系。树中双亲结点的孩子结点是无序的，二叉树中的左
26、右孩子是有序的。按照以下步骤，可以将一棵树转换为对应的二叉树。（1）在树中的兄弟结点之间加一条连线。（2）在树中，只保留双亲结点与第一个孩子结点之间的连线，将双亲结点与其它孩子结点的连线删除。（3）将树中的各个分支，以某个结点为中心进行旋转，子树以根结点成对称形状。第63页/共84页9.7.2 9.7.2 树转换为二叉树树转换为二叉树第64页/共84页9.7.2 9.7.2 树转换为二叉树树转换为二叉树第65页/共84页9.7.3 9.7.3 森林转换为二叉树森林转换为二叉树森林是由若干棵树组成的集合，树可以转换为二叉树，那么森林也可以转换为对应的二叉树。森林转换为对应的二叉树的步骤如下：（1
27、）把森林中的所有树都转换为对应的二叉树。（2）从第二棵树开始，将转换后的二叉树作为前一棵树根结点的右孩子，插入到前一棵树中。然后将转换后的二叉树进行相应的旋转。第66页/共84页9.7.3 9.7.3 森林转换为二叉树森林转换为二叉树第67页/共84页9.7.4 9.7.4 二叉树转换为树和森林二叉树转换为树和森林二叉树转换为树或者森林，就是将树和森林转换为二叉树的逆过程。将一棵二叉树转换为树或者森林的步骤如下：（1）在二叉树中，将某结点的所有右孩子结点、右孩子的右孩子结点都与该结点的双亲结点用线条连接。（2）删除掉二叉树中双亲结点与右孩子结点的原来的连线。（3）调整转换后的树或森林，使结点的
28、所有孩子结点处于同一层次。第68页/共84页9.7.4 9.7.4 二叉树转换为树和森林二叉树转换为树和森林第69页/共84页9.7.5 9.7.5 树和森林的遍历树和森林的遍历1树的遍历2森林的遍历第70页/共84页9.8 9.8 哈夫曼树哈夫曼树哈夫曼树，也称最优二叉树。它是一种带权路径长度最短的树，应用非常广泛。本节的主要学习内容包括哈夫曼树的定义、哈夫曼编码及哈夫曼编码算法的实现。第71页/共84页9.8.1 9.8.1 哈夫曼树的定义哈夫曼树的定义1路径和路径长度2树的带权路径长度3哈夫曼树第72页/共84页9.8.1 9.8.1 哈夫曼树的定义哈夫曼树的定义例如，假设给定一组权值1
29、,3,6,9，按照哈夫曼构造的算法对集合的权重构造哈夫曼树的过程如图9.42所示。第73页/共84页9.8.2 9.8.2 哈夫曼编码哈夫曼编码哈夫曼编码常应用在数据通信中，在数据传送时，需要将字符转换为二进制的字符串。在传送电文时，希望电文的代码尽可能的短。如果按照每个字符进行长度不等进行编码，将出现频率高的字符采用尽可能短的编码，则电文的代码长度就会减少。第74页/共84页9.8.3 9.8.3 哈夫曼编码算法的实现哈夫曼编码算法的实现下面利用哈夫曼编码的设计思想，通过一个实例实现哈夫曼编码的算法实现。例9_5 假设一个字符序列为A,B,C,D，对应的权重为1,3,6,9。设计一个哈夫曼树
30、，并输出相应的哈夫曼编码。第75页/共84页9.8.3 9.8.3 哈夫曼编码算法的实现哈夫曼编码算法的实现typedef struct/*哈夫曼树类型定义*/unsigned int weight;unsigned int parent,lchild,rchild;HTNode,*HuffmanTree;typedef char*HuffmanCode;/*存放哈夫曼编码*/第76页/共84页9.8.3 9.8.3 哈夫曼编码算法的实现哈夫曼编码算法的实现1哈夫曼编码的实现2查找权值最小和次小的两个结点3测试代码部分第77页/共84页9.9 9.9 树与二叉树的应用举例树与二叉树的应用举例本
31、节将通过几个具体实例来说明二叉树与树的使用。本节的主要学习内容包括相似二叉树、由二叉树的先序和中序序列确定一棵二叉树、树的孩子兄弟表示法。第78页/共84页9.9.1 9.9.1 相似二叉树相似二叉树相似二叉树指的是二叉树的结构相似。假设存在两棵二叉树T1和T2，T1和T2都是空二叉树或者T1和T2都不为空树，且T1和T2的左、右子树的结构分别相似。则称T1和T2是相似二叉树。第79页/共84页9.9.2 9.9.2 由先序和中序、中序和后序确定二叉树由先序和中序、中序和后序确定二叉树1由先序序列和中序序列确定一棵二叉树2由中序序列和后序序列确定一棵二叉树3程序举例第80页/共84页9.9.2
32、 9.9.2 由先序和中序、中序和后序确定二叉树由先序和中序、中序和后序确定二叉树第81页/共84页9.9.3 9.9.3 树的孩子兄弟链表应用举例树的孩子兄弟链表应用举例例9_7 利用孩子兄弟表示法创建一棵树，对树进行层次遍历、先序遍历，并求出树的深度。1孩子兄弟链表的相关操作2测试代码部分第82页/共84页9.10 9.10 小结小结本章主要介绍了一种非线性的数据结构树。树在数据结构中占据着非常重要的地位，树反映的是一种层次结构的关系。在树中，每个结点只允许有一个直接前驱结点，允许有多个直接后继结点，结点与结点之间是一种一对多的关系。树的定义是递归的。一棵树或者为空，或者是由m棵子树T1，T2，Tm组成，这m棵子树又是由其它子树构成。树中的孩子结点没有次序之分，是一种无序树。第83页/共84页感谢您的观看！第84页/共84页