二叉树中序遍历和后序遍历的递归与非递归算法

迷南。 2022-09-27 15:22 177阅读 0赞

昨天写的前序遍历的递归与非递归算法，在非递归算法中主要还是借用到了栈这一工具，其实在中序遍历和后序遍历中依旧可以理由栈的特性来进行非递归的遍历 操作。

## 1.中序遍历 ##

### 1.1 中序遍历的递归算法 ###

二叉树的构造以在上一篇博文中有说到，这里就不再重复了，直接上代码

public void InOrderTraverse(TreeNode T){
    		
    		if(T==null){
    			return;
    		}
    		InOrderTraverse(T.lchild);
    		System.out.println(T.data);
    		InOrderTraverse(T.rchild);
    		
    	}

运行结果如下图

![Center][]

### 1.2 中序遍历的非递归算法 ###

非递归算法的思路主要分为 将结点压入栈 和 从栈中弹出结点两部分，具体代码如下

public void InOrderWithoutRecursion(TreeNode T){
    		
    		Stack<TreeNode> stack = new Stack<TreeNode>();
    		TreeNode p;
    		while(T!=null||!stack.empty()){
    			
    			while(T!=null){             //将结点压进栈中
    				stack.push(T);
    				T = T.lchild;
    			}
    			
    			if(!stack.empty()){         //将栈中的结点弹出
    				p = stack.peek();  
    				stack.pop();
    				System.out.println(p.data); 				
    				T = p.rchild;			
    			}
    		}
    				
    	}

运行结果如下

![Center][]

## 2.后序遍历 ##

### 2.1后序遍历的递归算法 ###

其实在对比之后可以发现，前序、中序、后序算法的递归算法相似度非常高，差别仅仅在于对结点进行处理的那行或者那段代码的位置不同，所以非常好记，看看具体代码

public void postOrderTraverse(TreeNode T){
    		
    		if(T==null){
    			return;
    		}
    		postOrderTraverse(T.lchild);
    		postOrderTraverse(T.rchild);
    		System.out.println(T.data); //对结点进行处理，这里以输出代替
    		
    	}

输出结果为

![Center 1][]

### 2.2 后序遍历的非递归算法 ###

后序遍历的非递归算法也主要分为 将结点压入栈 和 从栈中弹出结点 两部分，但是后序遍历比中序遍历多了HashMap用来作为标记，当value为1时，表示key对应的结点的右孩子已经被便利过，value为0时表示未遍历过。

public void postOrderWithoutRecursion(TreeNode T){
    		
    		Map<Object,Integer> flag = new HashMap<Object,Integer>(); //结点右孩子是否被遍历过的标记
    		Stack<TreeNode> stack = new Stack<TreeNode>();
    		TreeNode p;
    		while(T!=null||!stack.empty()){
    			
    			while(T!=null){
    				stack.push(T);
    				flag.put(T.data, 0);       //当结点被压入栈时，将value初始化为0
    				T = T.lchild;
    			}
    			
    			if(!stack.empty()){
    				p = stack.peek();				
    				if(p.rchild!=null&&flag.get(p.data)!=1){
    					T = p.rchild;
    					flag.put(p.data, 1);     //表示p结点的右孩子已经被遍历过
    				}else{
    					stack.pop();
    					System.out.println(p.data);
    				}							
    			}
    			
    		}
    	}

输出结果为

![Center 1][]

后序遍历非递归修改版

public void postOrder(TreeNode root){
    		Stack<TreeNode> stack = new Stack<TreeNode>();
    		TreeNode hasOrder = null;
    		TreeNode node;
    		while(root!=null||!stack.empty()){
    			while(root!=null){
    				stack.push(root);
    				root = root.left;				
    			}
    			
    			if(!stack.empty()){
    				node = stack.peek();
    				if(node.right!=null&&hasOrder!=node.right){
    					root = node.right;
    				}else{
    					System.out.println(node.value);
    					hasOrder = node;
    					stack.pop();
    				}
    				
    			}
    	
    	    }
    	}

[Center]: /images/20220708/18fd38fd126b431cba4da5a7662204f4.png
[Center 1]: /images/20220708/ee7f01c963a146d588c2018c45dd84b0.png