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

- 日理万妓 2022-12-30 08:27 178阅读 0赞

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

*  非递归写法
 *   *  前序遍历（先序遍历）
     *  中序遍历
     *  后序遍历

如需递归写法，可以参考：[https://blog.csdn.net/weixin\_45413689/article/details/108270678][https_blog.csdn.net_weixin_45413689_article_details_108270678]

**结构体定义：**

struct node{
        
    	char data;
    	node *lchild;
    	node *rchild;
    };
    //构建二叉树使用二叉链表

# 非递归写法 #

使用非递归的写法，必然需要其他辅助空间来实现，对于递归改写成非递归的一个做法而言，我们首选的辅助空间就是**栈**结构。  
而我们要做的，就是使用栈去模拟递归的操作（只能操作栈顶）。  
如果想使用栈完全模拟递归的操作，将会对结构体进行更改，这是不允许的。  
那么……在不更改结构体定义的前提下，如何实现非递归写法呢？  
（以下使用了C++ STL中的stack）

## 前序遍历（先序遍历） ##

**思路：**

*  首先要操作，肯定是先入栈，对于前序遍历，就是根节点先入栈并访问。
 *  如果该节点不为空，那么就将其右子树、左子树依次入栈并访问。
    
     *  注意：这里右子树先入栈，因为我们需要先访问左子树，对于栈而言，是FILO（First in Last out），我们就需要将这两个子树入栈顺序调换一下，让右子树先入栈，从而先访问左子树。
 *  栈空即为树遍历完成。

**代码：**

void preOrder(node* root){
        
    	stack<node*> s;//声明一个指针类型的栈
    	s.push(root);//根节点入栈
    	
    	node* p = NULL;//临时变量
    	while (!s.empty()){
        //栈内还有元素，即树还没有遍历完
    		/* 取栈顶元素并将其出栈 */
    		p = s.top();//取栈顶元素做访问
    		s.pop();//每一个元素只访问一次，因此出栈
    		
    		if (p != NULL){
        //该节点不为NULL，说明起码是个叶子节点
    			cout << p->data;//做访问操作，以直接输出为例
    			
    			s.push(p->rchild);//将右子树入栈（可能入NULL）
    			s.push(p->lchild);//将左子树入栈（可能入NULL）
    		}
    	}
    	cout << endl;
    }

## 中序遍历 ##

**思路：**

*  入栈根节点，优先处理左子树
 *  循环入栈左子树（这是一个递归定义），直至为NULL（没有左子树了）
 *  取该节点进行访问
 *  操作其右子树
    
     *  如果其右子树不存在，将p赋值为NULL（使下一次循环的时候直接取栈顶），接着处理栈顶元素即可
     *  如果其右子树存在，将p赋值为其右子树，执行之前的操作
 *  **由于不能提前将根节点入栈（提前入栈会使得程序判定左子树入栈变得更加困难），因此需要给循环一个除了栈空以外的入口，故结束条件不能简单的判定栈是否为空，应当为p为NULL且栈为空**
    
     *  这里另外提一句，既然不可避免的要对循环进行更改，在效率影响几乎等同的情况下，应优先编码（或逻辑实现）更为轻松的一种做实现。

**代码：**

void inOrder(node* root){
        
    	stack<node*> s;//声明一个指针类型的栈
    	node* p = root;//临时变量，赋值为root为了进循环
    	
    	while (p!=NULL || !s.empty()){
        //当栈为空，且p为NULL的时候结束
    		while (p!=NULL){
        //p不为NULL则可能有子树
    			s.push(p);//入栈
    			p = p->lchild;//令p为其左子树，实现其左子树的循环入栈
    		}
    		
    		p = s.top();//去处栈顶元素
    		s.pop();//每个元素只访问一次，将栈顶元素出栈
    		
    		cout << p->data;//做访问
    
    		p = p->rchild;//令p为其节点的右子树，如果右子树存在，即为其右子树，不存在为NULL
    		/* 当然也可以写成如下形式，更便于理解：
    		if (p->rchild!=NULL){
    			p = p->rchild;
    		}
    		else{
    			p = NULL;
    		}
    		*/
    	}
    	cout << endl;
    }

## 后序遍历 ##

**思路：**

*  入栈根节点，但暂时不访问
 *  入栈其子树的一条链
 *  为叶子节点时进行访问并出栈
    
     *  如果访问的节点是栈顶结点的左子树（只需要判断是否为左子树，为右子树的时候不需要其他操作），还需要访问其右子树
 *  结束条件同中序遍历  
    **代码：**

void postOrder(node* root){
        
    	stack<node*> s;//声明一个指针类型的栈
    	node* p = root;//临时变量，先赋值为root，进循环
    	
    	while (p != NULL || !s.empty()){
        //p为NULL且栈空时结束
    		while(p != NULL){
        //可能有子树
    			s.push(p);//入栈
    			/* 分别入栈其子树（注意，这里并不是全部节点都入栈，仅一条链） */
    			if (p->lchild != NULL){
        //优先处理左子树
    				p = p->lchild;
    			}
    			/* 为了解决仅有右子树而没有左子树的情况 */
    			else if(p->rchild != NULL){
        //没有左子树时入栈其右子树
    				p = p->rchild;
    			}
    			else{
        //没有左子树同时没有右子树
    				p = NULL;
    			}
    			/*
    			这里else if和else这两行，可以合并成：
    			else{
    				p = p->rchild;
    			}
    			合并后代码简洁并且效率有略微提升，不合并便于理解，可以自行取舍；
    			*/
    		}
    		
    		p = s.top();//取栈顶元素
    		s.pop();//每个元素仅访问一次，出栈
    		
    		cout << p->data;//访问
    		
    		if (!s.empty() && p == s.top()->lchild){
        //判断当前节点是否为栈顶元素的左子树，注意此时栈不能为空
    			p = s.top()->rchild;//处理其右子树
    		}
    		else{
        
    			p = NULL;
    		}
    	}
    	
    	cout << endl;
    }

*如果发现文章中出现错误，欢迎评论指正。*

[https_blog.csdn.net_weixin_45413689_article_details_108270678]: https://blog.csdn.net/weixin_45413689/article/details/108270678