二叉树的三种遍历（非递归写法）中序遍历二叉树先序遍历二叉树后序遍历二叉树

中序遍历二叉树

访问顺序：
针对每一棵子树：先访问左孩子，再访问根节点，最后访问后孩子

非递归的算法思想：
从根节点开始，首先沿着左子树向下移动，同时入栈保存；当到达空子树后需要退栈访问节点，然后移动到右子树上去。

代码实现（JAVA版）

public void Mid(TreeNode root ) {
		Stack<TreeNode> stack = new Stack<>();
        List<TreeNode> list = new LinkedList<>();
        while(root != null || !stack.isEmpty()){
        	//一直向左边走，走到最左边的节点
            if(root != null){
                stack.push(root);
                root = root.left; 
            }else{    //到达最左边
                root = stack.pop();    //弹出最左边的节点
                list.add(root);           //访问最左边的节点
                root = root.right;       //向右节点走
            }
        }
  }

先序遍历二叉树

访问顺序：
针对每一棵子树：先访问根节点，再访问左孩子，最后访问后孩子

非递归的算法思想：
从根节点开始，首先沿着左子树向下移动，同时入栈保存；当到达空子树后需要退栈访问节点，然后移动到右子树上去。将访问节点的位置放在第一次指向该结点时

代码实现（JAVA版）

public void left(TreeNode root) {
		Stack<TreeNode> stack = new Stack<>();
        List<TreeNode> list = new LinkedList<>();
        while(root != null || !stack.isEmpty()){
        	//一直向左边走，走到最左边的节点
            if(root != null){
           		list.add(root);           //访问节点
                stack.push(root);
                root = root.left; 
            }else{    //到达最左边
                root = stack.pop();    //弹出最左边的节点
                root = root.right;       //向右节点走
            }
        }
  }

后序遍历二叉树

访问顺序：
针对每一棵子树：先访问左孩子，再访问右孩子，最后访问根节点

非递归的算法思想：
从根节点开始，首先沿着左子树向下移动，同时入栈保存；当到达空子树后需要退栈访问节点，然后移动到右子树上去。将访问节点的位置放在第三次指向该结点时

代码实现（JAVA版）

public void right(TreeNode root) {
		Stack<TreeNode> stack = new Stack<>();
        List<TreeNode> list = new LinkedList<>();  
        Stack<Integer> tag = new Stack<>();
        int num;
        while(root != null || !stack.isEmpty()){
        	//一直向左边走，走到最左边的节点
            if(root != null){
           	    stack.push(root);
           	    tag.push(1);
                root = root.left; 
            }else{    //向右边走
                root = stack.pop();   
                num = tag.pop();
                if(num == 1){
                	//从左子树返回，需要再入栈，转向右子树
                	stack.push(root);
                	tag.push(2);
                	root = root.right;
                }else{
                	//从右子树返回，访问节点
                	list.add(root);
                	root = null;
                }
            }
        }
  }

最后

以上就是甜蜜芒果为你收集整理的二叉树的三种遍历（非递归写法）中序遍历二叉树先序遍历二叉树后序遍历二叉树的全部内容，希望文章能够帮你解决二叉树的三种遍历（非递归写法）中序遍历二叉树先序遍历二叉树后序遍历二叉树所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。