1、import java.util.Stack;public class MyTreepublic static void main(String s)new MyTree();public MyTree()TreeNode root = init();/初始化二叉树并返回根节点System.out.println(“递归先序遍历“);preorder(root);System.out.println();System.out.println(“递归中序遍历“);inorder(root);System.out.println();System.out.println(“递归后续遍历“);pos
2、order(root);System.out.println();System.out.println(“非递归先序遍历“);preorder(root);System.out.println();System.out.println(“非递归中序遍历“);_inorder(root);System.out.println();System.out.println(“非递归后续遍历“);_posorder(root);System.out.println();public void preorder(TreeNode root)/递归二叉树的前序遍历if(root != null)System
3、.out.print(root.getValue();/访问节点值preorder(root.getLeft();preorder(root.getRight();public void _preorder(TreeNode root)/非递归二叉树的前序遍历Stack stack = new Stack();/定义堆栈存储while(!(root = null /访问节点if(root != null)/找到当前节点最深的左子树stack.push(root);/将当前左子树入栈root = root.getLeft();else/当左子树到底时，开始访问右节点root = stack.po
4、p();/当前节点出栈root = root.getRight();/指向右子树public void inorder(TreeNode root)/递归中序遍历if(root != null)inorder(root.getLeft();System.out.print(root.getValue();inorder(root.getRight();public void _inorder(TreeNode root)/非递归中序遍历Stack stack = new Stack();while(!(root = null root = root.getLeft();/找到最深左子树后开始访
5、问root = stack.pop();System.out.print(root.getValue();/开始寻找右子树root = root.getRight();public void posorder(TreeNode root)/递归后序遍历if(root != null)posorder(root.getLeft();posorder(root.getRight();System.out.print(root.getValue();/非递归的后续遍历需要两次访问节点，最后一次访问节点为准private int sign = 0;/得当当前访问节点的次数public void _po
6、sorder(TreeNode root)Stack stack = new Stack();/定义一个可以存放 TreeNode 和 Integer 的栈while(!(root = null /将当前节点压入堆栈stack.push(1);/并标记当前访问节点的次数root = root.getLeft();else/找到最深左子树后while(!stack.isEmpty()sign = (Integer)stack.pop();/出栈标记root = (TreeNode)stack.pop();/出栈节点if(sign = 1)/地一次访问节点stack.push(root);stac
7、k.push(2);root = root.getRight();/将节点指向右子树并开始访问指向右子树的左子树break;else if(sign = 2)/当第二次出栈时访问节点System.out.print(root.getValue();root = null;public TreeNode init()/二叉树的初始化TreeNode e = new TreeNode(E);/叶子节点TreeNode f = new TreeNode(F);TreeNode d = new TreeNode(D,e,f);/带有左右子树的节点TreeNode c = new TreeNode(C)
8、;TreeNode b = new TreeNode(B,c,d);TreeNode j = new TreeNode(J);TreeNode h = new TreeNode(H,null,j);/带有右子树的节点TreeNode i = new TreeNode(I);TreeNode g = new TreeNode(G,h,i);TreeNode a = new TreeNode(A,b,g);return a;/建立二叉树的节点类class TreeNodepublic char data;public TreeNode left,right;public TreeNode(char data)this(data,null,null);public TreeNode(char data,TreeNode left,TreeNode right)this.data = data;this.left = left;this.right = right;public TreeNode getLeft()/返回左子树return left;public TreeNode getRight()/返回右子树return right;public char getValue()/访问节点值return data;
