Java代码如下：
package com.ds.tree; import com.ds.list.MyStack; /** * 二叉树 */ public class BinaryTree { private static int index = 0; static class Node { public char data; public Node left; public Node right; public boolean isVisited = false; //是否被访问了，在后序非递归算法中用到 } private Node root; //先序创建二叉树，数据域为'#'表示空节点 public BinaryTree create(char[] data) { if(data == null || data.length == 0) { return null; } index = 0; root = createBinaryTree(data); return this; } //先序创建二叉树的递归算法 private Node createBinaryTree(char[] data) { char c = data[index++]; Node node = new Node(); if(c == '#') { node.data = '#'; node.left = null; node.right = null; }else { node.data = c; node.left = createBinaryTree(data); node.right = createBinaryTree(data); } return node; } //获取根节点 public Node getRoot() { return this.root; } //先序遍历 public void preOrder() { preorder(root); System.out.println(); } //先序遍历递归算法 private void preorder(Node node) { if(!isEmptyNode(node)) { visit(node); preorder(node.left); preorder(node.right); } } //先序遍历非递归算法 public void _preOrder() { MyStack<Node> stack = new MyStack<>(); Node p = this.root; while(!isEmptyNode(p) || !stack.isEmpty()) { if(!isEmptyNode(p)) { //判断节点是否为空 visit(p); stack.push(p); p = p.left; }else { p = stack.pop(); p = p.right; } } System.out.println(); } //中序遍历 public void inOrder() { inorder(root); System.out.println(); } //中序遍历递归算法 private void inorder(Node node) { if(!isEmptyNode(node)) { inorder(node.left); visit(node); inorder(node.right); } } //中序遍历非递归算法 public void _inOrder() { MyStack<Node> stack = new MyStack<>(); Node p = this.root; while(!isEmptyNode(p) || !stack.isEmpty()) { if(!isEmptyNode(p)) { stack.push(p); p = p.left; }else { p = stack.pop(); visit(p); p = p.right; } } System.out.println(); } //后序遍历 public void postOrder() { postorder(root); System.out.println(); } //后序遍历递归算法 private void postorder(Node node) { if(!isEmptyNode(node)) { postorder(node.left); postorder(node.right); visit(node); } } //后序遍历非递归算法 public void _postOrder() { MyStack<Node> stack = new MyStack<>(); Node p = this.root; while(!isEmptyNode(p) || !stack.isEmpty()) { if(!isEmptyNode(p)) { stack.push(p); p = p.left; }else { p = stack.peek(); //判断p的左右孩子节点是否都被访问过，如果都被访问过，则访问p节点 if(isChildrenVisited(p)) { visit(p); p.isVisited = true; stack.pop(); p = null; }else { p = p.right; } } } System.out.println(); } //判断一个节点是否为空节点 private boolean isEmptyNode(Node node) { return node == null || (node != null && node.data == '#'); } //判断一个节点的两个孩子节点是否都被访问了 private boolean isChildrenVisited(Node node) { if(isEmptyNode(node.left) && isEmptyNode(node.right)) { //空节点默认是被访问过的 return true; } return node.left.isVisited && node.right.isVisited; } //访问节点，打印节点数据域 private void visit(Node node) { System.out.print(node.data + " "); } public static void main(String[] args) { String s = "-+a##*b##-c##d##/e##f##"; char[] data = s.toCharArray(); BinaryTree tree = new BinaryTree().create(data); System.out.println("pre order result: "); tree.preOrder(); System.out.println("_pre order result: "); tree._preOrder(); System.out.println("in order result: "); tree.inOrder(); System.out.println("_in order result: "); tree._inOrder(); System.out.println("post order result: "); tree.postOrder(); System.out.println("_post order result: "); tree._postOrder(); } }MyStack为自定义的栈结构，参见：http://blog.csdn.net/yubo_725/article/details/52195459
代码运行结果如下：
