数据结构树与二叉树B.pptVIP

非递归的二叉树前序遍历： // 非递归实现二叉树的前序遍历 void preorder1(bintree t) { seqstack s; s.top = -1; // 当前处理的子树不为空或栈不为空则循环 while ( (t) || (s.top !=-1) ) { while (t) { printf(“%f”, t?data); s.top++; s.data[s.top] = t; t = t?lchild; }//endwhile if (s.top-1) { t = pop(s); t = t?rchild; }//endif }//endwhile }//end preorder1 * 二叉树的重建 由二叉树的前序序列和中序序列可以唯一地确定一棵二叉树 由二叉树的后序序列和中序序列可以唯一地确定一棵二叉树 由二叉树的前序序列和后序序列不可唯一地确定一棵二叉树 * 　仅知二叉树的前序序列“abcdefg” 不能唯一确定一棵二叉树， 如果同时已知二叉树的中序序列“cbdaegf”，则会如何？ 由二叉树的前序和中序序列建树 二叉树的前序序列 二叉树的中序序列 左子树 左子树 右子树 右子树 根 根 * a b c d e f g c b d a e g f a a b b c c d d e e f f g g a b c d e f g ^ ^ ^ ^ ^ ^ ^ ^ 前序序列 中序序列 * 前序序列{ A B H F D E C K G } 中序序列{ H B D F A E K C G } * 所以， 空指针数目＝2n－(n-1)=n+1个。 证明：用二叉链表存储包含n个结点的二叉树，结点必有2n个链域（见二叉链表数据类型说明）。 除根结点外，二叉树中每一个结点有且仅有一个双亲，意即每个结点地址占用了双亲的一个直接后继，n个结点地址共占用了n-1个双亲的指针域。也就是说，只会有n－1个结点的链域存放指针。 Threaded Binary Tree 讨论：用二叉链表法（l_child, r_child）存储包含n个结点的二叉树，结点的指针区域中会有多少个空指针？ 有n+1个！ 6.5 线索二叉树 * 结论：用二叉链表法存储包含n个结点的二叉树，结点的指针区域中会有n+1个空指针。 可以用它来存放当前结点的直接前驱和后继等线索，以加快查找速度。这就是线索二叉树的意义和用途。 疑问1：二叉树是1:2的非线性结构，如何定义其惟一的直接后继？ 答：要遍历之后才能得到，且不同遍历算法得到的后继也不同。 先依遍历规则把每个结点对应的前驱或后继线索预存起来，这叫做“线索化”。 疑问2：获得这种“直接前驱”或“直接后继”有何意义？ 答：从任一结点出发都能快速找到其前驱和后继，且不必借助堆栈 疑问3：如何经济的(预先)存放这类信息？ 答：左孩子/前驱复用，右孩子/后继复用，后者称之为线索 * lchild LTag data RTag rchild 约定: 当Tag域为0时,表示正常情况; 当Tag域为1时,表示线索情况. 前驱(后继) 左(右)孩子 为识别复用的两种不同信息，特增加两个标志域： 问：增加了前驱和后继等线索有什么好处？ ——能方便找出当前结点的前驱和后继，不用堆栈（递归）也能遍历整个树。 各1bit 疑问4：计算机如何识别是孩子指针还是线索指针？ * 1. 有关线索二叉树的几个术语： 线索链表： 线 索： 线索二叉树： 线 索 化： 用含Tag的结点样式所构成的二叉链表 指向结点前驱和后继的指针 加上线索的二叉树 对二叉树以某种次序遍历使其变为线索二叉树的过程 线索化过程就是在遍历过程中修改空指针的过程： 将空的lchild改为结点的直接前驱； 将空的rchild改为结点的直接后继。 非空指针呢？仍然指向孩子结点（称为“正常情况”） * data A G E I D J H C F B Ltag 0 0 1 1 1 1 0 1 0 1 Rtag 0 0 0 1 0 1 0 1 1 1 A G E I D J H C F B 例：带了两个标志的某先序遍历结果如下表所示，请画出对应的二叉树。 A Ltag=1表示前驱线索 Rtag=1表示后继线索 * A B C G E I D H F root 悬空？ NIL 悬空？ NIL 解：对该二叉树中序遍历的结果为: H, D, I, B, E, A, F