本文介绍: 两种思路,递归和非递归

题目描述:在二叉树查找值为 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&gt;非递归算法

思路: 非递归,因为在遇到 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 &amp;&amp; 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进行投诉反馈,一经查实,立即删除

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注