binary-search-tree - 从排序数组创建二叉搜索树

标签 binary-search-tree

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

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

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

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;

将计算 mid 作为二叉搜索树的根位置编号 2,即值 6。

但是,本示例中的二叉搜索树应如下所示:
    8
   / \
  4   10
 / \    \
2   6   20 

代码来自信誉良好的来源,但我的直觉是实现不正确。

我是否遗漏了什么或实现不正确?

最佳答案

引用 GeeksForGeeks

算法 ——


  • 获取数组的中间并使其成为根。

  • 递归地对左半部和右半部做同样的事情。

  • 获取左半部分的中间部分并使其成为根的左 child
    在步骤 1 中创建。
  • 获取右半部分的中间部分并使其成为
    root 在步骤 1 中创建。



  • Wikipedia Link

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

    关于binary-search-tree - 从排序数组创建二叉搜索树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44860508/

    相关文章:

    java - 将数据存储到数组列表中,然后存储到二叉搜索树中

    C - 使用 argv 命令

    c - 在 C 中为二叉搜索树分配内存的段错误

    java - 递归比较两个二叉搜索树

    c - 我怎样才能加快我的最小二叉树深度函数?

    在 C99 中创建二叉搜索树

    C++:计算 BST 中的重复项

    c - 将数据插入二叉搜索树中的链表

    java - 如何在 2-3 树 java 中找到正确的子节点进行搜索

    java - 将节点插入二叉搜索树