package binTree;import java.util.Stack;/** * @author bin.zhang * @version 2017年8月29日 上午10:22:01 */public class BinTreeTraversal { public static void main(String[] args) {  System.out.print("前序：");  Traversal.preOrder();  Traversal.preOrderRecursion(Traversal.createBinTree());  System.out.print("中序：");  Traversal.inOrder();  Traversal.inOrderRecursion(Traversal.createBinTree());  System.out.print("后序：");  Traversal.postOrder();  Traversal.postOrderRecursion(Traversal.createBinTree()); }}/** * 節點數據結構 *  * @author bin.zhang * @version 2017年8月30日 上午11:49:38 */class BinTreeNode { BinTreeNode() { } BinTreeNode(char data, int flag, BinTreeNode lchild, BinTreeNode rchild) {  this.data = data;  this.flag = flag;  this.lchild = lchild;  this.rchild = rchild; } char data; int flag; BinTreeNode lchild, rchild;}class Traversal { /**  * 創建一棵二叉樹  *   * @author bin.zhang  * @return 根節點  */ public static BinTreeNode createBinTree() {  BinTreeNode R3 = new BinTreeNode('F', 0, null, null);  BinTreeNode L2 = new BinTreeNode('D', 0, null, null);  BinTreeNode R2 = new BinTreeNode('E', 0, null, R3);  BinTreeNode L1 = new BinTreeNode('B', 0, L2, R2);  BinTreeNode R1 = new BinTreeNode('C', 0, null, null);  BinTreeNode T = new BinTreeNode('A', 0, L1, R1);  return T; } // 前序 public static void preOrder() {  BinTreeNode p = createBinTree();  Stack<BinTreeNode> stack = new Stack<BinTreeNode>();  while (p != null || !stack.empty()) {   if (p != null) {    System.out.print(p.data);    stack.push(p);    p = p.lchild;   }   else {    p = stack.pop();    p = p.rchild;   }  }  System.out.println(); } // 前序遞歸 public static void preOrderRecursion(BinTreeNode top) {  if (top != null) {   System.out.println(top.data);   preOrderRecursion(top.lchild);   preOrderRecursion(top.rchild);  } } // 中序 public static void inOrder() {  BinTreeNode p = createBinTree();  Stack<BinTreeNode> stack = new Stack<BinTreeNode>();  while (p != null || !stack.empty()) {   if (p != null) {    stack.push(p);    p = p.lchild;   }   else {    p = stack.pop();    System.out.print(p.data);    p = p.rchild;   }  }  System.out.println(); } // 中序遞歸 public static void inOrderRecursion(BinTreeNode top) {  if (top != null) {   inOrderRecursion(top.lchild);   System.out.println(top.data);   inOrderRecursion(top.rchild);  } } // 后序 public static void postOrder() {  BinTreeNode p = createBinTree();  Stack<BinTreeNode> stack = new Stack<BinTreeNode>(); // 初始化棧  int mark = 1; // 轉向標志  while (p != null || !stack.empty()) { // 遍歷   if (p != null && mark != 0) {    stack.push(p);    p = p.lchild;   }// 轉向左子樹   else {    p = stack.pop();    p.flag++; // 退棧    if (p.flag == 1) {     stack.push(p);     p = p.rchild;     mark = 1;    } // 轉向右子樹    else if (p.flag == 2 && !stack.empty()) { // 輸出結點     System.out.print(p.data);     mark = 0;    }    else if (p.flag == 2 && stack.empty()) { // 輸出根結點并退出     System.out.print(p.data);     break;    }   } // if-else  } // while  System.out.println(); } // 后序遞歸 public static void postOrderRecursion(BinTreeNode top) {  if (top != null) {   postOrderRecursion(top.lchild);   postOrderRecursion(top.rchild);   System.out.println(top.data);  } }}