非遞歸實現二叉樹的遍歷

非遞歸實現二叉樹的遍歷

二叉樹遍歷是樹的最基本算法之一，是二叉樹上進行其它運算之基礎。

所謂遍歷(Traversal)是指沿著某條搜索路線，依次對樹中每個結點均做一次且僅做一次訪問。

訪問結點所做的操作依賴於具體的應用問題。
① 前序遍歷(PreorderTraversal亦稱（先序遍歷））
——訪問根結點的操作發生在遍歷其左右子樹之前。
② 中序遍歷(InorderTraversal)
——訪問根結點的操作發生在遍歷其左右子樹之中（間）。
③ 後序遍歷(PostorderTraversal)
——訪問根結點的操作發生在遍歷其左右子樹之後。
④ 層次遍歷(LevelTraversal)

——訪問從根結點開始，逐層訪問

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Stack;

//二叉樹的鏈式結構
class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;

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

public class TestTraversalTreeNode {
	/**
	 * 線序遍歷
	 * 
	 * @param root   樹根
	 * @return
	 */
	public static ArrayList preorderTraversal(TreeNode root) {
		ArrayList result = new ArrayList();
		if (root == null)
			return result;
		Stack stack = new Stack();
		stack.push(root);
		while (!stack.isEmpty()) {
			TreeNode t = stack.pop();
			result.add(t.val);
			//先檢查push右結點
			if (t.right != null) {
				stack.push(t.right);
			}
			if (t.left != null) {
				stack.push(t.left);
			}
		}
		return result;
	}

	/**
	 * 中序遍歷
	 * 
	 * @param root   樹根
	 * @return
	 */
	public static ArrayList inorderTraversal(TreeNode root) {
		ArrayList result = new ArrayList();
		if (root == null)
			return result;
		Stack stack = new Stack();
		TreeNode p = root;
		//如果有左結點則一直push
		while (!stack.isEmpty() || p != null) {
			if (p != null) {
				stack.push(p);
				p = p.left;
			} else {
				TreeNode n = stack.pop();
				result.add(n.val);
				p = n.right;
			}
		}
		return result;
	}

	/**
	 * 後序遍歷
	 * 
	 * @param root  樹根
	 * @return
	 */
	public static ArrayList postorderTraversal(TreeNode root) {
		ArrayList result = new ArrayList();
		if (root == null) {
			return result;
		}
		Stack stack = new Stack();
		stack.push(root);
		TreeNode prev = null;// 記錄當前結點的上一個結點
		while (!stack.empty()) {
			TreeNode curr = stack.peek();
			// 查看當前結點是否是葉節點，是的話就訪問
			if (prev == null || prev.left == curr || prev.right == curr) {
				if (curr.left != null) {
					stack.push(curr.left);
				} else if (curr.right != null) {
					stack.push(curr.right);
				} else {// 當前結點是葉節點
					stack.pop();
					result.add(curr.val);
				}
				// 查看prev是否是的當前結點左結點
			} else if (curr.left == prev) {
				if (curr.right != null) {
					stack.push(curr.right);
				} else {
					stack.pop();
					result.add(curr.val);
				}
				// 查看prev是否是當前結點的右結點
			} else if (curr.right == prev) {
				stack.pop();
				result.add(curr.val);
			}
			prev = curr;
		}
		return result;
	}

	/**
	 * 層次遍歷
	 * 
	 * @param root  樹根
	 * @return
	 */
	public static ArrayList levelTraversal(TreeNode root) {
		ArrayList result = new ArrayList();
		LinkedList current = new LinkedList();
		if (root != null) {
			current.add(root);
			result.add(root.val);
		}
		while (current.size() > 0) {
			LinkedList parents = current;
			current = new LinkedList();
			for (TreeNode parent : parents) {
				if (parent.left != null) {
					current.add(parent.left);
					result.add(parent.left.val);
				}
				if (parent.right != null) {
					current.add(parent.right);
					result.add(parent.right.val);
				}
			}
		}
		return result;
	}

	/**
	 * 遍歷二叉樹的第k行
	 * 
	 * @param root 二叉樹根
	 * @param k 第k行
	 * @return 第k行的遍歷
	 */
	public static String findLevelList2(TreeNode root, int k) {
		ArrayList result = new ArrayList();
		LinkedList current = new LinkedList();
		if (root != null) {
			current.add(root);
		}
		int count = 0;
		while (current.size() > 0) {
			result.add(current);
			if (count == k) {
				return listToString(current);
			}
			count++;
			LinkedList parents = current;
			current = new LinkedList();
			for (TreeNode parent : parents) {
				if (parent.left != null) {
					current.add(parent.left);
				}
				if (parent.right != null) {
					current.add(parent.right);
				}
			}
		}
		return null;
	}

	/**
	 * 鏈表的結點轉化為字符串進行輸出
	 * @param list
	 * @return
	 */
	public static String listToString(LinkedList list) {
		int[] arr = new int[list.size()];
		int i = 0;
		for (TreeNode node : list) {
			arr[i] = node.val;
			i++;
		}
		return Arrays.toString(arr);
	}

	public static void main(String[] args) {
		TreeNode root = new TreeNode(1);
		root.left = new TreeNode(2);
		root.right = new TreeNode(3);
		root.left.left = new TreeNode(4);
		root.left.right = new TreeNode(5);
		System.out.println("前序：" + preorderTraversal(root).toString());
		System.out.println("中序：" + inorderTraversal(root).toString());
		System.out.println("後序：" + postorderTraversal(root).toString());
		System.out.println("順序：" + levelTraversal(root).toString());
		System.out.println("K序：" + findLevelList2(root, 2));
	}
}