查找x结点，打印x的祖先

算法

BiTree a[100];
int s=0;
//采用后序遍历算法，当找到x结点时，栈里的所有元素就是x的祖先 
void pos_traverse(BiTree T, ElemType x){
	BiTree temp = (BiTree)malloc(sizeof(BiNode));
	a[s]=T;
	while(s!=-1){
		if(a[s]->lchild&&a[s]->lchild!=temp&&a[s]->rchild!=temp){
			a[s+1]=a[s]->lchild;
			s++;
		} 
		else if(a[s]->rchild&&temp!=a[s]->rchild){
			a[s+1]=a[s]->rchild;
			s++;
		}
		else{
			temp=a[s--];
			if(temp->date == x){
				while(s!=-1){
					printf("%c ",a[s--]->date);
				}
			}
		}
	}
	return;
}

测试环境

#include 
#include
#include
#define maxsize 100
#define ElemType char 
//二叉树的创建序列 
//ab#df###c#e##
//abd##e##cf###
//ab#df###c#e##
typedef struct BiNode{
	ElemType date;
	struct BiNode *lchild,*rchild;
}BiNode,*BiTree;

BiNode* CreateBiTree();
void Traverse(BiNode *p);
void DeleteTree(BiTree &t);
void pos_traverse(BiTree T, ElemType x);


int main(){
	BiTree t = CreateBiTree();
	pos_traverse(t,'e');
	DeleteTree(t);
	return 0;
}

BiTree a[100];
int s=0;
//采用后序遍历算法，当找到x结点时，栈里的所有元素就是x的祖先 
void pos_traverse(BiTree T, ElemType x){
	BiTree temp = (BiTree)malloc(sizeof(BiNode));
	a[s]=T;
	while(s!=-1){
		if(a[s]->lchild&&a[s]->lchild!=temp&&a[s]->rchild!=temp){
			a[s+1]=a[s]->lchild;
			s++;
		} 
		else if(a[s]->rchild&&temp!=a[s]->rchild){
			a[s+1]=a[s]->rchild;
			s++;
		}
		else{
			temp=a[s--];
			if(temp->date == x){
				while(s!=-1){
					printf("%c ",a[s--]->date);
				}
			}
		}
	}
	return;
}

//用C++引用的方法删除树中所有节点 
void DeleteTree(BiTree &t){
	if(t){
		DeleteTree(t->lchild);
		DeleteTree(t->rchild);
		delete t;
		t = NULL;
	}
}


//用递归方法以中序遍历的方式创建二叉树 
BiNode* CreateBiTree(){
	BiNode *p;
	char a;
	scanf("%c",&a);
	if(a=='#')
	p=NULL;
	else{
		p=(BiNode *)malloc(sizeof(BiNode));
		p->date=a;
		p->lchild=CreateBiTree();
		p->rchild=CreateBiTree();
	}	
	return p;
}
//递归方法中序遍历二叉树 
void Traverse(BiNode *p){
	if(p==NULL){
		return;
	}
	else{
		printf("%c",p->date);
		Traverse(p->lchild);
		Traverse(p->rchild);
	}
	return;
}