【数据结构】（二叉树）打印值为x结点的所有祖先递归&&非递归

左手的ㄟ右手 2021-11-09 13:34 380阅读 0赞

## 打印值为x结点的所有祖先 ##

> **算法思想:** 打印x祖先 首先我们要做的就是查询到这个x值。那么如何查询到这个值呢？如何去想  
> 我的理解就是在那三个遍历中下手

**首先我想到了先序遍历并以此写了代码**

int flag=0; //定义一个全局变量来判断是否查找到了值
    void PrintAncestors(BiTree *T,char x){
        
    	if(!T)
    		return;
    	if(T->data==x){
        
    		flag=1; //查询到值的时候 改变标志位
    		return;
    	}
    	if(flag==0)
    		PrintAncestors(T->lchild,x); //若没有查找到往节点的左侧查找
    	if(flag==0)
    		PrintAncestors(T->rchild,x);//若没有查找到往节点的右侧查找
    	if(flag==1)
    		visit(T);		
    }

**然后我再网上借鉴了网上写的递归方法**

int PrintAncestors2(BiTree *T,char x){
        
    	if(!T)
    		return 0;
    	if(T->data==x){
        
    		return 1;
    	}
    	
    //这个可以这样理解
    //如果一颗二叉树他的左孩子有要查询的结点或者他的右孩子里面有要查询的结点那么该节点就是祖先结点
    	if(PrintAncestors2(T->lchild, x)||PrintAncestors2(T->rchild,x)){
         
    		visit(T);
    		return 1;
    	}else{
        
    		return 0;
    	}
    }

\*\*接下来是非递归的求解 \*\*  
对于非递归的求解这，里我在之前的博客中有写过[后序遍历的非递归代码][Link 1]这里我的思想是直接将后续遍历的代码拿了过来，并将出栈访问结点的操作更改为了判断出栈元素是否为要查找的x。如果是，那么就将栈内的元素全部出栈，如果不是则继续进行序遍历

void PrintAncestors3(BiTree *T,char x){
        
    	if(!T)
    		return ;
    	BiTree *s[MaxSize];
    	int top=-1;
    	BiTree *pre;
    	while(T||top!=-1){
        
    	
    		while(T){
        
    			 s[++top]=T;
    			 T=T->lchild;
    		}
    		if(top!=-1){
        
    			T=s[top];
    			if(T->rchild==NULL||T->rchild==pre){
        
    				top--;
    				if(T->data==x){
         //若当前结点为x那么依次退栈
    					while(top!=-1){
        
    						visit(s[top--]); //打印结点
    					}
    				exit(0);
    				}
    				pre=T;
    				T=NULL;		
    			}else
    				T=T->rchild;		
    		}	
    	}
    }

//二叉树结构体定义
    typedef struct BiTree{
        
    	char data;
    	BiTree *lchild;		
    	BiTree *rchild;
    
    }BiTree;
    
    
    void visit(BiTree *b){
        
    	printf("%c  ",b->data);
    }

[Link 1]: https://blog.csdn.net/qq_41934478/article/details/98115749