非递归遍历二叉树(数据结构)

freedom　⁠

已于 2024-11-25 22:31:34 修改

阅读量1.6k

点赞数 78

分类专栏： # 数据结构oj 文章标签：数据结构

于 2024-11-25 22:31:16 首次发布

本文链接：https://blog.csdn.net/weixin_60489641/article/details/143985641

版权

数据结构oj 专栏收录该内容

5 篇文章

订阅专栏

我的博客主页

非递归遍历二叉树

前序遍历（迭代）
中序遍历（迭代）
后续遍历（迭代）

二叉树的遍历方式有：前序遍历、中序遍历、后续遍历，层序遍历，而树的大部分情况下都是通过递归的方式来进行的。
首先要明白递归是函数自身调用自身，设计了很多因素记录树中遍历的入栈记录地址等。。。因为是在栈上开辟空间，这些操作对于时间和空间的消耗会更大，且容易溢出。迭代（非递归）它是在栈堆中开辟更大的空间，不容易溢出，且不会调用函数自身，效率也会提升很多。

更多的二叉树的oj题目在我的专栏中，感谢大家的观看

在数据结构中的学习难免少不了递归的学习，递归有时候也会让代码变得更加简洁，学习递归让我们对代码有更近一步的思考。

前序遍历（迭代）

每遍历一个节点打印一次元素且将其放入栈中，直到为空时，将栈顶元素移除来并打印并让其查看另一子树是否为空节点。

   public static void preOrderIteration(TreeNode root){
        if(root==null)return ;//根节点没有属性
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                System.out.print(cur.val+" ");
                cur=cur.left;
            }
            cur=stack.pop();//将从栈中弹出的元素给到cur
            cur=cur.right;//cur的右边赋值给cur是否为空
        }
    }

中序遍历（迭代）

因为中序遍历是左根右，给定一个辅助栈，每次走到最后一个节点的left或者right为空时将栈中的元素给到数组，然后再去遍历栈顶右边元素是否为空。

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list=new LinkedList<>();
        Stack<TreeNode> stack=new Stack<>();
        while(root!=null||!stack.isEmpty()){
            if(root!=null){
                stack.push(root);
                root=root.left;
            }else{
                //如果为null说明该节点的左子树为空，将栈顶元素放入数组中
                list.add(stack.peek().val);
                //检查栈顶的右节点
                root = stack.pop().right;
            }
        }
        return list;
    }

后续遍历（迭代）

在这里插入图片描述

   public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list=new LinkedList<>();
        if(root==null)return list;
        Stack<TreeNode> stack=new Stack<>();
         TreeNode prev=null;//记录上一个移除栈的元素
        while(root!=null||!stack.isEmpty()){
            while(root!=null){
            stack.push(root);
            root=root.left;
        }
            TreeNode top = stack.peek();//查看顶部元素右树是否为空
            //两个条件，右树为null或者此元素右树已经出过栈则直接出栈
            if(top.right==null||prev==top.right){
             TreeNode cur = stack.pop();
                 list.add(cur.val);
                prev=top;//记录上一个栈顶元素
            }else{
                root=top.right;
            }
        }
        return list;
    }