二叉树的递归与迭代实现(java)

递归实现，

前序：根左右

中序：左根右

后续：左右根

首先我们需要了解什么是二叉树的前序遍历：按照访问根节点——左子树——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候，我们按照同样的方式遍历，直到遍历完整棵树。因此整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。

中序和后序同理：

package 二叉树;

public class 递归 {
    public class Node{
        public int value;
        public Node Left;
        public Node Right;

        public Node(int data){
            this.value = data;
        }
    }
    public void preOrderRecur(Node head){
        if(head == null){
            return;
        }
        System.out.println(head.value+" ");
        preOrderRecur(head.Left);
        preOrderRecur(head.Right);
    }
    public void inOrederRecur(Node head){
        if(head == null){
            return;
        }
        inOrederRecur(head.Left);
        System.out.println(head.value+" ");

        inOrederRecur(head.Right);
    }
    public void posOrederRecur(Node head){
        if(head == null){
            return;
        }
        posOrederRecur(head.Left);
        posOrederRecur(head.Right);
        System.out.println(head.value+" ");
    }
    
}

迭代实现，

用自己的数据结构来代替函数栈的递归，凡是可以用递归的都能用迭代写出来

package 二叉树;

import java.util.Stack;

public class 非递归 {
    public class Node{
        public int value;
        public Node Left;
        public Node Right;

        public Node(int data){
            this.value = data;
        }
    }
    //用自己的数据结构来模拟代替函数栈
    public void preOrderUnRecur(Node head){
        System.out.println("pre-order: ");
        if(head != null){
            Stack< Node> stack = new Stack<Node>();
            stack.add(head);//插入根
            while(!stack.empty()){
                head = stack.pop();//弹出根
                System.out.println(head.value+" ");
                if(head.Right != null){
                    stack.push(head.Right);//栈的先进后出，最后左边会先打印
                }
                if(head.Left != null){
                    stack.push(head.Left);
                }
            }
        }
        System.out.println();
    }

    //中 zuo,根，you
    public void inOrderUnRecur(Node head){
        System.out.println("in-order: ");
        if(head != null){
            Stack<Node> stack = new Stack<Node>();
            while(!stack.empty() || head != null){
                if(head!=null){
                    stack.push(head);
                    head = head.Left; //一直放左，直到碰到根      左根右
                }else{
                    head = stack.pop();
                    System.out.println(head.value+" ");
                    head = head.Right;
                }
            }
        }
        System.out.println();
    }

    //后 zuo,you,根
    public void posOrderUnRecur(Node head){
        System.out.println("pos-order: ");
        if(head != null){
            Stack<Node> s1 = new Stack<Node>();//俩个栈实现
            Stack<Node> s2 = new Stack<Node>();
            s1.push(head);
            while(!s1.isEmpty()){
                head = s1.pop();
                s2.push(head);
                if(head.Left != null){
                    s1.push(head.Left);
                }
                if(head.Right != null){
                    s1.push(head.Right);
                }
            }
            while(!s2.isEmpty()){
                System.out.println(s2.pop()+" ");
            }
        }
    }

}