JAVA語言實現二叉樹的層次遍歷的非遞歸算法及遞歸算法

/* 二叉樹節點 /
public class BTNode {
　　private char key;
　　private BTNode left, right;
　　public BTNode(char key) {
　　　　this(key, null, null);
　　}
　　public BTNode(char key, BTNode left, BTNode right) {
　　　　this.key = key;
　　　　this.left = left;
　　　　this.right = right;
　　}
　　public char getKey() {
　　　　return key;
　　}
　　public void setKey(char key) {
　　　　this.key = key;
　　}
　　public BTNode getLeft() {
　　　　return left;
　　}
　　public void setLeft(BTNode left) {
　　　　this.left = left;
　　}
　　public BTNode getRight() {
　　　　return right;
　　}
　　public void setRight(BTNode right) {
　　　　this.right = right;
　　}
}

/ 二叉樹遍歷 */
public class BinTree {
　　protected BTNode root;
　　public BinTree(BTNode root) {
　　　　this.root = root;
　　}
　　public BTNode getRoot() {
　　　　return root;
　　}
　　/ 構造樹 /
　　public static BTNode init() {
　　　　BTNode a = new BTNode('A');
　　　　BTNode b = new BTNode('B', null, a);
　　　　BTNode c = new BTNode('C');
　　　　BTNode d = new BTNode('D', b, c);
　　　　BTNode e = new BTNode('E');
　　　　BTNode f = new BTNode('F', e, null);
　　　　BTNode g = new BTNode('G', null, f);
　　　　BTNode h = new BTNode('H', d, g);
　　　　return h;// root
　　}
　　/** 訪問節點 /
　　public static void visit(BTNode p) {
　　　　System.out.print(p.getKey() + " ");
　　}
　　/ 遞歸實現前序遍歷 */
　　protected static void preorder(BTNode p) {
　　　　if (p != null) {
　　　　　　visit(p);
　　　　　　preorder(p.getLeft());
　　　　　　preorder(p.getRight());
　　　　}
　　}
　　/ 遞歸實現中序遍歷 /
　　protected static void inorder(BTNode p) {
　　　　if (p != null) {
　　　　　　inorder(p.getLeft());
　　　　　　visit(p);
　　　　　　inorder(p.getRight());
　　　　}
　　}
　　/** 遞歸實現后序遍歷 /
　　protected static void postorder(BTNode p) {
　　　　if (p != null) {
　　　　　　postorder(p.getLeft());
　　　　　　postorder(p.getRight());
　　　　　　visit(p);
　　　　}
　　}
　　/ 非遞歸實現前序遍歷 */
　　protected static void iterativePreorder(BTNode p) {
　　　　Stack<BTNode> stack = new Stack<BTNode>();
　　　　if (p != null) {
　　　　　　stack.push(p);
　　　　　　while (!stack.empty()) {
　　　　　　　　p = stack.pop();
　　　　　　　　visit(p);
　　　　　　　　if (p.getRight() != null)
　　　　　　　　　　stack.push(p.getRight());
　　　　　　　　if (p.getLeft() != null)
　　　　　　　　　　stack.push(p.getLeft());
　　　　　　}
　　　　}
　　}
　　/ 非遞歸實現后序遍歷 /
　　protected static void iterativePostorder(BTNode p) {
　　　　BTNode q = p;
　　　　Stack<BTNode> stack = new Stack<BTNode>();
　　　　while (p != null) {
　　　　　　// 左子樹入棧
　　　　　　for (; p.getLeft() != null; p = p.getLeft())
　　　　　　　　stack.push(p);
　　　　　　// 當前節點無右子或右子已經輸出
　　　　　　while (p != null && (p.getRight() == null || p.getRight() == q)) {
　　　　　　　　visit(p);
　　　　　　　　q = p;// 記錄上一個已輸出節點
　　　　　　　　if (stack.empty())
　　　　　　　　　　return;
　　　　　　　　p = stack.pop();
　　　　　　}
　　　　　　// 處理右子
　　　　　　stack.push(p);
　　　　　　p = p.getRight();
　　　　}
　　}
　　/** 非遞歸實現中序遍歷 /
　　protected static void iterativeInorder(BTNode p) {
　　　　Stack<BTNode> stack = new Stack<BTNode>();
　　　　while (p != null) {
　　　　　　while (p != null) {
　　　　　　　　if (p.getRight() != null)
　　　　　　　　　　stack.push(p.getRight());// 當前節點右子入棧
　　　　　　　　stack.push(p);// 當前節點入棧
　　　　　　　　p = p.getLeft();
　　　　　　}
　　　　　　p = stack.pop();
　　　　　　while (!stack.empty() && p.getRight() == null) {
　　　　　　　　visit(p);
　　　　　　　　p = stack.pop();
　　　　　　}
　　　　　　visit(p);
　　　　　　if (!stack.empty())
　　　　　　　　p = stack.pop();
　　　　　　else
　　　　　　　　p = null;
　　　　}
　　}
　　public static void main(String[] args) {
　　　　BinTree tree = new BinTree(init());
　　　　System.out.print(" Pre-Order:");
　　　　preorder(tree.getRoot());
　　　　System.out.println();
　　　　System.out.print("　In-Order:");
　　　　inorder(tree.getRoot());
　　　　System.out.println();
　　　　System.out.print("Post-Order:");
　　　　postorder(tree.getRoot());
　　　　System.out.println();
　　　　System.out.print(" Pre-Order:");
　　　　iterativePreorder(tree.getRoot());
　　　　System.out.println();
　　　　System.out.print("　In-Order:");
　　　　iterativeInorder(tree.getRoot());
　　　　System.out.println();
　　　　System.out.print("Post-Order:");
　　　　iterativePostorder(tree.getRoot());
　　　　System.out.println();
　　}
}</pre>
/*遍歷是對樹的一種最基本的運算，所謂遍歷二叉樹，就是按一定的規則和順序走遍二叉樹的所有結點，使每一個結點都被訪問一次，而且只被訪問一次。由于二叉樹是非線性結構，因此，樹的遍歷實質上是將二叉樹的各個結點轉換成為一個線性序列來表示。

　　設L、D、R分別表示遍歷左子樹、訪問根結點和遍歷右子樹， 則對一棵二叉樹的遍歷有三種情況：DLR（稱為先根次序遍歷），LDR（稱為中根次序遍歷），LRD （稱為后根次序遍歷）。
　　(1)先序遍歷
　　訪問根；按先序遍歷左子樹；按先序遍歷右子樹
　　(2)中序遍歷
　　按中序遍歷左子樹；訪問根；按中序遍歷右子樹
　　(3)后序遍歷
　　按后序遍歷左子樹；按后序遍歷右子樹；訪問根
　　（4）層次遍歷
　　即按照層次訪問，通常用隊列來做。訪問根，訪問子女，再訪問子女的子女（越往后的層次越低）（兩個子女的級別相同）
*/</pre>