引言
我们不记录递归版的二叉树的遍历,我们主要研究非递归版的遍历
我们以这颗树为研究对象
同一规定一下,我们树的数据结构声明如下:
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;
}
}
}
以上就是我们的二叉树的遍历的非递归形式
注意中序遍历的条件
