二叉树的遍历

引言

• 本文展示了二叉树的前序遍历、中序遍历、后序遍历;
• 每种遍历均用递归和非递归的方法实现。
• 递归的方法明显比非递归的方法容易理解。
• 非递归的实现方式有很多种，本文给出了用一个栈实现的方法。

程序

package test;

import java.util.Stack;

public class Test {

	public static class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	public static TreeNode BinaryTree(int[] array) {
		return makeBinaryTreeByArray(array, 1);
	}

	public static TreeNode makeBinaryTreeByArray(int[] array, int index) {
		if (index < array.length) {
			int value = array[index];
			if (value != 0) {
				TreeNode t = new TreeNode(value);
				array[index] = 0;
				t.left = makeBinaryTreeByArray(array, index * 2);
				t.right = makeBinaryTreeByArray(array, index * 2 + 1);
				return t;
			}
		}
		return null;
	}
	
	//前序遍历 递归实现
	public static void preTraversal(TreeNode root){
		if(root==null){
			return;
		}
		
		System.out.print(root.val+" ");
		preTraversal(root.left);
		preTraversal(root.right);
	}
	
	//前序遍历 非递归实现(栈)
	public static void preTraversal1(TreeNode root){
		Stack<TreeNode> stack = new Stack<>();
		if(root==null){
			return;
		}
		
		stack.push(root);
		while(!stack.isEmpty()){
			TreeNode tmp = stack.pop();
			System.out.print(tmp.val+" ");
			if(tmp.right!=null){
				stack.push(tmp.right);
			}
			if(tmp.left!=null){
				stack.push(tmp.left);
			}
		}
	}
	
	//中序遍历 递归实现
	public static void midTraversal(TreeNode root){
		if(root==null){
			return;
		}
		
		if(root.left!=null){
			midTraversal(root.left);
		}
		
		System.out.print(root.val+" ");
		
		if(root.right!=null){
			midTraversal(root.right);
		}
	}
	
	//中序遍历 非递归实现(栈)
	public static void midTraversal1(TreeNode root){
		Stack<TreeNode> stack = new Stack<>();    
		TreeNode node = root;    
        while (node != null || stack.size() > 0) {    
            while (node != null) {    
                stack.push(node);    
                node = node.left;    
            }    
            if (stack.size() > 0) {    
                node = stack.pop();    
                System.out.print(node.val+" ");  
                node = node.right;    
            }    
        }   
	}
	
	//后序遍历 递归实现
	public static void behTraversal(TreeNode root){
		if(root==null){
			return;
		}
		
		if(root.left!=null){
			behTraversal(root.left);
		}
		
		if(root.right!=null){
			behTraversal(root.right);
		}
		
		System.out.print(root.val+" ");
	}
	
	//后序遍历 非递归实现(栈)
	public static void behTraversal1(TreeNode root){
		Stack<TreeNode> stack = new Stack<TreeNode>();    
		TreeNode node = root, prev = root;    
        while (node != null || stack.size() > 0) {    
            while (node != null) {    
                stack.push(node);    
                node = node.left;    
            }    
            if (stack.size() > 0) {    
            	TreeNode temp = stack.peek().right;    
                if (temp == null || temp == prev) {    
                    node = stack.pop();    
                    System.out.print(node.val+" ");    
                    prev = node;    
                    node = null;    
                } else {    
                    node = temp;    
                }    
            }    
        } 
	}

	/**       *                  13      *                 /  \      *               65    5      *              /  \    \      *             97  25   37      *            /    /\   /      *           22   4 28 32      */  
     *                  13 
     *                 /  \ 
     *               65    5 
     *              /  \    \ 
     *             97  25   37 
     *            /    /\   / 
     *           22   4 28 32 
     */
	public static void main(String[] args) {
		int[] arr = { 0, 13, 65, 5, 97, 25, 0, 37, 22, 0, 4, 28, 0, 0, 32, 0 };
		TreeNode root = BinaryTree(arr);
		preTraversal(root);  //13 65 97 22 25 4 28 5 37 32
		System.out.print("\n");
		preTraversal1(root);  //13 65 97 22 25 4 28 5 37 32 
		System.out.print("\n");
		midTraversal(root);  //22 97 65 4 25 28 13 5 32 37 
		System.out.print("\n");
		midTraversal1(root);  //22 97 65 4 25 28 13 5 32 37 
		System.out.print("\n");
		behTraversal(root);  //22 97 4 28 25 65 32 37 5 13 
		System.out.print("\n");
		behTraversal1(root);  //22 97 4 28 25 65 32 37 5 13 
	}
}