第07章1自定义数据类型.ppt

《第07章1自定义数据类型.ppt》由会员分享，可在线阅读，更多相关《第07章1自定义数据类型.ppt（38页珍藏版）》请在三一文库上搜索。

1、第7章 树和二叉树,树 二叉树 以结点类为基础的二叉树设计 二叉树类 二叉树的分步遍历 线索二叉树 哈夫曼树 树与二叉树的转换 树的遍历,主要知识点,7.1 树,1.树的定义,树是由n(n0)个结点组成的有限集合T。n=0的树称为空树；对n0的树，有:(1)仅有一个特殊的结点称为根结点，根结点没有前驱结点；(2)当n1时，除根结点外其余的结点分为m(m0)个互不相交的有限集合T1,T2，Tm，其中每个集合Ti本身又是一棵结构和树类似的子树。,注：树的定义具有递归性，即“树中还有树”。,若干术语,结点：由数据元素和构造数据元素之 间关系的指针组成,结点的度：结点所拥有的子树的个数,叶结点：度为0

2、的结点，也称作 终端结点,分支结点：度不为0的结点,孩子结点：树中一个结点的子树的根结点,双亲结点：若树中某结点有孩子结点，则这个结点就 称作它的孩子结点的双亲结点,兄弟结点：具有相同的双亲结点的结点,树的度：树中所有结点的度的最大值,结点的层次：从根结点到树中某结点所经路径上的分支数,树的深度：树中所有结点的层次的最大值,无序树：树中任意一个结点的各孩子结点之间的次序 构成无关紧要的树,有序树：树中任意一个结点的各孩子结点有严格排列 次序的树,森林：m（m0）棵树的集合,2.树的表示方法,(1)直观表示法,(2)形式化表示法,(3)凹入表示法,3.树的抽象数据类型,数据集合: 树的结点集合，

3、每个结点由数据元素和构造数 据元素之间关系的指针组成。 操作集合: (1)创建树 MakeTree(T) (2)撤消树 DestroyTree(T) (3)查找树中当前结点的双亲结点 Parent(T,curr) (4)查找树中当前结点的左孩子结点 LeftChild(T,curr) (5)查找树中当前结点的右兄弟结点 RightSibling(T,curr) (6)遍历树 Traverse(T,Visit( ),4.树的存储结构,树的结点之间的逻辑关系主要有双亲-孩子关系，兄弟关系。因此，从结点之间的逻辑关系分，树的存储结构主要有：双亲表示法、孩子表示法、双亲孩子表示法和孩子兄弟表示法四种组

4、合。,(1)双亲表示法,(a)一棵树,（b)仿真指针的双亲表示法存储结构,树及其使用仿真指针的双亲表示法,(2)孩子表示法,双亲孩子表示法,(3)双亲孩子表示法,(4)孩子兄弟表示法,常规指针的孩子兄弟表示法,7.2 二叉树,一、二叉树：是n(n0)个结点的有限集合。n=0的树称为空二叉树；n0的二叉树由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成 。 逻辑结构： 一对二（1:2） 基本特征: 每个结点最多只有两棵子树（不存在度大于2的结点）； 左子树和右子树次序不能颠倒。所以下面是两棵不同的树,1.二叉树的定义,二、满二叉树：在一棵二叉树中，如果所有分支结点都存在左 子树

5、和右子树，并且所有叶子结点都在同一层上，这样的 二叉树称为满二叉树。 三、完全二叉树：如果一棵深度为k，有n个结点的二叉树中各 结点能够与深度为k的顺序编号的满二叉树从1到n标号的 结点相对应的二叉树称为完全二叉树。如下图所示,(a)满二叉树,(b)完全二叉树,数据集合：二叉树的结点集合，每个结点由数据元素和构造数据元素之间关系的指针组成。 操作集合： (1)创建二叉树 MakeTree(T) (2)撤消二叉树 DestroyTree(T) (3)左插入结点 InsertLeftNode(curr,x) (4)右插入结点 InsertRightNode(curr,x) (5)左删除子树 Del

6、eteLeftTree(curr) (6)右删除子树 DeleteRightTree(curr) (7)遍历二叉树 Traverse(T,Visit(),2.二叉树抽象数据类型,3.二叉树的性质,性质1:在一棵非空二叉树的第i层上至多有2i个结点（i0）。,性质2:深度为k的二叉树至多有2k+1-1个结点(k-1)。,性质3: 具有n个结点的完全二叉树的深度k为不超过log2(n+1)-1的最大整数。,证明：根据性质2，对于有n个接点的深度为k的完全二叉树有 2k-1n2k+1-1，移项，有 2kn+12k+1 对不等式求对数，有klog2(n+1)k+1，因为k必须是整数，所以k=log2(

7、n+1)-1,性质4:对于一棵有n个结点的完全二叉树，按照从上至下和从左至右的顺序对所有结点从0开始顺序编号,则对于序号为i的结点(0in),有： (1)如果i0，则其双亲是结点(i-1)/2(“/”表示整除） ；如果i=0，则结点I是根结点，无双亲。 (2)如果2i+1n ，其左孩子是结点2i+1；如果2i+1n，则结点i无左孩子。 (3)如果2i2n，其右孩子是结点2i2；如果2i2n，则结点i无右孩子。,二叉树的存储结构主要有三种：顺序存储结构、链式存储结 构和仿真指针存储结构。 (1) 二叉树的顺序存储结构 完全二叉树的结点可按从上至下和从左至右的次序存储在一维数组中，其结点之间的关系

8、可由公式计算得到，这就是二叉树的顺序存储结构。下面两棵树在数组中的存储结构分别为：,4.二叉树的存储结构,对于一般的非完全二叉树显然不能直接使用二叉树的顺序存储结构。可以首先在非完全二叉树中增添一些并不存在的空结点使之变成完全二叉树的形态，然后再用顺序存储结构存储。,(a)一般二叉树,(b)完全二叉树形态,(c) 在数组中的存储形式,(2) 二叉树的链式存储结构 二叉树的链式存储结构是用指针建立二叉树中结点之间的关系。二叉树最常用的的链式存储结构是二叉链。二叉链存储结构的每个结点包含三个域，分别是数据域data、左孩子指针域leftChild和右孩子指针域rightChild。二叉链存储结构中

9、每个结点的图示结构为：,二叉链存储结构的二叉树也有不带头结点和带头结点两种。带头结点的二叉链存储结构的二叉树见下图(b)，不带头结点的二叉链存储结构的二叉树如下图(a)所示。,图7-10 二叉链存储结构的二叉树,(a)不带头结点的二叉树,(b)带头结点的二叉树,(3)二叉树的仿真指针 二叉树的仿真指针存储结构是用数组存储二叉树中的结点，数组中每个结点除数据元素域外，再增加仿真指针域用于仿真常规指针建立二叉树中结点之间的关系。,二叉树的仿真二叉链存储结构,7.3 以结点类为基础的二叉树设计,二叉树的实现有两种基本方法：一种方法是首先设计二叉树结点类，然后在二叉树结点类的基础上，用结点类的外部函数

10、实现二叉树的操作；另一种方法是在二叉树结点类的基础上，再设计二叉树类。,1.二叉树的结点类,模板形式的二叉树结点类定义和实现代码如下：,template class BiTreeNode private: BiTreeNode *leftChild; /左子树指针 BiTreeNode *rightChild; /右子树指针 public: T data; /数据域 BiTreeNode():leftChild(NULL), rightChild(NULL) BiTreeNode(T item, BiTreeNode *left = NULL, BiTreeNode *right = NULL

11、): data(item), leftChild(left), rightChild(right) BiTreeNode(),BiTreeNode* 设计说明： （1）成员变量通常设计成私有访问权限，但考虑到外部函数要频繁使用结点类中的成员变量，所以这里成员变量data设计成公有访问权限。 （2）二叉树也有带头结点（或称根结点）和不带头结点两种情况。这里设计了两个构造函数，第一个可用于带头结点结构中头结点对象的定义，第二个用于常规结点对象的定义。 （3）访问指针域的成员函数Left ()和Right()的返回值类型设计为指针的引用类型是十分必要的，引用类型变量意味着相应的变量是同一个变量，这使

12、得这两个函数不仅可以位于赋值号的左边，而且还可以位于赋值号的右边。,由结点构造二叉树的基本函数： template BiTreeNode *GetTreeNode(const T item, BiTreeNode *left = NULL, BiTreeNode *right = NULL) BiTreeNode *p; p = new BiTreeNode (item, left, right); return p; ,2.二叉树的遍历,(1)二叉树遍历的基本方法,从二叉树的定义知，一棵二叉树由三部分组成：根结点、左子树和右子树。若规定D,L,R分别代表“访问根结点”、“遍历根结点的左子树”

13、和“遍历根结点的右子树”，根据遍历算法对访问根结点处理的位置，称下面三种遍历算法分别为前序遍历（DLR）、中序遍历（LDR）和后序遍历（LRD）。,前序遍历（DLR）递归算法为： 若二叉树为空则算法结束；否则： （1）访问根结点； （2）前序遍历根结点的左子树； （3）前序遍历根结点的右子树。,中序遍历（LDR）递归算法为： 若二叉树为空则算法结束；否则： （1）中序遍历根结点的左子树； （2）访问根结点； （3）中序遍历根结点的右子树。 后序遍历（LRD）递归算法为： 若二叉树为空则算法结束；否则： （1）后序遍历根结点的左子树； （2）后序遍历根结点的右子树； （3）访问根结点。,此外，二

14、叉树还有层序遍历。层序遍历的要求是：按二叉树的层序次序（即从根结点层至叶结点层），同一层中按先左子树再右子树的次序遍历二叉树。 它的特点是，在所有未被访问结点的集合中，排列在已访问结点集合中最前面结点的左子树的根结点将最先被访问，然后是该结点的右子树的根结点。这样，如果把已访问的结点放在一个队列中，那么，所有未被访问结点的访问次序就可以由存放在队列中的已访问结点的出队列次序决定。因此可以借助队列实现二叉树的层序遍历。,当对一个二叉树用一种特定的遍历方法来遍历时，其遍历序列一定是线性的，且是惟一的。,二叉树的层序遍历算法如下： （1）初始化设置一个队列； （2）把根结点指针入队列； （3）当队列

15、非空时，循环执行步骤（3.a）到步骤（3.c）； （3.a）出队列取得一个结点指针，访问该结点； （3.b）若该结点的左子树非空，则将该结点的左子树指针入队列； （3.c）若该结点的右子树非空，则将该结点的右子树指针入队列； （4）结束。,(2)二叉树的遍历方法和二叉树的结构 二叉树是非线性结构，每个结点会有零个、一个或两个孩子结点，一个二叉树的遍历序列不能决定一棵二叉树，但某些不同的遍历序列组合可以惟一确定一棵二叉树。可以证明，给定一棵二叉树的前序遍历序列和中序遍历序列可以惟一确定一棵二叉树的结构。,(3)二叉树遍历的实现 template void PreOrder(BiTreeNode

16、*t, void Visit(T item) /使用Visit(item)函数前序遍历二叉树t if(t != NULL) Visit(t-data); PreOrder(t-Left(), Visit); PreOrder(t-Right(), Visit); 为了通用性，把访问操作设计成前序遍历二叉树函数的一个函数虚参 Visit()。,template void InOrder(BiTreeNode *t, void Visit(T item) /使用Visit(item)函数中序遍历二叉树t if(t != NULL) InOrder(t-Left(), Visit); Visit(t

17、-data); InOrder(t-Right(), Visit); template void PostOrder(BiTreeNode *t, void Visit(T item) /使用Visit(item)函数后序遍历二叉树t if(t != NULL) PostOrder(t-Left(), Visit); PostOrder(t-Right(), Visit); Visit(t-data); ,3.二叉树遍历的应用,(1)二叉树的撤消操作 在释放某个结点的存储空间前必须先释放该结点左孩子结点的存储空间和右孩子结点的存储空间，因此，二叉树撤消操作必须是后序遍历的具体应用。撤消操作函数

18、实现如下： template void Destroy(BiTreeNode * ,(2) 打印二叉树 把二叉树逆时针旋转900C，按照二叉树的凹入表示法打印二叉树。可把此函数设计成递归函数。由于把二叉树逆时针旋转900C后，在屏幕上方的首先是右子树，然后是根结点，最后是左子树，所以打印二叉树算法是一种特殊的中序遍历算法。 template void PrintBiTree(BiTreeNode* ,(3)查找数据元素 在二叉树中查找数据元素操作的要求是：在bt为根结点指针的二叉树中查找数据元素x，若查找到数据元素x时返回该结点的指针；若查找不到数据元素x时返回空指针。 在二叉树bt中查找数据

19、元素x函数可设计成先序遍历函数，此时查找结点的次序是：首先在根结点查找，然后在左子树查找，最后在右子树查找。但是，和常规递归算法不同的是，此函数当一个分支上的结点比较完仍未查找到数据元素x时，要返回到该结点的双亲结点处继续查找。因此，这是回溯算法的一个应用。 实现如下：,template BiTreeNode *Search(BiTreeNode *t, T x) BiTreeNode *p; if(t = NULL) return NULL; /空二叉树时的查找失败出口 if(t-data = x) return t; /查找成功出口 if(t-Left() != NULL) p = Sea

20、rch(t-Left(), x); /在左子树查找 if(p != NULL) return p; /查找成功时结束递归过程 if(t-Right() != NULL) p = Search(t-Right(), x); /在右子树查找 if(p != NULL) return p; /查找成功时结束递归过程 return NULL; /查找失败出口 ,例7-1 编写一个程序，首先建立如图7-10(a)所示的不带头结点的二叉链存储结构的二叉树，然后打印该二叉树并分别输出按照前序遍历二叉树次序、中序遍历二叉树次序和后序遍历二叉树次序访问各结点的序列信息，最后再测试查找函数和撤消函数的正确性。,创

21、建不带头结点的二叉链存储结构的二叉树函数设计如下： void MakeCharTree(BiTreeNode* ,4.应用举例,5.非递归的二叉树遍历算法,所有递归算法都可以借助堆栈转换成循环结构的非递归算法，通常有两种方法：一种方法是形式化模拟转换，另一种方法是根据要求解问题的特点设计借助堆栈的循环结构算法。,非递归的二叉树前序遍历算法如下： （1）初始化设置一个堆栈； （2）把根结点指针入栈； （3）当堆栈非空时，循环执行步骤（3.a）到步骤（3.c）； （3.a）出栈取得一个结点指针，访问该结点； （3.b）若该结点的右子树非空，则将该结点的右子树指针入栈； （3.c）若该结点的左子树非空，则将该结点的左子树指针入栈； （4）结束。,