《【2017年整理】二叉树前驱后继的查找》由会员分享，可在线阅读，更多相关《【2017年整理】二叉树前驱后继的查找（4页珍藏版）》请在金锄头文库上搜索。
1、线索二叉树的运算1 查找某结点*p 在指定次序下的前趋和后继结点（1）在中序线索二叉树中，查找结点*p 的中序后继结点在中序线索二叉树中，查找结点*p 的中序后继结点分两种情形： 若*p 的右子树空(即 p-rtag 为 Thread)，则 p-rchild 为右线索，直接指向*p 的中序后继。【例】下图的中序线索二叉树中，结点 D 的中序后继是 A。 若*p 的右子树非空(即 p-rtag 为 Link)，则*p 的中序后继必是其右子树中第一个中序遍历到的结点。也就是从*p 的右孩子开始，沿该孩子的左链往下查找，直至找到一个没有左孩子的结点为止，该结点是*p 的右子树中最左下 的结点，即 *
2、P 的中序后继结点。【例】上图的中序线索二叉树中：A 的中序后继是 F，它有右孩子；F 的中序后继是 H，它无右孩子；B 的中序后继是 D，它是 B 的右孩子。 在中序线索二叉树中求中序后继结点的过程可【参见动画演示】，具体算法如下：BinThrNode *InorderSuccessor(BinThrNode *p)/在中序线索树中找结点*p 的中序后继，设 p 非空BinThrNode *q；if (p-rtag=Thread) /*p 的右子树为空Return p-rchild； /返回右线索所指的中序后继else q=p-rchild； /从*p 的右孩子开始查找while (q-lt
3、ag=Link)q=q-lchild； /左子树非空时，沿左链往下查找return q； /当 q 的左子树为空时，它就是最左下结点 /end if该算法的时间复杂度不超过树的高度 h，即 O(h)。（2）在中序线索二叉树中查找结点*p 的中序前趋结点中序是一种对称序，故在中序线索二叉树中查找结点*p 的中序前趋结点与找中序后继结点的方法完全对称。具体情形如下： 若*p 的左子树为空，则 p-1child 为左线索，直接指向*p 的中序前趋结点；【例】上图所示的中序线索二叉树中，F 结点的中序前趋结点是 A 若*p 的左子树非空，则从*p 的左孩子出发，沿右指针链往下查找，直到找到一个没有右孩
4、子的结点为止。该结点是*p 的左子树中最右下 的结点，它是*p 的左子树中最后一个中序遍历到的结点，即*p 的中序前趋结点。【例】上图所示中序线索二叉树中，结点 E 左子树非空，其中序前趋结点是 I在中序线索二叉树中求中序前趋结点的过程可【参见动画演示】，具体算法如下：BinThrNode *Inorderpre(BinThrNode *p) /在中序线索树中找结点*p 的中序前趋，设 p 非空BinThrNode *q；if (p-ltag=Thread) /*p 的左子树为空return p-lchild； /返回左线索所指的中序前趋else q=p-lchild； /从*p 的左孩子开始
5、查找while (q-rtag=Link)q=q-rchild； /右子树非空时，沿右链往下查找return q； /当 q 的右子树为空时，它就是最右下结点 /end if 由上述讨论可知：对于非线索二叉树，仅从*p 出发无法找到其中序前趋(或中序后继) ，而必须从根结点开始中序遍历，才能找到*p 的中序前趋(或中序后继) 。线索二叉树中的线索使得查找中序前趋和中序后继变得简单有效。 （3） 在后序线索二叉树中，查找指定结点*p 的后序前趋结点在后序线索二叉树中，查找指定结点*p 的后序前趋结点的具体规律是： 若*p 的左子树为空，则 p-lchild 是前趋线索，指示其后序前趋结点。【例】
6、在下图所示的后序线索二叉树中，H 的后序前趋是 B，F 的后序前趋是 C。 若*p 的左子树非空，则 p-lchild 不是前趋线索。由于后序遍历时，根是在遍历其左右子树之后被访问的，故*p 的后序前趋必是两子树中最后一个遍历结点。当*p 的右子树非空时，*p 的右孩子必是其后序前趋【例】在上图所示的后序线索二叉树中，A 的后序前趋是 E；当*p 无右子树时，*p 的后序前趋必是其左孩子【例】在上图所示的后序线索二叉树中，E 的后序前趋是 F（4） 在后序线索二叉树中，查找指定结点*p 的后序后继结点具体的规律： 若*p 是根，则*p 是该二叉树后序遍历过程中最后一个访问到的结点。*p 的后序
7、后继为空 若*p 是其双亲的右孩子，则*p 的后序后继结点就是其双亲结点【例】上图所示的后序线索二叉树中，E 的后序后继是 A。 若*p 是其双亲的左孩子，但*P 无右兄弟，*p 的后序后继结点是其双亲结点【例】上图所示的后序线索二叉树中，F 的后序后继是 E。 若*p 是其双亲的左孩子，但*p 有右兄弟，则*p 的后序后继是其双亲的右子树中第一个后序遍历到的结点，它是该子树中最左下的叶结点【例】上图所示的后序线索二叉树中，B 的后序后继是双亲 A 的右子树中最左下的叶结点 H注意：F 是孩子树中最左下结点，但它不是叶子。由上述讨论中可知：在后序线索树中，仅从*p 出发就能找到其后序前趋结点；要找*p的后序后继结点，仅当*p 的右子树为空时，才能直接由*p 的右线索 p-rchild 得到。否则必须知道*p 的双亲结点才能找到其后序后继。因此，如果线索二叉树中的结点没有指向其双亲结点的指针，就可能要从根开始进行后序遍历才能找到结点*P 的后序后继。由此，线索对查找指定结点的后序后继并无多大帮助
