数据结构第6章b.ppt

* * 第六章 树和二叉树 6.1 树的概念 6.2 二叉树 6.3 遍历二叉树 6.4 线索二叉树 6.5 树和森林 6.6 哈夫曼树及其应用 * 6.3 遍历二叉树和线索二叉树 6.3.1 遍历二叉树 先序遍历二叉树的操作定义为： 若二叉树为空，则空操作；否则(1)访问根结点；(2)先序遍历左子树；(3)先序遍历右子树。 中序遍历二叉树的操作定义为： 若二叉树为空，则空操作；否则(1)中序遍历左子树；(2)访问根结点；(3)中序遍历右子树。 后序遍历二叉树的操作定义为： 若二叉树为空，则空操作；否则(1)后序遍历左子树；(2)后序遍历右子树；(3) 访问根结点。 * 二叉树的先序遍历示意图 * 二叉树的中序遍历示意图 * 二叉树的后序遍历示意图 * 练习:分别写出该树的三种遍历顺序 * 中序遍历算法： INORDER(bitree *t) { if(t) { INORDER(t-lchild); printf(“\t%c\n”,t-data); INORDER(t-rchild); } } * 前序遍历算法： PREORDER(bitree *t) { if(t) { printf(“\t%c\n”,t-data); PREORDER (t-lchild); PREORDER (t-rchild); } } * 后序遍历算法： POSTORDER(bitree *t) { if(t) { POSTORDER (t-lchild); POSTORDER (t-rchild); printf(“\t%c\n”,t-data); } } * 线索：指向结点前驱和后继的指针。 线索链表：加了线索的二叉链表（二叉树的存储结构的链表）。 线索二叉树：加上线索的二叉树。 线索化：对二叉树以某种次序遍历使其变为线索二叉 树的过程。 树和二叉树 6.3.2、线索二叉树 * 6.3.2、线索二叉树 树和二叉树 结点类型： 其中： lchild LTag data RTag rchild 0 lchild LTag 1 lchild 指向左孩子 0 rchild RTag 1 rchild 指向前趋线索 指向后继线索 指向右孩子 * 树和二叉树 * * F、B、E * D、F * 树和二叉树 后序线索树的方法： (1) 若结点 x 是二叉树的根，则其后继为空； (2) 若结点 x 是其双亲的右孩子或是其双亲 的左孩子且其双亲没有右子树，则其后 继结点即为双亲结点； (3) 若结点 x 是其双亲的左孩子，且其双 亲有右子树，则其后继为双亲的右子 树上按后序遍历列出的第一个结点。 图6.12后序后继线索二叉树 * E、B * （3） 在后序线索二叉树中，查找指定结点*p的后序前趋结点　　在后序线索二叉树中，查找指定结点*p的后序前趋结点的具体规律是：　　① 若*p的左子树为空，则p-lchild是前趋线索，指示其后序前趋结点。 * ② 若*p的左子树非空，则p-lchild不是前趋线索。由于后序遍历时，根是在遍历其左右子树之后被访问的，故*p的后序前趋必是两子树中最后一个遍历结点。　　 当*p的右子树非空时，*p的右孩子必是其后序前趋　　【例】在上图所示的后序线索二叉树中，A的后序前趋是E；　　 当*p无右子树时，*p的后序前趋必是其左孩子　　【例】在上图所示的后序线索二叉树中，E的后序前趋是F * 树和二叉树 * 线索二叉树的插入 在中序线索二叉树中插入一个结点p，使它成为结点s的右孩子。 下面分两种情况来分析： （1）若s的右子树为空，如图2 (a)所示，则插入结点p之后成为图2 (b)所示的情形。在这种情况中，s的后继将成为p的中序后继，s成为p的中序前驱，而p成为s的右孩子。二叉树中其它部分的指针和线索不发生变化。 * s s p  * 若s的右子树非空，如图3 (a)所示，插入结点p之后如图3 (b)所示。S原来的右子树变成p的右子树，由于p没有左子树，故s成为p的中序前驱，p成为s的右孩子；又由于s原来的后继成为p的后继，因此还要将s原来的本来指向s的后继的左线索，改为指向p。 * p s s