引言

我们不记录递归版的二叉树的遍历,我们主要研究非递归版的遍历

我们以这颗树为研究对象

同一规定一下,我们树的数据结构声明如下:

public static class Node
    {
        public int value;
        public Node left;
        public Node right;
        
        public Node(int data)
        {
            this.value=data;
        }
    }

非递归版本之先序遍历

递归实际上就是通过内存中的栈来保存现场,我们通过创建一个栈来保留现场
我们从栈中弹出一个元素,先把它的右子树压入栈中,然后我们将它的左子树压入栈中(因为要先输出左子树,所有每次把他放在离栈顶更近的位置),然后我们来实现以下

public static void printPre(Node head)
    {
        if(head==null)
        {
            return ;
        }
        Stack<Node> stack=new Stack<>();
        stack.push(head);
        while(!stack.isEmpty())
        {
            Node cur=stack.pop();
            System.out.print(cur.value+" ");
            if(cur.right!=null)
            {
                stack.push(cur.right);
            }
            if(cur.left!=null)
            {
                stack.push(cur.left);
            }
        }
    }

以下是这个代码需要注意的点

• 首先要创建一个栈Stack<>
• 在进入循环之前,我们要先把头放入其中
• 循环的开始,就是弹出栈顶的元素,然后将它们输出,然后把当前元素的右子树放入其中,在放左子树,因为每次要先弹出左子树的值
• 注意循环条件
  为了加深印象,我们在把这个代码重要的点,在记录一下

//创建Stack
//将head放入到Stack中
//循环条件while(栈不为空)
{
    //循环的一个步就是将栈顶元素弹出,然后输出
    //然后就是两个if判断的语句
     if(){} if(){}
}

根据递归的方法我们知道,先序的遍历顺序是 头,左子树,右子树
而后序的遍历顺序是左子树,右子树,头,所有我们可以将后序遍历看做是逆序两次的先序遍历(这样说也不准确),直接看代码吧

    public static void printPost(Node head)
    {
        if(head==null)
        {
            return ;
        }
        Stack<Node> helpStack=new Stack<>();
        Stack<Node> stack=new Stack<>();
        stack.push(head);
        while(!stack.isEmpty())
        {
            Node cur=stack.pop();
            helpStack.push(cur);
            if(cur.left!=null)
            {
                stack.push(cur.left);
            }
            if(cur.right!=null)
            {
                stack.push(cur.right);
            }
        }
        while(!helpStack.isEmpty())
        {
            Node cur=helpStack.pop();
            System.out.print(cur.value+" ");
        }
    }

这是一种讨巧的非递归版的后序遍历,十分容易理解,不过在后面的代码中,我们会介绍另一种遍历方式.

非递归版本之中序遍历

图片.png

如图所示就是中序遍历的思路,现在看起来十分的复杂,我们来一点一点分析它的含义

    public static void inPrintOrder(Node head)
    {
        if(head==null)
        {
            return ;
        }
        Stack<Node> stack=new Stack<>();
        while(!stack.isEmpty()||head!=null)//注意这里的循环条件,这是整个代码中最容易忽略的
        {
            if(head!=null)//head一直都指向当前的结点
            {
                stack.push(head);
                head=head.left;//如果他的左边一直能走,那就一条道走到最后
            }else//当走到死路了(俏皮)
            {
                Node node=stack.pop();//把栈顶的元素弹出
                System.out.print(node.value+" ");//输出
                head=node.right;//然后进入它的右孩子,这时候右孩子有null的风险,
//不过循环的条件依然可以不用跳出
            }
        }
    }

总得来说,就是一条道走到黑,如果走到黑,那就弹出以下,走栈顶元素的有右孩子,就走它的右孩子,然后继续一直向左走
注意循环的条件 while(!stack.isEmpty()||head!=null),两个条件满足其中一个就可以了
然后注意打印的时间,当没有道可以走了,就出栈,然后打印
注意循环条件最重要的

非递归版本之后序遍历

后序遍历比较难以理解,当然你可以通过上面介绍的讨巧的办法做,我们试着来理解一下后序遍历的方法.
我先来说一下大概的思路.就是确定一个h表示的是上一个打印的值.
如果h不是当前结点的左孩子,那么就把当前结点的左孩子入栈,如果h不是当前结点的右孩子,那么把当前结点的右孩子入栈.这样说不是十分理解,我们直接看书吧

图片.png
图片.png
图片.png

实际上就是通过if和else来判断当前结点的左孩子处理过了没有,然后在判断结点的右孩子处理了没有,最后打印,我们来自己实现以下

public static void f(Node h)
{
     Stack<Node> stack=new Stack<>();
     stack.push(h);
     while(!stack.isEmpty())
     {
          c=stack.peek();
          if(c.left!=null&&h!=c.left&&h!=c.right)
          {
               左孩子入栈
          }else if(c.right!=null&&h!=c.right)
          {
                右孩子入栈
          }else
          {
              //打印 
              h=c;
          }
     }
}

以上就是我们的二叉树的遍历的非递归形式
注意中序遍历的条件