从排序后的数组中创建二进制搜索树

问题描述 投票:4回答:3

我目前正在检查有关编码算法的信息。如果我们有以下情况:

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

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

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);
}

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

[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(即值6)作为二分查找树的根,将其计算出来。

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

    8
   / \
  4   10
 / \    \
2   6   20 

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

我是否缺少某些内容或实现不正确?

binary-search-tree
3个回答
6
投票

参考GeeksForGeeks

算法-

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

Wikipedia Link

CODE

 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);
    }
}

1
投票

经过排序的数组将为您提供平衡的二叉树。这可以在O(n)时间轻松完成,因为我们可以在O(1)时间获得中间元素。以下是一个简单的算法,

  1. 为数组中的中间元素构造一个节点并返回它(这将是基本情况的根)。

    1. 从数组左半部分的1开始重复,将返回值分配给根的左子级。

    2. 从数组右半边的1开始重复,将返回值分配给根的右子级。

Java实现

 TreeNode sortedArrayToBST(int arr[], int start, int end) {  
           if (start > end)
              return null; // same as (start+end)/2, avoids overflow.    
           int mid = start + (end - start) / 2;      
           TreeNode node = new
           TreeNode(arr[mid]); 
           node.left = sortedArrayToBST(arr, start, mid-1); 
           node.right = sortedArrayToBST(arr, mid+1, end); 
            return node; 
    }

TreeNode sortedArrayToBST(int arr []){返回sortedArrayToBST(arr,0,arr.length-1); }

时间复杂度: ** O(n) **以下是sortedArrayToBST()的重复关系。

T(n)= 2T(n / 2)+ C

T(n)->大小为n的数组所需的时间

C->常量(查找数组的中间并将根链接到左侧和右侧子树需要固定的时间)


0
投票

将排序后的数组转换为二进制搜索树(BST)的迭代JavaScript实现:

function sortedArrayToBstIteratively(nums) {
    // use stack iteratively split nums into node tuples and save values
    const stack = []

    // add root node to tree
    const tree = {first: 0, last: nums.length-1}
    stack.push(tree)

    // iteratively split array in the middle and continue with the two halfs
    while(stack.length > 0) {
        let node = stack.pop()

        if (node.last >= node.first) {
            if (node.last === node.first) {
                // node reaches a single leaf value (last == first)
                node.value = nums[node.first]
            } else {
                // node has still valid indices to further split the array (last > first)
                const middle = Math.ceil((node.first + node.last) / 2)
                node.value = nums[middle]
                node.left = {first: node.first, last: middle - 1}
                node.right = {first: middle + 1, last: node.last}
                stack.push(node.left)
                stack.push(node.right)
            }
        } else {
            // node has no more valid indices (last < first), create empty leaf
            node.value = null
        }

        delete node.first
        delete node.last
    }

    // console.log(JSON.stringify(tree))

    return tree
}
© www.soinside.com 2019 - 2024. All rights reserved.