算法练习第四天（二叉树相关）

https://blog.csdn.net/qq_37186947/article/details/90681403

package com.baidu.insurprod.biz.util;

import java.util.LinkedList;
import java.util.Stack;

/**
 * @author meizhenhao
 * @Date 2020/11/9 下午4:52
 */
public class TwoTree {

    public static void main(String[] args) {
        int[] arr = {3, 1, 4, 2, 5};
        Node root = buildTwoChaTree(arr);
        System.out.print("递归实现先序遍历  ：");
        preForEach(root);
        System.out.println();

        System.out.print("非递归实现先序遍历：");
        preForEachNO(root);
        System.out.println();

        System.out.print("递归实现中序遍历  ：");
        inForEach(root);
        System.out.println();

        System.out.print("非递归实现中序遍历：");
        inForEachNO(root);
        System.out.println();

        System.out.print("递归实现后序遍历  ：");
        lastForEach(root);
        System.out.println();

        System.out.print("非递归实现后序遍历：");
        lastForEachNO(root);
        System.out.println();

        System.out.print("实现层序遍历     ：");
        levelForEach(root);
        System.out.println();
    }

    private static void levelForEach(Node root) {
        if (root == null) {
            return;
        }
        // 使用队列
        LinkedList<Node> queue = new LinkedList<>();
        queue.addLast(root);
        // 当前层节点数、下一层节点数
        int high = 0, curLevelNum = 1, nextLevelNum = 0;
        while (!queue.isEmpty()) {
            Node temp = queue.removeFirst();
            System.out.print(temp.value + "     ");
            curLevelNum--;

            if (temp.left != null) {
                queue.addLast(temp.left);
                nextLevelNum++;
            }

            if (temp.right != null) {
                queue.addLast(temp.right);
                nextLevelNum--;
            }

            if (curLevelNum == 0) {
                high++;
                curLevelNum = nextLevelNum;
                nextLevelNum = 0;
            }
        }
    }

    // 先序遍历，非递归
    private static void preForEachNO(Node root) {
        if (root == null) {
            return;
        }

        Stack<Node> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            // 先处理  根和左，全部入栈
            while (root != null) {
                stack.push(root);
                System.out.print(root.value + "      ");
                root = root.left;
            }

            // 在处理  右
            if (!stack.isEmpty()) {
                root = stack.pop().right;
            }
        }
    }

    // 先序遍历，递归
    public static void preForEach(Node root) {
        if (root == null) {
            return;
        }
        System.out.print(root.value + "     ");
        preForEach(root.left);
        preForEach(root.right);
    }

    // 中序遍历，非递归
    private static void inForEachNO(Node root) {
        if (root == null) {
            return;
        }

        Stack<Node> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            // 先处理 左根
            while (root != null) {
                stack.push(root);
                root = root.left;
            }

            if (!stack.isEmpty()) {
                root = stack.pop();
                System.out.print(root.value + "       ");
                root = root.right;
            }
        }
    }

    // 中序遍历，递归
    public static void inForEach(Node root) {
        if (root == null) {
            return;
        }
        inForEach(root.left);
        System.out.print(root.value + "     ");
        inForEach(root.right);
    }

    // 后序遍历，非递归
    private static void lastForEachNO(Node root) {
        if (root == null) {
            return;
        }
        Stack<Node> inStack = new Stack<>();
        Stack<Node> outStack = new Stack<>();
        inStack.push(root);

        while (!inStack.isEmpty()) {
            Node temp = inStack.pop();
            outStack.push(temp);

            if (temp.left != null) {
                inStack.push(temp.left);
            }

            if (temp.right != null) {
                inStack.push(temp.right);
            }
        }

        while (!outStack.isEmpty()) {
            System.out.print(outStack.pop().value + "       ");
        }

    }

    // 后序遍历，递归
    public static void lastForEach(Node root) {
        if (root == null) {
            return;
        }
        lastForEach(root.left);
        lastForEach(root.right);
        System.out.print(root.value + "     ");
    }

    // 创建一个二叉排序树
    public static Node buildTwoChaTree(int[] arr) {

        if (arr == null || arr.length <= 0) {
            return null;
        }

        Node root = new Node(arr[0]);
        for (int i = 1; i < arr.length; i++) {
            if (i <= arr.length - 1) {
                insertTwoChaTree(root, arr[i]);
            }
        }
        return root;
    }

    private static void insertTwoChaTree(Node root, int value) {
        if (value > root.value) {
            if (root.right == null) {
                root.right = new Node(value);
                return;
            }
            insertTwoChaTree(root.right, value);
        } else if (value < root.value) {
            if (root.left == null) {
                root.left = new Node(value);
                return;
            }
            insertTwoChaTree(root.left, value);
        }
    }
}

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