数据结构演示课件第十讲二叉树.ppt

3. 二叉树的存储结构 讨论：不是完全二叉树怎么办？ 二、链式存储结构用二叉链表即可方便表示。 例： 遍历 二叉树的遍历(traversing binary Tree)是指从根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次 6.8 遍历二叉树和线索二叉树 例1： 例2：用二叉树表示算术表达式 习题1 ：写出如图所示的二叉树的前(先)序﹑中序和后序遍历序列. 习题2：若一棵二叉树，左右子树均有三个结点，其左子树的前（先）序序列与中序序列相同，右子树的中序序列与后序序列相同，试构造该树。 习题3：一棵非空的二叉树其先序序列和后序序列正好相反，画出这棵二叉树的形状。 习题4：已知一棵完全二叉树共有892个结点，试求：⑴ 树的高度；⑵ 叶结点数；⑶ 单支(度为1)结点数；⑷ 最后一个非终端结点的序号。 下课！ 算法和数据结构 * 数据结构大话《数据结构》 崔基哲 2012年 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 算法和数据结构 * 第一章 绪论 第二章 算法 第三章 线性表 第四章 栈和队列 第五章 串 第六章 树第七章 图 第八章 查找 第九章 排序 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 一、顺序存储结构 按二叉树的结点“自上而下、从左至右”编号，用一组连续的存储单元存储。 A B C D E F G H I [1] [2] [3] [4] [5] [6] [7] [8] [9] A B C G E I D H F 问：顺序存储后能否复原成唯一对应的二叉树形状？ 答：若是完全/满二叉树则可以做到唯一复原。 而且有规律：下标值为i的双亲，其左孩子的下标值必为2i，其右孩子的下标值必为2i＋1（即性质5） 例如，对应[2]的两个孩子必为[4]和[5],即B的左孩子必是D,右孩子必为E。 T[0]一般不用 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 答：一律转为完全二叉树！ 方法很简单，将各层空缺处统统补上“虚结点”，其内容为空。 A B ^ C ^ ^ ^ D ^ … E [1] [2] [3] [4] [5] [6] [7] [8] [9] . [16] A B E C D 缺点：①浪费空间；②插入、删除不便 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 缺点：①浪费空间；②插入、删除不便 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 缺点：①浪费空间；②插入、删除不便 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. data left_child right_child data left_child right_child 一般从根结点开始存储。（相应地，访问树中结点时也只能从根开始） 注：如果需要倒查某结点的双亲，可以再增加一个双亲域（直接前趋）指针，将二叉链表变成三叉链表。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 二叉树结点数据类型定义： typedef struct BiTNode { TElemType data; struct BiTNode *left_child, *right_chi