importjava.util.Stack;publicclassMyTree{publicstaticvoidmain(String[]s){newMyTree();}publicMyTree(){TreeNoderoot=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();}publicvoidpreorder(TreeNoderoot){//递归二叉树的前序遍历if(root!=null){System.out.print(root.getValue());//访问节点值preorder(root.getLeft());preorder(root.getRight());}}publicvoid_preorder(TreeNoderoot){//非递归二叉树的前序遍历Stack<TreeNode>stack=newStack<TreeNode>();//定义堆栈存储while(!(root==null&&stack.isEmpty())){System.out.print(root.getValue());//访问节点if(root!=null){//找到当前节点最深的左子树stack.push(root);//将当前左子树入栈root=root.getLeft();}else{//当左子树到底时，开始访问右节点root=stack.pop();//当前节点出栈root=root.getRight();//指向右子树}}}publicvoidinorder(TreeNoderoot){//递归中序遍历if(root!=null){inorder(root.getLeft());System.out.print(root.getValue());inorder(root.getRight());}}publicvoid_inorder(TreeNoderoot){//非递归中序遍历Stack<TreeNode>stack=newStack<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();}}publicvoidposorder(TreeNoderoot){//递归后序遍历if(root!=null){posorder(root.getLeft());posorder(root.getRight());System.out.print(root.getValue());}}//非递归的后续遍历需要两次访问节点，最后一次访问节点为准privateintsign=0;//得当当前访问节点的次数publicvoid_posorder(TreeNoderoot){Stackstack=newStack();//定义一个可以存放TreeNode和Integer的栈while(!(root==null&&stack.isE