数据结构第6章b

1第六章树和二叉树6.1树的概念6.2二叉树6.3遍历二叉树6.4线索二叉树6.5树和森林6.6哈夫曼树及其应用

26.3

遍历二叉树和线索二叉树6.3.1遍历二叉树先序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则(1)访问根结点；(2)先序遍历左子树；(3)先序遍历右子树。中序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则(1)中序遍历左子树；(2)访问根结点；(3)中序遍历右子树。后序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则(1)后序遍历左子树；(2)后序遍历右子树；(3)访问根结点。3二叉树的先序遍历示意图4二叉树的中序遍历示意图5二叉树的后序遍历示意图6练习:分别写出该树的三种遍历顺序7中序遍历算法：INORDER(bitree*t){if(t){INORDER(t->lchild);printf(“\t%c\n”,t->data);INORDER(t->rchild);}}8前序遍历算法：PREORDER(bitree*t){if(t){printf(“\t%c\n”,t->data);PREORDER(t->lchild);PREORDER(t->rchild);}}9后序遍历算法：POSTORDER(bitree*t){if(t){POSTORDER(t->lchild);POSTORDER(t->rchild);printf(“\t%c\n”,t->data);}}10线索：指向结点前驱和后继的指针。线索链表：加了线索的二叉链表（二叉树的存储结构的链表）。线索二叉树：加上线索的二叉树。线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程。

树和二叉树6.3.2、线索二叉树116.3.2、线索二叉树

树和二叉树结点类型：

其中：lchildLTagdataRTagrchild0lchildLTag1lchild指向左孩子0rchildRTag1rchild指向前趋线索指向后继线索指向右孩子12

树和二叉树1314F、B、E15D、F16

树和二叉树后序线索树的方法：(1)若结点x是二叉树的根，则其后继为空；(2)若结点x是其双亲的右孩子或是其双亲的左孩子且其双亲没有右子树，则其后继结点即为双亲结点；(3)若结点x是其双亲的左孩子，且其双亲有右子树，则其后继为双亲的右子树上按后序遍历列出的第一个结点。

图6.12后序后继线索二叉树

17E、B18（3）在后序线索二叉树中，查找指定结点*p的后序前趋结点

在后序线索二叉树中，查找指定结点*p的后序前趋结点的具体规律是：

①若*p的左子树为空，则p->lchild是前趋线索，指示其后序前趋结点。

19②若*p的左子树非空，则p->lchild不是前趋线索。由于后序遍历时，根是在遍历其左右子树之后被访问的，故*p的后序前趋必是两子树中最后一个遍历结点。

当*p的右子树非空时，*p的右孩子必是其后序前趋

【例】在上图所示的后序线索二叉树中，A的后序前趋是E；

当*p无右子树时，*p的后序前趋必是其左孩子

【例】在上图所示的后序线索二叉树中，E的后序前趋是F

20

树和二叉树21线索二叉树的插入在中序线索二叉树中插入一个结点p，使它成为结点s的右孩子。下面分两种情况来分析：（1）若s的右子树为空，如图2(a)所示，则插入结点p之后成为图2(b)所示的情形。在这种情况中，s的后继将成为p的中序后继，s成为p的中序前驱，而p成为s的右孩子。二叉树中其它部分的指针和线索不发生变化。22ssp

23若s的右子树非空，如图3(a)所示，插入结点p之后如图3(b)所示。S原来的右子树变成p的右子树，由于p没有左子树，故s成为p的中序前驱，p成为s的右孩子；又由于s原来的后继成为p