题目描述:在二叉树中查找值为 x的结点,试编写算法(用 C语言)打印值为 X 的结点的所有祖先,假设值为x的结点不多于一个。
<1>递归算法
思路: 考虑递归,当前结点值不等于 x 时,递归其左右子树,如果两者有一个返回值为 true,则说明当前结点为 x 的祖先结点,直接打印。
bool AncestorX(BiTree T,ElemType x){
if(T == NULL)
return false;
if(T->data == x)
return true;
if(AncestorX(T->lchild,x) || AncestorX(T->rchild,x))
printf(T->data);
}
<2>非递归算法
思路: 非递归,因为在遇到 x 的时候需要将其所有祖先打印,而当访问到 x 且能保留x 的祖先的方法,只有使用后序非递归遍历(后序非递归遍历形式)。
void AncestorX2(BiTree T,ElemType x){
InitStack(S);
BiTNode *p = T;
BiTNode *r = NULL;
while(p || !IsEmpty(S)){
if(p){
push(S,p);
p = p->lchild;
}
else{
GetTop(S,p);
if(p->data == x){
pop(S,p); //先把等于 x 的结点弹出
while(!IsEmpty(S)){
pop(S,p);
printf(p->data);
}
return;
}
if(p->rchild && p->rchild != r)
p = p->rchild;
else{
pop(S,p);
r = p; //记录右结点已访问
p = NULL; //防止再次把 p 结点压入栈
}
}
}
}
原文地址:https://blog.csdn.net/weixin_52092223/article/details/134710571
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_30932.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。