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/

    相关文章:

    serialization - : hash table or BST in terms of serialization, 并发哪个更合适?

    c# - 插入函数不插入

    java - 我怎样才能让我的 BST add 方法在前两个子节点之后添加节点?

    Java 二叉搜索树在运行时不打印

    java - 二叉搜索树 - Java

    java - 随机化文本文件以避免树不平衡

    java - 顺序遍历错误?

    algorithm - 如何使用 {pre,in,post}order 遍历结果重建 BST

    algorithm - 使用广度优先搜索和中序遍历来分析一个非常大的二叉搜索树的有效性

    java - 关于递归存储的二叉搜索树问题