递归
public void f(Node head){
if(head==null)return;
f(head.left);
f(head.right);
}
//递归实现–无论是哪种递归,每个节点都可以回到自己三次。先序遍历就是i遇到节点的第一次打印
//递归实现--无论是哪种递归,每个节点都可以回到自己三次。先序遍历就是i遇到节点的第一次打印
,中序遍历就是遇到节点的第二次打印....
//先序遍历
public void pre(Node head){
if(head==null)return;
System.out.println(head.value);
pre(head.left);
pre(head.right);
}
//中序遍历
public void in(Node head){
if(head==null)return;
in(head.left);
System.out.println(head.value);
in(head.right);
}
//后序遍历
public void pre(Node head){
if(head==null)return;
pos(head.left);
pos(head.right);
System.out.println(head.value);
}
非递归
//非递归实现
//任何递归都可以改成非递归,压栈实现
//先序遍历:头-左-右
//先头结点放入栈里,1弹出即打印,2有右孩子压右孩子,3如有左孩子压左孩子
public void pre(Node head){
System.out.println("先序遍历");
Stack<Node> stack=new Stack<>();
stack.push(head);
while(!stack.isEmpty()){
Node node=stack.pop();
System.out.println(node.value+" ");
if(head.right!=null)stack.push(head.right);
if(head.left!=null)stack.push(head.left);
}
System.out.println();
}
//后序遍历:左-右-头
//先头结点放入栈里,1弹出即打印,2有左孩子压左孩子,3如有右孩子压右孩子
//此时和先序遍历比较像,只不过是头-右-左,===》倒过来就是后序遍历
//倒过来,只需要弹出的时候不打印,而是将值再存到一个栈里面,最后再打印即可
public void pos(Node head){
Stack<Node> stack1=new Stack<>();//栈1存放树节点
Stack<Node> stack2=new Stack<>();//栈2专门存放弹出时候的值
stack.push(head);
while(!stack.isEmpty()){
Node node=stack.pop();
stack2.push(node.value);
if(head.left!=null)stack1.push(head.left);
if(head.right!=null)stack1.push(head.right);
}
while(!stack2.isEmpty()){
System.out.println(stack2.pop().value+" ");
}
}
//当然也可以用一个栈实现
public void pos2(Node h){
if(h!=null){
Stack<Node> stack=new Stack<>();
stack.push(h);
Node c=null;
while(!stack.isEmpty()){
c=stack.peek();
//没处理过左子树和右子树
if(c.left!=null&&h!=c.left&&h!=c.right){
stack.push(c.left);
//没处理过右子树
}else if(c.right!=null&&h!=c.right){
stack.push(c.right);
//已经处理过两个子树
}else{
System.out.println(stack.pop().value+" ");
//h记录访问过的节点,只有在第一次赋值的时候才有这个意义
h=c;
}
}
}
}
//中序遍历
//1整条左边界依次进栈2.1无法继续弹出节点就打印,然后来到弹出节点的右数继续执行1
public void in(Node head){
Stack<Node> stack=new Stack<Node>();
while(!stack.isEmpty()||head!=null){
if(head!=null){
stack.push(head);
head=head.left;
}else{
Node node=stack.pop();
System.out.println(node.value+" ");
head=node.right;
}
}
}
|