数据结构课件第六章2.pptVIP

第6章 树和二叉树（Tree Binary Tree） 6.2 二叉树 为何要重点研究每结点最多只有两个 “叉” 的树？ 二叉树的结构最简单，规律性最强； 可以证明，所有树都能转为唯一对应的二叉树，不失一般性。 6.2.2 二叉树的性质 (3+2) 对于性质3和性质5的证明 6.2.3 二叉树的存储结构 讨论：不是完全二叉树怎么办？ 二、链式存储结构用二叉链表即可方便表示。 二叉树链式存储举例： 6.3 遍历二叉树和线索二叉树 例1： 例2：用二叉树表示算术表达式 对遍历的分析： 例：【严题集6.42③】编写递归算法，计算二叉树中叶子结点的数目。 如何把二叉树存入电脑内？ 特别讨论：若已知先序（或后序）遍历结果和中序遍历结果，能否“恢复”出二叉树？ 6.3.2 线索二叉树 讨论1：二叉树是1:2的非线性结构，如何定义其直接后继？ 为区别两种不同情况，特增加两个标志域： 1. 有关线索二叉树的几个术语： 例：带了两个标志的某先序遍历结果如下表所示，请画出对应的二叉树。 例1：画出以下二叉树对应的中序线索二叉树。 例2：【 2000年计算机系考研题】给定如图所示二叉树T，请画出与其对应的中序线索二叉树。 线索二叉树的生成算法（递归算法见教材P134-135） 3. 线索二叉树的遍历（无需堆栈） 附：中序线索二叉树遍历步骤 （算法6.5）： 算法流程： 5）当RTag=0时（表示有右孩子） ，此时应当从该结点的右孩子开始(p=p-rchild）查找左下角的子孙结点；即重复2） 1）设置一个有哪些信誉好的足球投注网站指针p； 2）先寻找中序遍历之首结点（即最左下角结点），方法是：当LTag=0时（表示有左孩子），p=p-lchild; 直到LTag=1（无左孩子，已到最左下角）；首先访问p-data； 3）接着进入该结点的右子树，检查RTag 和p-rchild ； 4） 若该结点的RTag=1(表示有后继线索)，则p=p-rchild ；访问p-data ;并重复4） ，直到后继结点的RTag=0； 有后继找后继，无后继找右子树的最左子孙 * 6.1 树的基本概念 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 赫夫曼树及其应用 二叉树的定义、性质和存储结构 二叉树的运算 6.2.1 二叉树的定义 6.2.2 二叉树的性质 6.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 时为根,除外）。 ——先后用归纳法证明了二叉树的性质3， 即：叶子数目= 2度结点数＋1 可以用归纳法证明了性质5。 一、顺序存储结构 按二叉树的结点“自上而下、从左至右”编号，用一组连续的存储单元存储。 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 缺点：①浪费空间；②插入、删除不便 data left_child right_child data left_child right_child 二叉树结点数据类型定义： typedef struct node *tree_pointer; typedef struct node{ int data; tree_pointer left_child, right_child; } node; 一般从根结点开始存储。（相应地，访问树中结点时也只能从根开始） 注：如果需要倒查某结点的双亲，可以再增加一个双亲域（直接前趋）指针