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

算法和数据结构1 数据结构数据结构 大话大话数据结构数据结构 崔基哲 2012年 算法和数据结构 2 第一章 绪论 第二章 算法 第三章 线性表 第四章 栈和队列 第五章 串 第六章 树 第七章 图 第八章 查找 第九章 排序 3. 二叉树的存储结构 一、顺序存储结构 按二叉树的结点“自上而下、 从左至右”编号，用一组连续 的存储单元存储。 A A B B C C D D E E F F G G H H I I 1 2 3 4 5 6 7 8 9 A A B B C C GG E E I I D D HH F F 问：顺序存储后能否复原成唯一对应的二叉树形状？ 答：若是完全/满二叉树则可以做到唯一复原。 而且有规律：下标值为i的双亲，其左孩子的下标值必为2i，其 右孩子的下标值必为2i1（即性质5） 例如，对应2的两个孩子必为4和5,即B的左孩子必是D,右 孩子必为E。 T0一 般不用 讨论：不是完全二叉树怎么办？ 答：一律转为完全二叉树！ 方法很简单，将各层空缺处统统补上“虚结点”，其内容为空。 A A B B C C D D E E 1 2 3 4 5 6 7 8 9 . 16 A B E C D 缺点：浪费空间；插入、删除不便 缺点：浪费空间；插入、删除不便 缺点：浪费空间；插入、删除不便 二、链式存储结构 用二叉链表即可方便表示。 datadataleft_childleft_childright_childright_child datadata left_childleft_childright_childright_child 一般从根结点开始存储。 （相应地，访问树中结点时也只能从根开始） 注：如果需要倒查某结点的双亲，可以再增加一个双亲域（直接前 趋）指针，将二叉链表变成三叉链表。 二叉树结点数据类型定义： typedef struct BiTNode TElemType data; struct BiTNode *left_child, *right_child; BiTNode, *BiTree; 例 ： A B E C D A A B B D D C C E E 遍历 w二叉树的遍历(traversing binary Tree) 是指从根结点出发，按照某种次序依 次访问二叉树中的所有结点，使得每 个结点被访问一次且仅被访问一次 6.8 遍历二叉树和线索二叉树 一、遍历二叉树（Traversing Binary Tree） 遍历定义指按某条搜索路线遍访每个结点 且不重复（又称周游）。 遍历用途它是树结构插入、删除、修改、 查找和排序运算的前提，是二叉 树一切运算的基础和核心。 遍历方法牢记一种约定，对每个结点的查 看都是“先左后右” 。 遍历规则 v二叉树由根、左子树、右子树构成，定义为D、 L、R vD、 L、R的组合定义了六种可能的遍历方案： LDR, LRD, DLR, DRL, RDL, RLD v若限定先左后右，则有三种实现方案： DLR LDR LRD 先 (根)序遍历 中 (根)序遍历 后(根)序遍 历 注：“先、中、后”的意思是指访问的结点D是先 于子树出现还是后于子树出现。 例1： 先序遍历的结果是： 中序遍历的结果是： 后序遍历的结果是： 层序遍历的结果是： A B C D E A B D E CA B D E C D B E A CD B E A C D E B C AD E B C A A B C D EA B C D E 口诀： DLR先序遍历，即先根再左再右 LDR中序遍历，即先左再根再右 LRD后序遍历，即先左再右再根 + * A * / E D C B 先序遍历 + * * / A B C D E 前缀表示 中序遍历 A / B * C * D + E 中缀表示 后序遍历 A B / C * D * E + 后缀表示 层序遍历 + * E * D / C A B 例2：用二叉树表示算术表达式 f dg i be hj ac w习题1 ：写出如图所示的二叉树的前(先)序 中 序和后序遍历序列. 习题2：若一棵二叉树，左右子树均有三个结点，其左 子树的前（先）序序列与中序序列相同，右子树的中序 序列与后序序列相同，试构造该树。 习题3：一棵非空的二叉树其先