JAVAは二叉木の遍歴を実現する非再帰アルゴリズム及び再帰アルゴリズム(前序,中序,後序,階層)

/*              ，       ，                     ，            ，        。           ，  ，                              。 
　　 L、D、R         、           ，                ：DLR（        ），LDR（        ），LRD （        ）。 
　　(1)     
　　   ；        ；         
　　(2)     
　　        ；   ；         
　　(3)     
　　        ；        ；    
　　（4）     
　　       ，       。   ，    ，        （        ）（         ） 
*/

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;
	}
}

 
 
import java.util.LinkedList;
import java.util.Stack;

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;
		}
	}
	
	 //level order  
    public static void levelOrder(BTNode p){  
        if(p==null)return;  
        LinkedList<BTNode> queue=new LinkedList<BTNode>();  
        queue.add(p);  
        while(!queue.isEmpty()){  
        	BTNode temp=queue.remove();  
           visit(temp);
            if(temp.getLeft()!=null){  
                queue.add(temp.getLeft());  
            }  
            if(temp.getRight() != null){  
                queue.add(temp.getRight());  
            }  
        }  
    }  

	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();
		System.out.print("level:");
		levelOrder(tree.getRoot());
		System.out.println();
	}
}