二叉树遍历的递归和非递归实现

爱被打了一巴掌 2021-10-30 01:54 328阅读 0赞

所谓二叉树的遍历，是指按某条搜索路径访问树中的每个结点，使得每个结点均被访问且仅被访问一次

## 前序遍历 ##

**1、递归实现**

如果二叉树非空，则先访问根结点—左子树—右子树

void PreOrder(BiTree T){
    	if(T!=NULL){
    	visit(T);//先访问根结点
    	PreOrder(T->lchild); //先序遍历左子树
    	PreOrder(T->rchild); //先序遍历右子树
    	}
    }

**2、非递归实现**

借助栈实现

void PreOrder(BiTree T){
    	InitStack(s);//初始化一个栈
    	BiTree p=T;//初始化一个遍历指针
    	while(p!=NULL||StackEmpty(s)!=NULL){//当p非空，或者栈非空时
    		if(p!=NULL){
    			visit(p); //先访问根结点
    			Push(S,p);//将当前节点入栈
    			p=p->lchild;
    		}else{ //此时p的左子树均已访问
    				Pop(S,p); //将栈顶元素出栈
    				p=p->rchild;
    		}
    	}
    }

**中序遍历**

递归实现

void InOrder(BiTree T){
    	if(T!=NULL){
    	InOrder(T->lchild);
    	visit(T);
    	InOrder(T->rchild);
    	}
    }

非递归实现

void InOrder(BiTree T){
    	InitStack(S);
    	BiTree p=T;
    	while(p!=NULL||StackEmpty(S)!=NULL){
    		if(p!=NULL){
    			Push(S,p);//将p入栈
    			p=p->lchild;
    		}else{
    			Pop(S,p);
    			visit(p);
    			p=p->rchild;
    		}
    	}
    }

**后序遍历**

递归实现

void PostOrder(BiTree T){
    	if(T!=NULL){
    		PostOrder(T->lchild);
    		PostOrder(T->rchild);
    		visit(T);
    	}
    }

非递归实现

void PostOrder(BiTree T){
    	InitStack(S);
    	BiTree p=T;q=NULL; //设置一个p指针用来标识当前结点的右子树是否被访问
    	while(p!=NULL||StackEmpty(S)!=NULL){
    		if(p!=NULL){
    			Push(S,p);
    			p=p->lchild;
    		}else{
    			GetTop(s,p);//取栈顶元素
    			if(p->rchild==NULL||p->rchild==q){//p的右子树为空或者p的右子树已经被访问
    				visit(P);
    				Pop(S,p);
    				q=p;
    				p=NULL;//将p设置为空是为了继续读取下一个栈顶元素
    			}else{
    				p=p->rchild;
    			}
    		}
    	}
    }