《数据结构 教学课件 ppt 作者 方风波 王巧莲 主编 黄鹤鸣 副主编 第六章 树》由会员分享，可在线阅读，更多相关《数据结构 教学课件 ppt 作者 方风波 王巧莲 主编 黄鹤鸣 副主编 第六章 树（79页珍藏版）》请在金锄头文库上搜索。
1、第六章 树,数据结构,第六章 树,第六章 树,知 识 点 二叉树及二叉树的存储结构 二叉树的遍历 树的基本概念 二叉排序树 哈夫曼树 难 点 二叉树遍历算法的设计 修改二叉树遍历算法，进行二叉树其它相关的操作，解决实际应用问题,要 求 熟练掌握以下内容: 理解树形结构的基本概念和术语 二叉树定义和存储结构 二叉树的遍历次序及二叉树遍历算法 了解以下内容： 树和二叉树之间的相互转换方法 线索二叉树的建立及遍历算法 树的应用：二叉排序树和哈夫曼树,第六章目录,6.1 树的定义和基本术语 6.2 二叉树 6.3 二叉树的遍历 6.4 树的应用 6.5 应用实例及分析 小 结 习题与练习,6.1.1
2、树的定义,树是n个结点的有限集合T，在一棵非空树中（n0）有且仅有一个称作根的结点；其余结点可分为m个（m0）互不相交的集合T1，T2Tm，其中，每一个集合本身又是一棵树,并称为根的子树。 当n=0时，称为空树。 有限集合T1，T2Tm应该“互不相交”，即任意两个集合不能有相重的结点。 树的各个结点有不同层次关系，这种关系通常用图形表示，但与自然界的树木相反，习惯上将整棵树的根画在最上层，如图5.1所示。,图6.1 树的表示法,6.1.2 基本术语,1. 结点的度：树中每个结点具有的子树数或者后继结点数称为该结点的度（Degree）。度数为0的结点，即没有子树的结点叫作端结点或叶子结点。一棵树
3、中各个结点度数的最大值叫做这个树的度。 2. 儿子结点和父亲结点：一个结点的子树的根或者后继结点称为该结点的儿子结点，反之，该结点则称为其后继结点的父亲结点。 3. 兄弟结点：同一个结点的儿子结点之间互称为兄弟结点。,4. 子孙结点和祖先结点：一个结点的子树中所有结点均称之为该结点的子孙结点。反之，从根结点到达一个结点的路径上的所有结点，都叫做该结点的祖先结点。 5. 树的深度：树是一种层次结构，树中结点的层次（Level）是从根结点算起的。根结点为第一层，其儿子结点为第二层。其余各结点的层数逐层由上而下计算。一棵树中结点的最大层数叫做此树的深度或高度。 6. 森林：n个树的集合叫森林(For
4、est)。,树形结构的逻辑特征,树形结构的逻辑特征可用树中结点之间的父子关系来描述： 树中任一结点都可以有零个或多个直接后继结点（即儿子结点），但至多只能有一个直接前趋结点（即父亲结点）。 树中只有根结点无前趋，它是开始结点； 叶结点无后继，它们是终端结点。 树形结构是非线性结构。,返回,6.2.1 二叉树的定义及其性质,一个二叉树是n个结点的有限集合（n0），此集合或者是空集（n=0），或者是由一个根结点及两棵互不相交的、分别称为左子树和右子树的二叉树组成。 由上述定义可知，二叉树可以是空集，其根可以有空的左子树或右子树，或者左、右子树皆为空。 一般地，二叉树有五种基本形态，如图5.2所示。
5、,图6.2 二叉树的基本形态,(a) 空二叉树 (b) 仅有一个根结点的二叉树 (c) 右子树为空的二叉树 (d)左子树为空的二叉树 (e)左、右子树均非空的二叉树,1. 满二叉树,在一个二叉树中，若第i层的结点数为2i-1，则称此层的结点数是满的，当树中的每一层都是满的，则称此二叉树为满二叉树。 即如果一个二叉树中，除最下一层的各结点度数为0以外，其它各层结点的度数均等于2，则此二叉树为满二叉树。 满二叉树的第一层有一个结点（即根结点），第二层有两个结点，依此类推。每一层的结点数都是上一层结点数的二倍。所以，在满二叉树的第i层共有2i-1个结点（i1），一个深度为h的满二叉树的结点总数为2h
6、-1。,图6.3 满二叉树,2. 完全二叉树,如果一个二叉树各层都是“满”的，只是最下面一层从右边起连续缺n个结点，这种二叉树叫做完全二叉树。 例如图5.3中的满二叉树，如果缺少从第11号至第15号结点（没有图中虚框里的几个结点），就是一个完全二叉树。 设完全二叉树的结点数为n，它与树的深度之间的关系为： 2h-1-1n 2h-1 即n值大于深度为h-1的满二叉树的结点数，但小于或等于深度为h的满二叉树的结点数。,对于完全二叉树，对其结点采用“按层编号”比较方便，即从根结点开始由上而下逐层给结点编号，同一层的结点由左向右编号。 对于完全二叉树中任一个编号为i的结点(1in)，它的父结点和左、右
7、儿子结点的编号与i值有如下的关系： 1) 如果i=1，则它是整个树的根结点，无父结点；若i1，则其父结点编号为 。 2) 如果2in，则其左儿子结点编号为2i；若2in，则无左儿子结点。 3) 如果（2i+1）n，则其右儿子结点编号为（2i+1）；反之，则无右儿子结点。,6.2.2 二叉树的存储结构,1. 二叉树的顺序存储结构：用一个一维数组来存储二叉树的各个结点，显然，二叉树的结点必须按某种次序分别存入数组的各个单元，这种次序应能反映结点间的逻辑关系，否则二叉树上的各种基本运算在顺序存储结构上很难实现。 对于完全二叉树来说，可以采用“以编号为地址”的方法，将编号为i的结点存入一维数组的第i个
8、单元。 图6.3所示的完全二叉树按此方法存入数组中如下图5.4所示。,图6.4 二叉树的顺序存储结构,这种存储结构适用于完全二叉树和满二叉树。 如果某二叉树不是完全二叉树，中间有一些结点不存在，则采用顺序存储结构时，数组中必然要有一些空闲单元，对存储空间利用不够。,图6.5 非完全二叉树的顺序表示,图6.5中的二叉树,采用顺序存储结构时,一维数组的21单元中只用上了7个。 2. 二叉树的链式存储结构：对于这种非完全二叉树，采用链式存储结构更合适，如图5.6所示。,结点结构,通常每个结点中设置三个域,即值域、左指针域和右指针域，其结点结构如下： 其中data表示值域，用于存储放入结点的数据，le
9、ft和right分别表示左指针域和右指针域，用以分别存储指向左儿子结点和右儿子结点的指针。,结点定义,链式存储结构的结点定义如下： typedef struct bnode ElemType data; struct bnode *left, *right; btree; 这里的ElemType可以是任何相应的数据类型如int、float或char等。,6.2.3 普通树与二叉树的转换,普通树可用链式存储结构来表示，每个结点包括数据域以及指向它各个儿子结点的指针域。 由于同一树的各结点度数一般并不相同，如按结点的度数给每个结点设置不同数目的指针域，不同结点的数据结构不同，会给算法设计和程序编制
10、造成困难。 如欲令同一树的各结点有相同数据结构，则只能按结点度数最大值（该树的度数）给每个结点设置指针。这样较浪费存储空间。 按照一定的原则将普通树用二叉树来表示，是较好的表示方法。,要把普通树转换为二叉树，就必须找到一种结点与结点之间至多用两个量说明的关系 ：树中每个结点最多只有一个最左边的儿子结点和一个右邻的兄弟结点 。 按照这种关系可以把普通树转换成相应的二叉树，具体方法如下： 1) 在所有兄弟结点之间加一连线； 2) 对每个结点，除了保留与其左儿子结点的连线外，去掉该结点与其它儿子结点的连线。,图6.8 树转化为二叉树,图中所示的树经过变换，可得下面的形式。,得到的已是一棵二叉树，若按
11、顺时针方向将它旋转就更清楚地变为下面所示的二叉树。,由于树根没有兄弟，所以树转换为二叉树后，二叉树的根结点的右子树必为空。,返回,6.3.1 二叉树的遍历,二叉树的遍历(Traversal)是指按一定的规律访问二叉树的每个结点，且每个结点只被访问一次的过程。 对二叉树的遍历过程实际上是将非线性结构的二叉树中的结点排列成一个线性序列的过程。 对于用顺序法表示的二叉树，各结点在数组中的编号很有规律，其遍历较容易进行，但对于用链式存储结构表示的二叉树，进行遍历就复杂一些，故本节仅讨论链式存储形式的二叉树遍历过程。,一个非空的二叉树由根结点及左、右子树这三个基本部分组成，因此若能依次遍历这三部分，便是
12、遍历了整个二叉树。 在任一给定结点上，可以按某种次序执行三个操作：访问结点本身，遍历该结点左子树，遍历该结点右子树，操作排列次序： 左、根、右； 根、左、右； 左、右、根； 右、根、左； 根、右、左； 右、左、根； 由于实际问题一般都是要求左子树较右子树先遍历，故只采用其中、三种遍历次序，分别称为中序遍历、先序遍历和后序遍历。,三种遍历次序以递归的形式定义： (1) 中序（Inorder）遍历 若遍历的二叉树为空，执行空操作；否则依次执行下列操作： 中序遍历左子树； 访问根结点； 中序遍历右子树。 (2) 先序（Preorder）遍历 若遍历的二叉树为空，执行空操作；否则依次执行下列操作： 访
13、问根结点； 先序遍历左子树； 先序遍历右子树。,(3) 后序（Postorder）遍历 若遍历的二叉树为空，执行空操作；否则依次执行下列操作： 后序遍历左子树； 后序遍历右子树； 访问根结点。,图6.9 二叉树遍历,中序遍历序列：H，D，I，B，E，A，F，C，G。 先序遍历序列：A，B，D，H，I，E，C，F，G。 后序遍历序列：H，I，D，E，B，F，G，C，A。,中序遍历递归算法,void inorder(btree *p) if (p！=NULL) inorder(p-left); printf(“%d“,p-data); inorder(p-right); ,6.3.2 二叉树的非递
14、归遍历,可利用堆栈将递归算法改写成非递归的形式。下面以先序遍历为例来具体说明。 图示为二叉树上的任一结点X,以及它的左子树XL和右子树XR。假设t是指向结点X的指针。,非递归先序遍历二叉树上任一结点X的主要操作： (1) 访问结点X； (2) 结点X的右指针进栈； (3) 若XL不空，沿X的左指针遍历XL ； (4) 从栈中取出X的右指针； (5) 若XR不空，沿X的右指针遍历XR 。,先序遍历的非递归算法,void preorder (btree *t) btree stackstacksize; /*定义栈*/ int top=1; stacktop = t; /*将根指针进栈*/ whi
15、le (top0) s = stacktop; /*读栈顶元素到s中*/ top-; while (s!=NULL),先序遍历的非递归算法续, printf (“ %c “,s-data); top+; stacktop = s-rignt; /*右指针进栈*/ s = s-left; /*修改s以继续遍历左子树*/ ,算法分析,内循环条件“s!=NULL”统一处理了三种情况： 第一次执行内循环语句时，s的值为根指针。此时“s!=NULL”意味着二叉树非空，因此接下去的操作是执行内循环体：访问根结点、根结点的右指针进栈保存、修改s为根结点的左指针。 s的值由内循环中的最后一个语句所赋值。这时s
16、指向某结点的左儿子结点。若s!NULL成立，接下去是执行循环体遍历左子树。 当退出内循环时，由外循环中的读栈顶元素语句读出一个结点的右指针送入s，接下去执行的内循环语句实际上是遍历右子树。,返回,6.4.1 二叉排序树,1.二叉排序树的定义 所谓排序，就是将一组杂乱无序的数据按一定的规律顺序排列起来。 对一个二叉树若规定：任一结点如果有左子树，其左子树各结点的数据必须小于该结点的数据；任一结点如果有右子树，其右子树各结点的数据必须等于或大于该结点的数据，按这样规定构成的二叉树叫做二叉排序树。,在一个二叉排序树中，其结点是按左子树、根和右子树的次序有序的，故对二叉排序树进行中序遍历得到的结点序列是一个有序序列。 以整数类型的数据排列为例，设要求将一批正整数按递增的次序排列，若有相同的数据，则按先后次序列出。按二叉排序树要求可将这批正整数构成一个二叉排序树，每个参加排序的数据对应二叉树的一个结点，然后，对这种树进行一次中序遍历，按访问各结点的顺序输
