二叉树的递归遍历、非递归遍历

JAVA 数组生成二叉树

package eight;

import java.util.*;

public class Main {
    private static class Node {
        Node left;
        Node right;
        int data;

        Node(int newData) {
            left = null;
            right = null;
            data = newData;
        }
    }

    public static Node createBinTree(int array[], int num) {
        //根节点为第一个数
        Node root = new Node(array[num]);
        // 左孩子
        if(num * 2 + 1 < array.length){
            root.left = createBinTree(array, num * 2 + 1);
        }

        // 右孩子
        if(num * 2 + 2 < array.length){
            root.right = createBinTree(array, num * 2 + 2);
        }

        return root;
    }

    /*
     * 先序遍历
     * 根左右
     */
    public static void preOrder(Node node) {
        if (node == null)
            return;
        System.out.print(node.data + " ");
        preOrder(node.left);
        preOrder(node.right);
    }

    /*
     * 中序遍历
     * 左根右
     */
    public static void inOrder(Node node) {
        if (node == null)
            return;
        inOrder(node.left);
        System.out.print(node.data + " ");
        inOrder(node.right);
    }

    /*
     * 后序遍历
     * 左右根
     */
    public static void postOrder(Node node) {
        if (node == null)
            return;
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.data + " ");
    }

    /*
     * 层次遍历(广度优先遍历)
     * 将每个节点放入对列中，依据对列先进先出的特点，顺序遍历树。直到队列为空
     */
    public static void levelOrder(Node root){
        Queue<Node> queue = new ArrayDeque<>();
        if(root != null)
            queue.offer(root);
        while(!queue.isEmpty()) {
            Node node = queue.poll();
            System.out.print(node.data + " ");
            if(node.left != null) 
            	queue.add(node.left);
            if(node.right != null) 
            	queue.add(node.right);
        }
    }
    

    /*
     * 前序遍历，非递归,利用栈(相当于深度优先遍历)
     * 1，先入栈根节点，输出根节点val值，再先后入栈其右节点、左结点；
     * 2，出栈左节点，输出其val值，再入栈该左节点的右节点、左节点；直到遍历完该左节点所在子树。
     * 3，再出栈右节点，输出其val值，再入栈该右节点的右节点、左节点；直到遍历完该右节点所在子树。
     * */
    public static void PreOrder2(Node root) {
        Stack<Node> stack = new Stack<Node>();
        if (root != null) {
            stack.push(root);
        }
        while (!stack.empty()) {
            Node node = stack.pop();
            System.out.print(node.data + " ");
            //右结点先入栈，左结点后入栈
            if (node.right != null) 
            	stack.push(node.right);
            if (node.left != null) 
            	stack.push(node.left);
        }
    }
    
    //递归深度遍历，每条路作为一条数据
    static List<String> res1 = new ArrayList<>();
    public List<String> binaryTreePaths(Node root) {
        helper(root,new String());
        return res1;
    }
    public static void helper(Node root,String str) {
        if (root == null) 
            return;
        if (root.left==null && root.right==null) {
            str += root.data;
            res1.add(str);
            return;
        } else {
            helper(root.left, str+root.data+"->");
            helper(root.right, str+root.data+"->");
        }
    }
    
    //每行最大值
    static List<Integer> list = new ArrayList<>();
    public static List<Integer> largestValues(Node root) {
        //List<Integer> list = new ArrayList<>();
        if(root == null)
            return list;
        Queue<Node> queue = new LinkedList<>();
        
        queue.add(root);
        int count = 0;
        int max = Integer.MIN_VALUE;
        Node node = null;
        while(!queue.isEmpty())
        {
            count = queue.size();
            for(int i = 0 ; i < count ; i++)
            {
                node = queue.remove();
                max = Math.max(max,node.data);
                if(node.left!=null)
                    queue.add(node.left);
                if(node.right!=null)
                    queue.add(node.right);
            }
            list.add(max);
            max = Integer.MIN_VALUE;
        }
        return list;
    }
    
    //每行作为一个链表
    static List<List<Integer>> res = new ArrayList<>();
    public static List<List<Integer>> everylevelOrder(Node root) { 
        if(root == null)
            return res;
        
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(root);
        while(!queue.isEmpty()){
            int count = queue.size();
            List<Integer> list = new ArrayList<Integer>();
            for(int i = 0; i < count ; i++){
                Node node = queue.poll();
                list.add(node.data);
                if(node.left != null)
                    queue.add(node.left);
                if(node.right != null)
                    queue.add(node.right);
            }
            res.add(list);
        }
        return res;
    }

    /*
     * 中序遍历，非递归实现
     * 1，首先从根节点出发一路向左，入栈所有的左节点；
     * 2，出栈一个节点，输出该节点val值，查询该节点是否存在右节点，
     *    若存在则从该右节点出发一路向左入栈该右节点所在子树所有的左节点；
     * 3，若不存在右节点，则出栈下一个节点，输出节点val值，同步骤2操作；
     * 4，直到节点为null，且栈为空。
     * */
    public static void inOrder1(Node root) {
        Stack<Node> stack = new Stack<>();
        while (root != null || !stack.empty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            if (!stack.empty()) {
                Node node = stack.pop();
                System.out.print(node.data + " ");
                root = node.right;
            }
        }
    }

    static ArrayList alist = new ArrayList();
    //非递归实现中序遍历(存入数组)
    public static ArrayList inOrder2(Node root){
        Stack<Node> stack = new Stack<Node>();
        Node p = root;
        while(p != null || !stack.empty()){
            while(p != null){
                stack.push(p);
                p = p.left;
            }
            if(!stack.empty()){
                Node temp = stack.pop();
                alist.add(temp.data);
                p = temp.right;
            }
        }
        return alist;
    }

    static ArrayList blist = new ArrayList();
    //非递归实现二叉树的后续遍历
    //使用一个堆栈来存储数据，当一个节点的子节点已经遍历过了或者该节点是叶子节点时，就把该节点添加进列表里
    public static ArrayList postOrder1(Node root){
        Stack<Node> stack = new Stack<Node>();
        if(root == null)
            return blist;
        Node cur,pre = null;
        stack.push(root);
        while(!stack.empty()){
            cur = stack.peek();
            if((cur.left == null && cur.right == null) || (pre != null && (cur.left == pre || cur.right == pre))){
                Node temp = stack.pop();
                blist.add(temp.data);
                pre = temp;
            }
            else{
                if(cur.right != null)
                    stack.push(cur.right);
                if(cur.left != null)
                    stack.push(cur.left);
            }
        }
        return blist;
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s1 = sc.nextLine();
        //输入样例：1,2,3,4,5
        String[] s2 = s1.split(",");//将s1用逗号分隔，放到s2数组中

        int array[] = new int[s2.length];

        for(int i = 0 ; i < s2.length ; i ++) {
            array[i] = Integer.valueOf(s2[i]);
        }

        Node root = null;
        root = createBinTree(array, 0);

        System.out.println("先序遍历1：");
        preOrder(root);
        System.out.println();

        System.out.println("中序遍历1：");
        inOrder(root);
        System.out.println();

        System.out.println("后序遍历1：");
        postOrder(root);
        System.out.println();

        System.out.println("广度优先遍历：");
        levelOrder(root);
        System.out.println();
        
        System.out.println("广度优先遍历，寻找每层最大值：");
        largestValues(root);
        System.out.print(list);
        System.out.println();
        
        System.out.println("广度优先遍历，每行作为一个链表：");
        everylevelOrder(root);
        System.out.print(res);
        System.out.println();

        System.out.println("先序遍历2（深度优先遍历）：");
        PreOrder2(root);
        System.out.println();

        System.out.println("中序遍历2：");
        inOrder1(root);
        System.out.println();

        System.out.println("中序遍历3：");
        inOrder2(root);
        System.out.print(alist);
        System.out.println();

        System.out.println("后序遍历2：");
        postOrder1(root);
        System.out.print(blist);
        System.out.println();
    }
}

其中用到的Stack：

peek( )：查看堆栈顶部的对象，但不从堆栈中移除它。

pop( )：移除堆栈顶部的对象，并作为此函数的值返回该对象。

push(Object element)：把项压入堆栈顶部。