首页 > 试题广场 >

阅读下列算法，若有错，则改正之。 BiTree InSuc

[问答题]

阅读下列算法，若有错，则改正之。

BiTree InSucc (BiTree q)
 {　　//已知q是指向中序线索二叉树上某个结点的指针。
 //本函数返回指向*q的后继的指针。
 r = q->rchild;
 if(!r->rtag)
 while(!r->rtag)
 r = r->rchild;
 return r;
 }//InSucc

推荐

赞花婆

其错误在于中序遍历应先访问其左子树，可做如下修改：
BiTree InSucc(BiTree q){
// 一直q是指向中序线索二叉树上某个结点的指针，
// 本函数返回指向*q的后继的指针。
r=q->rchild;
if(!r->ltag)
while(!r->ltag) r=r->lchild;
return r;
} // InSucc

发表于 2018-03-25 10:03:36 回复(1)

志成林

作者：Damon林成志
链接：https://interview.nowcoder.com/questionTerminal/385198734a1f49e6aa1cd8b6c9457dfb
来源：牛客网
4,5,6,7行都有错误。因为中序遍历应该先访问左子树，正确算法为：
BiTree InSucc (BiTree q) {
//已知q是指向中序线索二叉树上某个结点的指针。
//本函数返回指向*q的后继的指针。
r = q->lchild;
if(!r->ltag)
while(!r->ltag)
r = r->lchild;
return r;
}//InSucc

发表于 2018-12-17 15:52:29 回复(0)