非递归遍历二叉树

在进行二叉树遍历时，使用递归的方式来遍历是很简单的；我们可以采用非递归的方式来实现一下，即用一个栈来保存节点实现遍历(迭代)。

前序遍历

前序遍历顺序是 根-左-右；我们可以每一次都把根节点先处理，再先将右节点压栈，最后将左节点压栈，这样即可实现前序遍历。

        Stack<TreeNode> s = new Stack<TreeNode>();
        s.push(root);
        while(!s.empty())
        {
            TreeNode n = s.pop();
           //此时处理(打印或者存储)
            if(n.right!=null)
                s.push(n.right);
            if(n.left!=null)
                s.push(n.left);
        }

中序遍历

中序遍历顺序是 左-根-右；我们可以先把根节点压栈，然后在一直把左节点压栈，直到左节点无子节点；此时开始出栈，并处理，这时，我们可以判断该节点有无右节点，有的话，再进行压栈处理(和一开始一样)，这样便能实现中序遍历。

       Stack<TreeNode> s= new Stack<TreeNode>();
        do{
            while(root!=null)
            {
                s.push(root);
                root=root.left;
            }
            TreeNode t =  s.pop();
            //此时处理(打印或者存储)
            if(t.right!=null)
                root=t.right;

        }while(!s.empty()||root!=null);

后序遍历

后序遍历顺序是 左-右-根；因为栈的特征是先进后出，我们用两个栈，一个表示原树，另一位用来存储；我们先把根节点入栈，因为我们要先把右边的入栈，在将左边的入栈，所有先处理右边，在处理左边即可。也可以这样理解，前序遍历是 根-左-右，后序遍历倒过来 根-右-左，压栈就类似于倒过来。

        Stack<TreeNode> s = new Stack<TreeNode>();
        Stack<TreeNode> s1= new Stack<TreeNode>();
        s.push(root);
        while(!s.empty())
        {
           TreeNode n=s.pop();
            s1.push(n);
            if(n.left!=null)
                s.push(n.left);
           
            if(n.right!=null)
                s.push(n.right);
        }  
        //最后再进行处理

最后

以上就是自然狗为你收集整理的非递归遍历二叉树的全部内容，希望文章能够帮你解决非递归遍历二叉树所遇到的程序开发问题。

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