二叉树的递归与非递归遍历（前序、中序、后序）

Love The Way You Lie 2022-06-10 02:21 259阅读 0赞

**二叉树遍历算法是各大软件公司面试经常提及的一个话题，笔者在总结网上的一些资料，将二叉树的（前序、中序、后序）递归遍历和非递归遍历算法总结如下，其中中序非递归算法最简单，后序非递归算法最难。**

首先，定义二叉树结点类型如下：

//Binary Tree Node
    typedef struct node
    {
    	int data;
    	struct node* lchild;//左孩子
    	struct node* rchild;//右孩子 
    }BTNode;

# 一、前序遍历 #

## 1、递归算法 ##

//前序递归算法 
    void preOrder1(BTNode *root)
    {
    	if(root!=NULL)
    	{
    		cout<<root->data<<" ";
    		preOrder(root->lchild);
    		preOrder(root->rchild);
    	}
    }

## 2、非递归算法 ##

根据前序遍历访问的顺序，优先访问根结点，然后再分别访问左孩子和右孩子。即对于任一结点，其可看做是根结点，因此可以直接访问，访问完之后，若其左孩子不为空，按相同规则访问它的左子树；当访问其左子树时，再访问它的右子树。因此其处理过程如下：

对于任一结点P：  
  
     1)访问结点P，并将结点P入栈;  
  
     2)判断结点P的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点P，循环至1);若不为空，则将P的左孩子置为当前的结点P;  
  
     3)直到P为NULL并且栈为空，则遍历结束。

//前序非递归算法
    void preOrder2(BTNode *root)
    {
    	BTNode *p=root;
    	stack<BTNode *>s;
    	while(!s.empty()||p!=NULL)
    	{
    		while(p!=NULL)
    		{
    			cout<<p->data<<" ";
    			s.push(p);
    			p=p->lchild;
    		}
    		
    		if(!s.empty())
    		{
    			p=s.top();
    			s.pop();
    			p=p->rchild;
    		}
    	}
    }

# 二、中序遍历 #

## 1、递归算法 ##

//中序递归遍历
    void inOrder1(BTNode *root)
    {
    	if(root!=NULL)
    	{
    		inOrder1(root->lchild);
    		cout<<root->data<<" ";
    		inOrder1(root->rchild);
    	}
    }

## 2、非递归算法 ##

根据中序遍历的顺序，对于任一结点，优先访问其左孩子，而左孩子结点又可以看做一根结点，然后继续访问其左孩子结点，直到遇到左孩子结点为空的结点才进行访问，然后按相同的规则访问其右子树。因此其处理过程如下：  
  
　　对于任一结点P，  
  
  　1)若其左孩子不为空，则将P入栈并将P的左孩子置为当前的P，然后对当前结点P再进行相同的处理；  
  
 　 2)若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的P置为栈顶结点的右孩子；  
  
  　3)直到P为NULL并且栈为空则遍历结束。

//中序非递归遍历
    void inOrder2(BTNode *root)
    {
    	BTNode *p=root;
    	stack<BTNode *>s;
    	while(!s.empty()||p!=NULL)
    	{
    		while(p!=NULL)
    		{
    			s.push(p);
    			p=p->lchild;
    		}
    		
    		if(!s.empty())
    		{
    			p=s.top();
    			cout<<p->data<<" ";
    			s.pop();
    			p=p->rchild;
    		}
    	}
    }

# 三、后序遍历 #

## 1、递归算法 ##

//后序递归遍历
    void postOrder1(BTNode *root)
    {
    	if(root!=NULL)
    	{
    		postOrder1(root->lchild);
    		postOrder1(root->rchild);
    		cout<<root->data<<" ";
    	}
    }

## 2、非递归算法 ##

要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；或者P存 在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种况，则将P的右孩子和左孩子依次入栈，这样就保证了 每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。

//后序非递归遍历
    void postOrder2(BTNode *root)
    {
    	stack<BTNode *>s;
    	BTNode *cur;//当前结点 
    	BTNode *pre=NULL;//前一次访问的结点 
    	s.push(root);
    	while(!s.empty())
    	{
    		cur=s.top();
    		//如果当前结点没有孩子结点或者孩子节点都已被访问过 
    		if((cur->lchild==NULL&&cur->rchild==NULL)||(pre!=NULL&&(pre==cur->lchild||pre==cur->rchild)))
    		{
    			cout<<cur->data<<" ";
    			s.pop();
    			pre=cur;
    		}
    		else
    		{
    			if(cur->rchild!=NULL)
    			   s.push(cur->rchild);
    			if(cur->lchild!=NULL)
    			   s.push(cur->lchild);
    		}
    	}
    }

参考博客：http://www.cnblogs.com/SHERO-Vae/p/5800363.html

在此向作者表示谢谢！