package train.demo;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class tree {
    private int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9};
    private static List<Node> nodeList = null;
    private static class Node {
        Node leftChild;
        Node rightChild;
        int data;

        Node(int newData) {
            leftChild = null;
            rightChild = null;
            data = newData;
        }
    }
    // 创建二叉树
    public void createBinTree() {
        nodeList = new LinkedList<>();
        for(int nodeIndex = 0; nodeIndex < array.length; nodeIndex++) {
            nodeList.add(new Node(array[nodeIndex]));
        }
        // 除最后一个父节点，可能只有左孩子，没有右孩子
        for (int parentIndex = 0; parentIndex < array.length / 2 - 1; parentIndex++) {
            // left
            nodeList.get(parentIndex).leftChild = nodeList.get(parentIndex * 2 + 1);
            // right
            nodeList.get(parentIndex).rightChild = nodeList.get(parentIndex * 2 + 2);
        }
        int lastParentIndex = array.length / 2 - 1;
        nodeList.get(lastParentIndex).leftChild = nodeList.get(lastParentIndex * 2 + 1);
        if (array.length % 2 == 1) {
            nodeList.get(lastParentIndex).rightChild = nodeList.get(lastParentIndex * 2 + 2);
        }
    }
    // 先序遍历
    public static void preOrderTraverse(Node node) {
        if (node == null) return;
        System.out.println(node.data + " ");
        preOrderTraverse(node.leftChild);
        preOrderTraverse(node.rightChild);
    }
    // 中序遍历
    public static void inOrderTraverse(Node node) {
        if (node == null)
            return;
        inOrderTraverse(node.leftChild);
        System.out.print(node.data + " ");
        inOrderTraverse(node.rightChild);
    }

    // 后序遍历
    public static void postOrderTraverse(Node node) {
        if (node == null)
            return;
        postOrderTraverse(node.leftChild);
        postOrderTraverse(node.rightChild);
        System.out.print(node.data + " ");
    }
    public static  void  l(Node node) {
    }
    // 层序遍历
    public static void levelOrder(Node node) {
        if (node == null) return;
        Queue<Node> queue = new LinkedList<>();
        List<Integer> ret = new ArrayList<>();

        queue.add(node);
//        Node tmp = queue.poll();
//        System.out.println(tmp.rightChild.data);
        while (!queue.isEmpty()) {
            Node tmp = queue.poll();
            ret.add(tmp.data);

            if (tmp.leftChild != null) queue.add(tmp.leftChild);
            if (tmp.rightChild != null) queue.add(tmp.rightChild);
            System.out.println("queue.size(): " + queue.size());
        }
        int[] res = new int[ret.size()];
//        for (int i=0; i<ret.size(); i++) {
//            res[i] = ret.get(i);
//            System.out.println(res[i]);
//        }
    }

    public static  void main(String args[]) {
        tree t = new tree();
        t.createBinTree();
        // 根节点
        Node root = nodeList.get(0);
        // 先序遍历
//        preOrderTraverse(root);
        l(root);
        levelOrder(root);
    }

}