java實作二叉樹周遊(先序中序後序)

二叉樹的周遊，主要有先序中序和後序周遊，三個的遞歸實作都比較簡單，而非遞歸實作略複雜。

先周遊之前，我們先定義一個節點

public class TreeNode {
	private int data;
	private TreeNode left;
	private TreeNode right;
	//get set方法省略
}
           

遞歸實作

1. 先序周遊

public void preOrder(TreeNode root){
	if(root!=null){
		System.out.println(root.getData());
		preOrder(root.getLeft());
		preOrder(root.getRight());
	}
}
           

1. 中序周遊

public void inOrder(TreeNode root){
	if(root!=null){
		inOrder(root.getLeft());
		System.out.println(root.getData());
		inOrder(root.getRight());
	}
	
}
           

1. 後序周遊

public void postOrder(TreeNode root){
	if(root!=null){
		postOrder(root.getLeft());
		postOrder(root.getRight());
		System.out.println(root.getData());
	}
}
           

非遞歸實作

1. 先序周遊

public void preOrder(TreeNode root){
	Stack<TreeNode> stack = new Stack<TreeNode>();
	while(true){
		while(root!=null){
			System.out.println(root.getData());
			stack.push(root);
			root = root.getLeft();
		}
		if(stack.isEmpty()) break;
		root = stack.pop();
		root = root.getRight();
	}
}
           

1. 中序周遊

public void inOrder(TreeNode root){
	Stack<TreeNode> stack = new Stack<TreeNode>();
	while(true){
		while(root!=null){
			stack.push(root);
			root = root.getLeft();
		}
		if(!stack.isEmpty()) break;
		root = stack.pop();
		System.out.println(root.getData());
		root = root.getRight();
	}
}
           

1. 後序周遊(兩個棧實作)

public void postOrder(TreeNode root){
	if(root==null) return;
	Stack<TreeNode> stack1 = new Stack<TreeNode>();
	Stack<TreeNode> stack2 = new Stack<TreeNode>();
	stack1.push(root);
	while(!stack1.isEmpty()){
		TreeNode node = stack1.pop();
		stack2.push(node);
		if(node.getLeft()!=null){
			stack1.push(node.getLeft());
		}
		if(node.getRight()!=null){
			stack1.push(node.getRight());
		}
	}
	while(!stack2.isEmpty())
		System.out.println(stack2.pop().getData());
	
}