数据结构第六章树B.pptVIP

第6章 树和二叉树（ Tree Binary Tree ） 6.2 二叉树 2. 二叉树的性质 (3+2) 3. 二叉树的存储结构 讨论：不是完全二叉树怎么办？ 二、链式存储结构 例： 6.3 遍历二叉树和线索二叉树 对遍历的分析： 2、要实现遍历运算，必须先把二叉树存入电脑内 二、线索二叉树（Threaded Binary Tree） 为区别两种不同情况，特增加两个标志域： 1. 有关线索二叉树的几个术语： 例：带了两个标志的某先序遍历结果如下表所示，请画出对应的二叉树。 例1：画出以下二叉树对应的中序线索二叉树。 例2：给定如图所示二叉树T，请画出与其对应的中序线索二叉树。 3. 线索二叉树的遍历（无需堆栈） 28 25 40 55 60 33 08 54 解:因为中序遍历序列是：55 40 25 60 28 08 33 54 对应线索树应当按此规律连线，即在原二叉树中添加虚线。 NIL NIL * 6.1 树的基本概念 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 哈夫曼树及其应用 1. 二叉树的定义 2. 二叉树的性质 3. 二叉树的存储结构 （二叉树的运算见下一节） 性质1: 在二叉树的第i层上至多有2i-1个结点（i0）。 性质2: 深度为k的二叉树至多有2k-1个结点（k0）。 性质3: 对于任何一棵二叉树，若2度的结点数有n2个，则叶子数（n0）必定为n2＋1 （即n0=n2+1） 对于两种特殊形式的二叉树（满二叉树和完全二叉树），还特别具备以下2个性质： 性质4: 具有n个结点的完全二叉树的深度必为?log2n?＋1 性质5: 对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号为2i＋1；其双亲的编号必为?i/2?（i＝1 时为根,除外）。 性质4: 具有n个结点的完全二叉树的深度必为?log2n?＋1 性质5: 对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号为2i＋1；其双亲的编号必为i/2（i＝1 时为根,除外）。 证明：根据性质2，深度为k的二叉树最多只有2k-1个结点，且完全二叉树的定义是与同深度的满二叉树前面编号相同，即它的总结点数n位于k层和k-1层满二叉树容量之间， 即 2k-1-1n≤2k-1 或者 2k-1≤n2k 三边同时取对数，于是有：k-1≤log2nk 因为k是整数，所以k=?log2n? +1 注：深度是从k=1开始计算的。 注：编号是从1开始的！ 根据归纳法可轻松证明 一、顺序存储结构 按二叉树的结点“自上而下、从左至右”编号，用一组连续的存储单元存储。 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]一般不用 答：一律转为完全二叉树！ 方法很简单，将各层空缺处统统补上“虚结点”，其内容为空。 A B ^ C ^ ^ ^ D ^ … E [1] [2] [3] [4] [5] [6] [7] [8] [9] . [16] A B E C D 缺点：①浪费空间；②插入、删除不便 A B C D E A B C E D data l_child r_child data LCHILD RCHILD 二叉树结点数据类型定义： typedef struct BiTNode { TElemType data; struct BiTNode *l_child, *r_child; } BiTNode,*BiTree; 二叉链表的结点类型 PARENT lchild data rchild parent 三叉链表的结点类型 A B E C D ^ A B ^ D ^ C ^ ^ E ^ 空指针个数：2*n0+1*n1+0*n2 =2n0+n1 =n0+n1+n0 =n0+n1+n2+1 =n+1 一般从根结点开始存储。（相应地，访问树中结点时也只能从根开始） ^ 一、遍历二叉树（Traversing Binary Tree） 遍历定义—— 遍历用途—— 遍历方法—— 指按某条有哪些信誉好的足球投注网站路径巡访树中每个结点，使得每个结点均被访问一次且仅被访问一次（又称周游）。 它是树结构插入、删除、