二叉樹的周遊（Java）

二叉樹的周遊分為：前序周遊，中序周遊，後序周遊，層次周遊。本文主要講述二叉樹的前中後序周遊的遞歸實作和非遞歸實作（Java代碼實作）。

先上一個二叉樹，我們來看看它的前中後序輸出分别是什麼：

接下來我們用代碼實作：

class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode(int x) {
		val = x;
	}
}

public class Tree {
	//前序遞歸使用
	List<Integer> bforder=new ArrayList<>();
	//中序遞歸使用
	List<Integer> inorder=new ArrayList<>();
	//後序遞歸使用
	List<Integer> aforder=new ArrayList<>();
	
	//遞歸前序周遊二叉樹
	public List<Integer> bforderTraversal(TreeNode root) {
		bforder(root);
		return bforder;
	}
	void bforder(TreeNode root){
		if(root==null){
			return;
		}
		bforder.add(root.val);
		bforder(root.left);
		bforder(root.right);
	}
	
	//不遞歸前序周遊二叉樹
	public List<Integer> bforderTraversal1(TreeNode root) {
		List<Integer> res= new ArrayList<>();
		Stack<TreeNode> s=new Stack<>();
		if(root==null){
			return res;
		}
		s.push(root);
		while(!s.isEmpty()){
			TreeNode p=s.pop();
			res.add(p.val);
			if(p.right!=null){
				s.push(p.right);
			}
			if(p.left!=null){
				s.push(p.left);
			}
		}
		return res;
	}
	
	//遞歸中序周遊二叉樹
	public List<Integer> inorderTraversal(TreeNode root) {
		inorder(root);
		return inorder;
	}
	void inorder(TreeNode root){
		if(root==null){
			return;
		}
		inorder(root.left);
		inorder.add(root.val);
		inorder(root.right);
	}
	//非遞歸中序周遊二叉樹
	public List<Integer> inorderTraversal1(TreeNode root) {
		List<Integer> res= new ArrayList<>();
		if(root==null){
			return res;
		}
		Stack<TreeNode> s=new Stack<>();
		TreeNode p=root;
		while(p!=null || !s.isEmpty()){
			while(p!=null){
				s.push(p);
				p=p.left;
			}
			if(!s.empty()){
				p=s.pop();
				res.add(p.val);
				p=p.right;
			}
		}
		return res;
	}
	
	//遞歸後序周遊二叉樹
	public List<Integer> aforderTraversal(TreeNode root) {
		aforder(root);
		return aforder;
	}
	void aforder(TreeNode root){
		if(root==null){
			return;
		}
		aforder(root.left);
		aforder(root.right);
		aforder.add(root.val);
	}
	//非遞歸後序周遊二叉樹
	public List<Integer> aforderTraversal1(TreeNode root) {
		List<Integer> res= new ArrayList<>();
		Stack<TreeNode> s=new Stack<>();
		if(root==null){
			return res;
		}
		s.push(root);
		TreeNode cur=root;
		TreeNode pre=null;
		while(!s.isEmpty()){
			cur=s.peek();
            if((cur.left==null&&cur.right==null)||((pre!=null)&&(pre==cur.left||pre==cur.right))) {
                res.add(cur.val);
                s.pop();
                pre=cur; //注意這裡，pre僅僅在輸出了cur的時候下才更新。
            }else{
                if(cur.right!=null)
                    s.push(cur.right);
                if(cur.left!=null)
                    s.push(cur.left);
            }
		}
		return res;
	}
	//非遞歸後序周遊二叉樹
	public List<Integer> aforderTraversal2(TreeNode root) {
		List<Integer> res= new ArrayList<>();
		Stack<TreeNode> s=new Stack<>();
		if(root==null){
			return res;
		}
		s.push(root);
		while(!s.isEmpty()){
			TreeNode p=s.pop();
			res.add(p.val);
			if(p.left!=null){
				s.push(p.left);
			}
			if(p.right!=null){
				s.push(p.right);
			}
		}
		Collections.reverse(res);
		return res;
	}
	
	
	@Test
	public void test(){
		TreeNode root =new TreeNode(10);
		TreeNode node1=new TreeNode(2);
		TreeNode node2=new TreeNode(5);
		TreeNode node3=new TreeNode(8);
		TreeNode node4=new TreeNode(7);
		TreeNode node5=new TreeNode(6);
		root.left=node1;
		root.right=node2;
		node1.left=node3;
		node2.left=node4;
		node2.right=node5;
		
		//測試前序周遊(非遞歸)
		System.out.println("前序周遊(非遞歸):");
		System.out.println(bforderTraversal1(root));
		//測試前序周遊(遞歸)
		System.out.println("前序周遊(遞歸):");
		System.out.println(bforderTraversal(root));
		
		
		//測試中序周遊(非遞歸)
		System.out.println("中序周遊(非遞歸):");
		System.out.println(inorderTraversal1(root));
		//測試中序周遊(遞歸)
		System.out.println("中序周遊(遞歸):");
		System.out.println(inorderTraversal(root));
		
		
		//測試後序周遊(非遞歸)
		System.out.println("後序周遊(非遞歸):");
		System.out.println(aforderTraversal2(root));
		//測試後序周遊(遞歸)
		System.out.println("後序周遊(遞歸):");
		System.out.println(aforderTraversal(root));
	}
}
           

運作結果：

前序周遊(非遞歸): [10, 2, 8, 5, 7, 6] 前序周遊(遞歸): [10, 2, 8, 5, 7, 6] 中序周遊(非遞歸): [8, 2, 10, 7, 5, 6] 中序周遊(遞歸): [8, 2, 10, 7, 5, 6] 後序周遊(非遞歸): [8, 2, 7, 6, 5, 10] 後序周遊(遞歸): [8, 2, 7, 6, 5, 10]