我目前正在检查有关编码算法的信息。如果我们有以下情况:
给定一个具有唯一整数元素的排序(递增顺序)数组,编写了一种算法来创建高度最小的二叉搜索树。
建议使用以下代码作为解决方案:
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
该代码来自一个有信誉的来源,但是我的直觉是实现不正确。
我是否缺少某些东西或实现不正确?
算法-
码
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);
}
}
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句