package 实际问题; import java.util.Stack; public class MyTree{ public 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("递归后续遍历"); posorder(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.out.print(root.getValue());//访问节点值 preorder(root.getLeft()); preorder(root.getRight()); } } public void _preorder(TreeNode root){ //非递归二叉树的前序遍历 Stack<TreeNode> stack = new Stack<TreeNode>();//定义堆栈存储 while(!(root == null && stack.isEmpty())){ while (root != null) { System.out.print(root.getValue()); stack.push(root); root = root.getLeft(); } if (!stack.isEmpty()) { root = stack.pop(); 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<TreeNode> stack = new Stack<TreeNode>(); while(!(root == null && stack.isEmpty())){ while(root != null){//先找到最深的左子树 stack.push(root); root = root.getLeft(); } //找到最深左子树后开始访问 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 _posorder(TreeNode root){ Stack stack = new Stack();//定义一个可以存放TreeNode 和 Integer的栈 while(!(root == null && stack.isEmpty())){ if(root != null){//找最深左子树 stack.push(root);//将当前节点压入堆栈 stack.push(1);//并标记当前访问节点的次数 root = root.getLeft(); }else{//找到最深左子树后 while(!stack.isEmpty()){ sign = (Integer)stack.pop();//出栈标记 root = (TreeNode)stack.pop();//出栈节点 if(sign == 1){//地一次访问节点 stack.push(root); stack.push(2); root = root.getRight();//将节点指向右子树并开始访问指向右子树的左子树 break; }else if(sign == 2){//当第二次出栈时访问节点 System.out.print(root.getValue()); root = null; } } } } } public TreeNode init(){//二叉树的初始化 TreeNode d = new TreeNode('4'); TreeNode e = new TreeNode('5'); TreeNode f = new TreeNode('6'); TreeNode g = new TreeNode('7'); TreeNode b = new TreeNode('2',d,e); TreeNode c = new TreeNode('3',f,g); TreeNode a = new TreeNode('1',b,c); return a; } } //建立二叉树的节点类 class TreeNode{ public 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; } }