数据结构 c c++ 第五章 树

《数据结构 c c++ 第五章 树》由会员分享，可在线阅读，更多相关《数据结构 c c++ 第五章 树（59页珍藏版）》请在金锄头文库上搜索。

1、第五章 树,第五章 树,知 识 点 二叉树及二叉树的存储结构 二叉树的遍历 树的基本概念 二叉排序树 哈夫曼树 难 点 二叉树遍历算法的设计 修改二叉树遍历算法，进行二叉树其它相关的操作，解决实际应用问题,要 求 熟练掌握以下内容: 理解树形结构的基本概念和术语 二叉树定义和存储结构 二叉树的遍历次序及二叉树遍历算法 了解以下内容： 树和二叉树之间的相互转换方法 线索二叉树的建立及遍历算法 树的应用：二叉排序树和哈夫曼树,第五章目录,5.1 树的定义和基本术语 5.2 二叉树 5.3 二叉树的遍历 5.4 线索二叉树 5.5 树的应用 5.6 应用实例及分析 小 结 习题与练习,5.1.1 树

2、的定义,树是n个结点的有限集合T，在一棵非空树中（n0）有且仅有一个称作根的结点；其余结点可分为m个（m0）互不相交的集合T1，T2Tm，其中，每一个集合本身又是一棵树,并称为根的子树。 当n=0时，称为空树。 有限集合T1，T2Tm应该“互不相交”，即任意两个集合不能有相重的结点。 树的各个结点有不同层次关系，这种关系通常用图形表示，但与自然界的树木相反，习惯上将整棵树的根画在最上层，如图5.1所示。,图5.1 树的表示法,5.1.2 基本术语,1. 结点的度：树中每个结点具有的子树数或者后继结点数称为该结点的度（Degree）。度数为0的结点，即没有子树的结点叫作端结点或叶子结点。一棵树中

3、各个结点度数的最大值叫做这个树的度。 2. 儿子结点和父亲结点：一个结点的子树的根或者后继结点称为该结点的儿子结点，反之，该结点则称为其后继结点的父亲结点。 3. 兄弟结点：同一个结点的儿子结点之间互称为兄弟结点。,4. 子孙结点和祖先结点：一个结点的子树中所有结点均称之为该结点的子孙结点。反之，从根结点到达一个结点的路径上的所有结点，都叫做该结点的祖先结点。 5. 树的深度：树是一种层次结构，树中结点的层次（Level）是从根结点算起的。根结点为第一层，其儿子结点为第二层。其余各结点的层数逐层由上而下计算。一棵树中结点的最大层数叫做此树的深度或高度。 6. 森林：n个树的集合叫森林(Fore

4、st)。,树形结构的逻辑特征,树形结构的逻辑特征可用树中结点之间的父子关系来描述： 树中任一结点都可以有零个或多个直接后继结点（即儿子结点），但至多只能有一个直接前趋结点（即父亲结点）。 树中只有根结点无前趋，它是开始结点； 叶结点无后继，它们是终端结点。 树形结构是非线性结构。,返回,5.2.1 二叉树的定义及其性质,一个二叉树是n个结点的有限集合（n0），此集合或者是空集（n=0），或者是由一个根结点及两棵互不相交的、分别称为左子树和右子树的二叉树组成。 由上述定义可知，二叉树可以是空集，其根可以有空的左子树或右子树，或者左、右子树皆为空。 一般地，二叉树有五种基本形态，如图5.2所示。,

5、图5.2 二叉树的基本形态,(a) 空二叉树 (b) 仅有一个根结点的二叉树 (c) 右子树为空的二叉树 (d)左子树为空的二叉树 (e)左、右子树均非空的二叉树,1. 满二叉树,在一个二叉树中，若第i层的结点数为2i-1，则称此层的结点数是满的，当树中的每一层都是满的，则称此二叉树为满二叉树。 即如果一个二叉树中，除最下一层的各结点度数为0以外，其它各层结点的度数均等于2，则此二叉树为满二叉树。 满二叉树的第一层有一个结点（即根结点），第二层有两个结点，依此类推。每一层的结点数都是上一层结点数的二倍。所以，在满二叉树的第i层共有2i-1个结点（i1），一个深度为h的满二叉树的结点总数为2h-

6、1。,图5.3 满二叉树,2. 完全二叉树,如果一个二叉树各层都是“满”的，只是最下面一层从右边起连续缺n个结点，这种二叉树叫做完全二叉树。 例如图5.3中的满二叉树，如果缺少从第11号至第15号结点（没有图中虚框里的几个结点），就是一个完全二叉树。,对于完全二叉树，对其结点采用“按层编号”比较方便，即从根结点开始由上而下逐层给结点编号，同一层的结点由左向右编号。 对于完全二叉树中任一个编号为i的结点(1in)，它的父结点和左、右儿子结点的编号与i值有如下的关系： 1) 如果i=1，则它是整个树的根结点，无父结点；若i1，则其父结点编号为 。 2) 如果2in，则其左儿子结点编号为2i；若2i

7、n，则无左儿子结点。 3) 如果（2i+1）n，则其右儿子结点编号为（2i+1）；反之，则无右儿子结点。,5.2.2 二叉树的存储结构,1. 二叉树的顺序存储结构：用一个一维数组来存储二叉树的各个结点，显然，二叉树的结点必须按某种次序分别存入数组的各个单元，这种次序应能反映结点间的逻辑关系，否则二叉树上的各种基本运算在顺序存储结构上很难实现。 对于完全二叉树来说，可以采用“以编号为地址”的方法，将编号为i的结点存入一维数组的第i个单元。 图5.3所示的完全二叉树按此方法存入数组中如下图5.4所示。,图5.4 二叉树的顺序存储结构,这种存储结构适用于完全二叉树和满二叉树。 如果某二叉树不是完全二

8、叉树，中间有一些结点不存在，则采用顺序存储结构时，数组中必然要有一些空闲单元，对存储空间利用不够。,图5.5 非完全二叉树的顺序表示,图5.5中的二叉树,采用顺序存储结构时,一维数组的21单元中只用上了7个。 2. 二叉树的链式存储结构：对于这种非完全二叉树，采用链式存储结构更合适，如图5.6所示。,结点结构,通常每个结点中设置三个域,即值域、左指针域和右指针域，其结点结构如下： 其中data表示值域，用于存储放入结点的数据，left和right分别表示左指针域和右指针域，用以分别存储指向左儿子结点和右儿子结点的指针。,链式存储结构的结点定义如下： typedef struct bnode E

9、lemType data; struct bnode *left, *right; *btree; 这里的ElemType可以是任何相应的数据类型如int、float或char等。,5.2.3 普通树与二叉树的转换,普通树可用链式存储结构来表示，每个结点包括数据域以及指向它各个儿子结点的指针域。 由于同一树的各结点度数一般并不相同，如按结点的度数给每个结点设置不同数目的指针域，不同结点的数据结构不同，会给算法设计和程序编制造成困难。 如欲令同一树的各结点有相同数据结构，则只能按结点度数最大值（该树的度数）给每个结点设置指针。这样较浪费存储空间。 按照一定的原则将普通树用二叉树来表示，是较好的表

10、示方法。,把普通树转换成相应的二叉树，具体方法如下： 1) 在所有兄弟结点之间加一连线； 2) 对每个结点，除了保留与其左儿子结点的连线外，去掉该结点与其它儿子结点的连线。,图中所示的树经过变换，可得下面的形式。,得到的已是一棵二叉树，若按顺时针方向将它旋转就更清楚地变为下面所示的二叉树。,5.3.1二叉树的遍历,二叉树的遍历(Traversal)是指按一定的规律访问二叉树的每个结点，且每个结点只被访问一次的过程。 对二叉树的遍历过程实际上是将非线性结构的二叉树中的结点排列成一个线性序列的过程。 对于用顺序法表示的二叉树，各结点在数组中的编号很有规律，其遍历较容易进行，但对于用链式存储结构表示

11、的二叉树，进行遍历就复杂一些，故本节仅讨论链式存储形式的二叉树遍历过程。,一个非空的二叉树由根结点及左、右子树这三个基本部分组成，因此若能依次遍历这三部分，便是遍历了整个二叉树。 在任一给定结点上，可以按某种次序执行三个操作：访问结点本身，遍历该结点左子树，遍历该结点右子树，操作排列次序： 左、根、右； 根、左、右； 左、右、根； 右、根、左； 根、右、左； 右、左、根； 由于实际问题一般都是要求左子树较右子树先遍历，故只采用其中、三种遍历次序，分别称为中序遍历、先序遍历和后序遍历。,三种遍历次序以递归的形式定义： (1) 中序（Inorder）遍历 若遍历的二叉树为空，执行空操作；否则依次执

12、行下列操作： 中序遍历左子树； 访问根结点； 中序遍历右子树。 (2) 先序（Preorder）遍历 若遍历的二叉树为空，执行空操作；否则依次执行下列操作： 访问根结点； 先序遍历左子树； 先序遍历右子树。,(3) 后序（Postorder）遍历 若遍历的二叉树为空，执行空操作；否则依次执行下列操作： 后序遍历左子树； 后序遍历右子树； 访问根结点。,中序遍历序列：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)

13、inorder(p-left); coutdata; inorder(p-right); ,typedef struct bnode ElemType data; struct bnode *left, *right; btree;,我们在输入结点值时，存在的结点则输入它对应的字符，不存在的结点(虚结点)，输入#，最后以回车作为输入的结束,表示建二叉链表已完成。 如要建 如图的树，输入的数据为：AB#CD#,typedef struct bnode char data; struct bnode *left, *right; *btree; btree createtree(btree t)

14、char ch; ch=getchar(); if(ch=#) t=NULL; else t=new bnode; t-data=ch; t-left=createtree(t-left); t-right=createtree(t-right); return t; ,void inorder(btree p) if (p!=NULL) inorder(p-left); coutdata; inorder(p-right); void main() btree T; T=NULL; T=createtree(T); inorder(T); ,5.3.2 二叉树的非递归遍历,可利用堆栈将递归算

15、法改写成非递归的形式。下面以先序遍历为例来具体说明。 图示为二叉树上的任一结点X,以及它的左子树XL和右子树XR。假设t是指向结点X的指针。,非递归先序遍历二叉树上任一结点X的主要操作： (1) 访问结点X； (2) 结点X的右指针进栈； (3) 若XL不空，沿X的左指针遍历XL ； (4) 从栈中取出X的右指针； (5) 若XR不空，沿X的右指针遍历XR 。,先序遍历的非递归算法,void preorder (btree t) bnode stackstacksize; /*定义栈*/ int top=0; stacktop = t; /*将根指针进栈*/ while (top=0) s =

16、 stacktop; top-; /*读栈顶元素到s中*/ while (s!=NULL),typedef struct bnode char data; struct bnode *left, *right; *btree;, coutdata; top+;stacktop = s-rignt; /*右指针进栈*/ s = s-left; /*修改s以继续遍历左子树*/ ,5.4 线索二叉树,在一个n结点的链式存储二叉树中，有n+1个指针域是空指针域，可以把每个空指针域用于存放分别指向某种遍历次序的前趋和后继结点的指针。 在结点的空指针域中存放的该结点在某遍历次序下的前趋结点和后继结点的指针叫做线索。 把某结点原来空的左（右）指针域用于存放指向其前趋（后继）结点的指针，也叫左（右）线索。 对一个二叉树中的所有结点的空指针域按照某种遍历次序加线索的过程叫作线索化，被线索化了的二叉树称作线索二叉树。,