【题目分析】中序线索二叉树中,指针P所指结点的后继结点的特征是:若p->rtag=1,p->rchild指向其后继,否则,P的右子树上按中序遍历的第一个结点是其中序后继。 【算法6.63】
BiThrTree InSucc(BiThrTree T, BiThrTree p) ∥在中序线索二叉树T中,查找给定结点p的中序后继 {if(p->rtag==1)
q=p->rchild; ∥若p的右标志为1,用其右指针指向后继 else {q=p->rchild; while(q->ltag==0)
q=q->lchild; ∥p的后继为其右子树中最左下的结点 }
return (q); }∥结束InSucc