数据结构-第二部分电子教案

《数据结构-第二部分电子教案》由会员分享，可在线阅读，更多相关《数据结构-第二部分电子教案（260页珍藏版）》请在金锄头文库上搜索。

1、1,第二部分 树,树形结构式处理具有层次关系的数据元素 这部分将介绍 树 二叉树 堆,2,第五章 树,树的概念 二叉树 表达式树 哈夫曼树与哈夫曼编码 树和森林,3,树的概念,树的定义 树的术语 树的运算,4,树的定义,树是n (n1) 个结点的有限集合T，并且满足：,(1)有一个被称之为根(root)的结点,(2)其余的结点可分为m(m0)个互不相交的集合Tl，T2，Tm，这些集合本身也是一棵树，并称它们为根结点的子树(Subree)。每棵子树同样有自己的根结点。,6,根结点、叶结点、内部节点 结点的度和树的度 儿子结点 父亲结点 兄弟结点 祖先结点 子孙结点 结点所处层次 树的高度,有序树

2、 无序树 森林,树的术语,7,树的概念,树的定义 树的术语 树的运算,8,树的常用操作,建树create()：创建一棵空树； 清空clear()：删除树中的所有结点； 判空IsEmpty()：判别是否为空树； 找根结点root()：找出树的根结点。如果树是空树，则返回一个特殊的标记； 找父结点parent(x)：找出结点x的父结点； 找子结点child(x,i)：找结点x的第i个子结点； 剪枝delete(x,i)：删除结点x的第i棵子树； 构建一棵树MakeTree（x,T1, T2, ,Tn）：构建一棵以x为根结点，以T1, T2, ,Tn为第i棵子树的树； 遍历traverse()：访问

3、树上的每一个结点。,9,第五章 树,树的概念 二叉树 表达式树 哈夫曼树与哈夫曼编码 树和森林,10,二叉树,二叉树的概念 二叉树的性质 二叉树的基本运算 二叉树的遍历 二叉树的实现 二叉树类 二叉树遍历的非递归实现,11,二叉树的定义,二叉树（Binary Tree）是结点的有限集合，它或者为空，或者由一个根结点及两棵互不相交的左、右子树构成，而其左、右子树又都是二叉树。,注意：二叉树必须严格区分左右子树。即使只有一棵子树，也要说明它是左子树还是右子树。交换一棵二叉树的左右子树后得到的是另一棵二叉树。,12,二叉树的基本形态,(a) 空二叉树,(b) 根和空的左右子树,(c) 根和左右子树,

4、(d) 根和左子树,(e) 根和右子树,13,结点总数为3 的所有二叉树的不同形状,14,一棵高度为k并具有2k1个结点的二叉树称为满二叉树。 一棵二叉树中任意一层的结点个数都达到了最大值,满二叉树,15,满二叉树实例,不是满二叉树,16,完全二叉树,在满二叉树的最底层自右至左依次(注意：不能跳过任何一个结点)去掉若干个结点得到的二叉树也被称之为完全二叉树。满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。 完全二叉树的特点是： （1）所有的叶结点都出现在最低的两层上。 （2）对任一结点，如果其右子树的高度为k，则其左子树的高度为k或k1。,17,完全二叉树,非完全二叉树,18,二叉树,

5、二叉树的概念 二叉树的性质 二叉树的基本运算 二叉树的遍历 二叉树的实现 二叉树类 二叉树遍历的非递归实现,19,二叉树的性质1,一棵非空二叉树的第 i 层上最多有2i-1个结点（i1）。,1层：结点个数 21-1=1个 2层：结点个数 22-1=2 个 3层：结点个数 23-1=4 个,20,证明：当i=1时，只有一个根结点，2i-1=20 =1,命题成立。 假定对于所有的j，1jk,命题成立。 即第j层上至多有2j-1个结点。 由归纳假设可知，第j = k层上至多有2k-1个结点。 若要使得第k+1层上结点数为最多，那么，第k层上 的每个结点都必须有二个儿子结点。 因此，第k+1层上结点数

6、最多为为第k层上最多结点数 的二倍，即：22k-12k+1-12k。 所以，命题成立。,21,二叉树的性质2,一棵高度为k的二叉树，最多具有2k1个结点。,证明：这棵二叉树中的每一层的结点个数必须最多。 根据性质1，第i层的结点数最多为等于2i-1， 因此结点个数 N 最多为：,22,对于一棵非空二叉树，如果叶子结点数为n0，度数为2的结点数为n2，则有: n0n21 成立。,二叉树的性质3,23,证明：设n为二叉树的结点总数，n1为二叉树中度数为 1的结点数。 二叉树中所有结点均小于或等于2，所以有： n n0 n1 n2 再看二叉树中的树枝(父结点和儿子结点之间的 线段)总数。 在二叉树中

7、，除根结点外，其余结点都有唯一 的一个树枝进入本结点。,性质3证明,24,设B为二叉树中的树枝数，那么有下式成立： B n1 这些树枝都是由度为1和度为2的结点发出的， 一个度为1的结点发出一个树枝，一个度为2的结点发出两个树枝，所以有： B n12n2 因此， n0n21,25,二叉树的性质4,具有n个结点的完全二叉树的高度 k = log2n + 1,证明 根据完全二叉树的定义和性质2可知，高度为k的 完全二叉树的第一层到第k-1层具有最多的结点个 数，总数为 2k-1- 1个，第k层至少具有一个结点， 至多有2k-1个结点。因此， 2k-1 1 n 2k - 1 即 2k-1 n 2k

8、对不等式取对数，有 k -1 log2n k 由于k是整数，所以有：k = log2n 1,26,二叉树的性质5,如果对一棵有n个结点的完全二叉树中的结点按层自上而下（从第1层到第 log2n +1层），每一层按自左至右依次编号。若设根结点的编号为1。则对任一编号为i的结点（1in),有： （1）如果i1，则该结点是二叉树的根结点；如果i1，则其父亲结点的编号为i/2 。 （2）如果2i n，则编号为i的结点为叶子结点，没有儿子；否则，其左儿子的编号为2i。 （3）如果2i + 1 n，则编号为i的结点无右儿子；否则，其右儿子的编号为2i+1。,27,28,二叉树,二叉树的概念 二叉树的性质

9、二叉树的基本运算 二叉树的遍历 二叉树的实现 二叉树类 二叉树遍历的非递归实现,29,二叉树常用操作,建树create()：创建一棵空的二叉树； 清空clear()：删除二叉树中的所有结点； 判空IsEmpty()：判别二叉树是否为空树； 找根结点root()：找出二叉树的根结点。 找父结点parent(x)：找出结点x的父结点； 找左孩子lchild(x)：找结点x的左孩子结点； 找右孩子rchild(x)：找结点x的右孩子结点； 删除左子树delLeft(x)：删除结点x的左子树； 删除右子树delRight(x)：删除结点x的右子树； 构建一棵树MakeTree（x,TL, TR）：构建

10、一棵以x为根结点，以TL， TR为左右子树的二叉树； 遍历traverse()：访问二叉树上的每一个结点。,30,二叉树,二叉树的概念 二叉树的性质 二叉树的基本运算 二叉树的遍历 二叉树的实现 二叉树类 二叉树遍历的非递归实现,31,二叉树的遍历,二叉树的遍历讨论的是如何访问到树上的每一个结点 在线性表中，我们可以沿着后继链访问到所有结点。而二叉树是有分叉的，因此在分叉处必须确定下一个要访问的节点：是根结点、左结点还是右结点 根据不同的选择，有三种遍历的方法：前序、中序和后序,32,前序遍历,如果二叉树为空，则操作为空 否则 访问根结点 前序遍历左子树 前序遍历右子树,33,中序遍历,如果二

11、叉树为空，则操作为空 否则 中序遍历左子树 访问根结点 中序遍历右子树,34,后序遍历,如果二叉树为空，则操作为空 否则 后序遍历左子树 后序遍历右子树 访问根结点,35,前序：A、L、B、E、 C、D、W、X,中序：B、L、E、A、 C、W、X、D,后序：B、E、L、X、 W、D、C、A,36,前序 中序 唯一确定一棵二叉树,前序: A、B、D、E、F、C 中序: D、B、E、F、A、C,前序: B、D、E、F 中序: D、B、E、F,前序: E、F 中序: E、F,37,同理，由二叉树的后序序列和中序序列同样可以唯一地确定一棵二叉树 但是，已知二叉树的前序遍历序列和后序遍历序列却无法确定一

12、棵二叉树。比如：已知一棵二叉树的前序遍历序列为A、B，后序遍历序列为B、A，我们虽然可以很容易地得知结点A为根结点，但是无法确定结点B是结点A的左儿子还是右儿子，因为B无论是结点A的右儿子还是左儿子都是符合已知条件的。,38,二叉树,二叉树的概念 二叉树的性质 二叉树的基本运算 二叉树的遍历 二叉树的实现 二叉树类 二叉树遍历的非递归实现,39,二叉树的实现,顺序实现 链接实现,40,完全二叉树的顺序存储,根据编号性质，可以省略左右孩子字段,41,普通二叉树的顺序存储,D,B,A,H,I,将普通的树修补成完全二叉树,42,右单支树的实例,43,顺序实现的特点,存储空间的浪费。 一般只用于一些特

13、殊的场合，如静态的并且结点个数已知的完全二叉树或接近完全二叉树的二叉树。,44,二叉树的实现,顺序实现 链接实现,45,链接存储结构,标准形式：（二叉链表）,广义标准形式：（三叉链表）,46,标准形式的实例,47,广义标准形式的实例,48,二叉树基本运算的实现,由于二叉树是一个递归的结构，因此二叉树中的许多运算的实现都是基于递归函数。 create()：将指向根结点的指针设为空指针就可以了，即root = NULL。 isEmpty()：只需要判别root即可。如果root等于空指针，返回true，否则，返回false。 root()：返回root指向的结点的数据部分。如果二叉树是空树，则返回

14、一个特殊的标记。,49,clear(),从递归的观点看，一棵二叉树由三部分组成：根结点、左子树、右子树。删除一棵二叉树就是删除这三个部分。 根结点的删除很简单，只要回收根结点的空间，把指向根结点的指针设为空指针。 如何删除左子树和右子树呢？记住左子树也是一棵二叉树，右子树也是一棵二叉树，左右子树的删除和整棵树的删除过程是一样的。,50,if （左子树非空） 递归删除左子树； if （右子树非空） 递归删除右子树； delete root指向的结点； root = NULL；,51,parent(x)：在二叉链表的实现中一般不实现这个操作 lchild(x)：返回结点x的left值 rchild

15、(x)：返回结点x的right值 delLeft(x)：对左子树调用clear函数删除左子树，然后将结点x的left置为NULL。 delRight(x)：对右子树调用clear函数删除右子树，然后将结点x的right置为NULL。 makeTree（x,TL, TR）：为x申请一个结点，让它的left指向TL的根结点，right指向TR的根结点。,52,二叉树的遍历,前序： 访问根结点； if （左子树非空） 前序遍历左子树； if （右子树非空）前序遍历右子树； 其他两种遍历只要调整一下次序即可。,53,二叉树,二叉树的概念 二叉树的性质 二叉树的基本运算 二叉树的遍历 二叉树的实现 二叉

16、树类 二叉树遍历的非递归实现,54,二叉树类,由于二叉树的顺序实现仅用于一些特殊的场合。大多数情况下，二叉树都是用二叉链表实现，所以仅介绍用二叉链表实现的二叉树类。,55,二叉树类的设计,标准的链接存储由两个类组成：结点类和树类。 和线性表的实现类似，这个结点类是树类专用的，因此可作为树类的私有内嵌类。,56,结点类Node的设计,存储和处理树上每一个结点的类。 数据成员包括：结点的数据及左右孩子的指针。 结点的操作包括： 构造和析构,57,二叉树类的设计,树的存储：存储指向根结点的指针 树的操作： 树的标准操作 增加了一个建树的函数,58,递归函数的设计,对于二叉树类的用户来说，他并不需要知道这些操作时用递归函数实现的。 对用户来说，调用这些函数并不需要参数