从排序数组创建二叉搜索树 [英] Creating a Binary Search Tree from a sorted array

问题描述

我目前正在检查有关算法编码的问题.如果我们有以下情况:

I am currently checking about coding an algorithms. If we have the following case:

给出具有唯一整数元素的排序(递增顺序)数组，编写了一种算法来创建高度最小的二叉搜索树.

Given a sorted (increasing order) array with unique integer elements, wrote an algorithm to create a binary search tree with minimal height.

建议使用以下代码作为解决方案:

The following code is proposed as the solution:

TreeNode createMinimalBST(int arr[], int start, int end){
    if (end < start) {
        return null;
    }
    int mid = (start + end) / 2;
    TreeNode n = new TreeNode(arr[mid]);
    n.setLeftChild(createMinimalBST(arr, start, mid - 1));
    n.setRightChild(createMinimalBST(arr, mid + 1, end));
    return n;
}

TreeNode createMinimalBST(int array[]) {
    return createMinimalBST(array, 0, array.length - 1);
}

但是，如果我使用以下数组输入尝试此代码:

But if I try this code with the following array input:

[2,4,6,8,10,20]

[2,4,6,8,10,20]

然后执行第一次迭代

createMinimalBST([2,4,6,8,10,20], 0, 5);

以下行:

int mid = (start + end) / 2; // in Java (0 + 5) / 2  =  2;

将以二进制数2为搜索树的根，计算位置编号2(其值为6)作为根.

would calculate the mid as the root of the binary search tree the position number 2 which is the value 6.

但是，此示例中的二进制搜索树应如下所示:

However, the binary search tree in this example should look like:

    8
   / \
  4   10
 / \    \
2   6   20 

代码来自一个有信誉的来源，但是我的直觉是实现不正确.

The code is coming from a reputable source, but my gut feeling is that the implementation is incorrect.

我缺少什么还是实现不正确吗?

Am I missing something or the implementation is not right ?

推荐答案

参考 GeeksForGeeks

算法-

1. 获取数组的中间并将其设为根.
2. 递归地对左半部分和右半部分执行相同的操作.
   • 获取左半部分的中间部分，使其成为根的子代 在步骤1中创建.
   • 获取右半部分的中间部分，使其成为正确的子代 在步骤1中创建的根目录.

1. Get the Middle of the array and make it root.
2. Recursively do same for left half and right half.
   • Get the middle of left half and make it left child of the root created in step 1.
   • Get the middle of right half and make it right child of the root created in step 1.

维基百科链接

代码

 class Node {

    int data;
    Node left, right;

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

class BinaryTree {

    static Node root;

    /* A function that constructs Balanced Binary Search Tree 
    from a sorted array */
    Node sortedArrayToBST(int arr[], int start, int end) {

        /* Base Case */
        if (start > end) {
            return null;
        }

        /* Get the middle element and make it root */
        int mid = (start + end) / 2;
        Node node = new Node(arr[mid]);

        /* Recursively construct the left subtree and make it
        left child of root */
        node.left = sortedArrayToBST(arr, start, mid - 1);

        /* Recursively construct the right subtree and make it
        right child of root */
        node.right = sortedArrayToBST(arr, mid + 1, end);

        return node;
    }

    /* A utility function to print preorder traversal of BST */
    void preOrder(Node node) {
        if (node == null) {
            return;
        }
        System.out.print(node.data + " ");
        preOrder(node.left);
        preOrder(node.right);
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        int arr[] = new int[]{2, 4, 6, 8, 10, 12};
        int n = arr.length;
        root = tree.sortedArrayToBST(arr, 0, n - 1);
        System.out.println("Preorder traversal of constructed BST");
        tree.preOrder(root);
    }
}

这篇关于从排序数组创建二叉搜索树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！