问答题 写出算法,求出中序线索二叉树中给定值为x的结点之后继结点,返回该后继结点的指针。线索树中结点结构为:(1tag,lc,data,rc,aag)。其中,data存放结点的值;lc,rc为指向左、右孩子或该结点前驱或后继的指针;ltag,rtag为标志域,若值为0,则lc,rc为指向左、右孩子的指针;若值为1,则1c,rc为指向其前驱、后继结点的指针。【北京邮电大学1996八(20分)】
【正确答案】正确答案:首先查找值为X的结点,设结点存在,且指针p指向该结点。若P一>rtag=1,P一>RC不为空,则P一>rc指向其后继;若P一>rtag=0,P结点有右子女,则其右子树上按中序遍历的第一个结点是其后继。前面几个题已有涉及找中序后继的内容,这里不再赘述。
【答案解析】