|
线索二叉树的运算 查找某结点*p在指定次序下的前趋和后继结点 ()在中序线索二叉树中查找结点*p的中序后继结点 在中序线索二叉树中查找结点*p的中序后继结点分两种情形 ① 若*p的右子树空(即p>rtag为Thread)则p>rchild为右线索直接指向*p的中序后继【例】下图的中序线索二叉树中 结点D的中序后继是A ② 若*p的右子树非空(即p>rtag为Link)则*p的中序后继必是其右子树中第一个中序遍历到的结点也就是从*p的右孩子 开始沿该孩子的左链往下查找直至找到一个没有左孩子的结点为止该结点是*p的右子树中最左下的结点即*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>ltag==Link) q=q>lchild; //左子树非空时沿左链往下查找 return q; //当q的左子树为空时它就是最左下结点 } //end if } 该算法的时间复杂度不超过树的高度h即O(h) ()在中序线索二叉树中查找结点*p的中序前趋结点 中序是一种对称序故在中序线索二叉树中查找结点*p的中序前趋结点与找中序后继结点的方法完全对称具体情形如下 ① 若*p的左子树为空则p>child为左线索直接指向*p的中序前趋结点; 【例】上图所示的中序线索二叉树中F结点的中序前趋结点是A ② 若*p的左子树非空则从*p的左孩子出发沿右指针链往下查找直到找到一个没有右孩子的结点为止该结点是*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的左孩子开始查找 while (q>rtag==Link) q=q>rchild; //右子树非空时沿右链往下查找 return q; //当q的右子树为空时它就是最右下结点 } //end if } 由上述讨论可知对于非线索二叉树仅从*p出发无法找到其中序前趋(或中序后继)而必须从根结点开始中序遍历才能找到 *p的中序前趋(或中序后继)线索二叉树中的线索使得查找中序前趋和中序后继变得简单有效 |
