把数组转换成树

题目

按照下面的例子，将一个数组转换成二叉树。

输入  :  arr[] = {1, 2, 3, 4, 5, 6}
输出 : 
                  1
                 / \
                2   3
               / \ /
              4  5 6


输入: arr[] = {1, 2, 3, 4, 5, 6, 6, 6, 6, 6}
输出: 
                   1
                  / \
                 2   3
                / \ / \
               4  5 6  6
              / \ /
             6  6 6

答案

观察元素的排列位置，可以知道要按照层次遍历的方式构造二叉树。

二叉树（英语：Binary tree）是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构，二叉树有如下性质：假设根节点的索引为 0，如果某个节点的索引为 i，则它的左子节点的索引是 2 * i + 1，右子节点的索引是 2 * i + 2。根据这个性质，可以使用递归方法分别将左右两个分支一层一层地进行二叉树的构造，非常方便。

public class ConstructLevelOrderTree {

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        int[] arr = {1, 2, 3, 4, 5, 6, 6, 6, 6};
        tree.root = tree.insertLevelOrder(arr, tree.root, 0);
        tree.printLevelOrder();
    }

}


class Node {
    int data;
    Node left, right;

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

class BinaryTree {

    Node root;

    BinaryTree() {
        root = null;
    }


    void printLevelOrder() {
        int h = height(root);
        int i;
        for (i = 1; i <= h; i++) {
            printGivenLevel(root, i);
        }

    }

    int height(Node root) {
        if (root == null) {
            return 0;
        } else {
            int lheight = height(root.left);
            int rheight = height(root.right);

            if (lheight > rheight) {
                return (lheight + 1);
            } else {
                return (rheight + 1);
            }
        }
    }

    void printGivenLevel(Node root, int level) {
        if (root == null) {
            return;
        }

        if (level == 1) {
            System.out.print(root.data + " ");
        } else if (level > 1) {
            printGivenLevel(root.left, level - 1);
            printGivenLevel(root.right, level - 1);
        }
    }

    Node insertLevelOrder(int[] arr, Node root, int i) {
        if (i < arr.length) {
            Node temp = new Node(arr[i]);
            root = temp;

            root.left = insertLevelOrder(arr, root.left, (2 * i) + 1);

            root.right = insertLevelOrder(arr, root.right, (2 * i) + 2);
        }

        return root;
    }


}