问题
单项选择题
如下所示的二叉树。
如果将该二叉树存储为对称序线索二叉树,则结点E的右线索指向结点( )。
答案
参考答案:A
解析: 在中序线索二叉树中,查找结点*p的中序后继结点分两种情形:①若*p的右子树空(即p->rtag为Thread),则p->rchild为右线索,直接指向*p的中序后继;②若*p的右子树非空(即p->rtag为Link),则*p的中序后继必是其右子树中第一个中序遍历到的结点。也就是从*p的右孩子开始,沿该孩子的左链往下查找,直至找到一个没有左孩子的结点为止,该结点是*p的右子树中“最左下”的结点,即*P的中序后继结点。因此,结点E的右线索指向结点A。