How binary search tree is created?

问题:

Suppose i am having an array say

1 5 4 6 8 9 10 22 17 7 9 3

I want to create a binary search tree from this array. I need algorithm to understand that.

I have read rest other things related to BST like inorder traversal preorder postorder, tree walk, insertion deletion etc

Book has not provided how to create BST. Need help here

回答1:

if you do not care about the tree being balanced it is simple:

1. put the first element of the tree as the head.
2. iterate over the array. if an element is bigger than the node take a left(repeat the step for the left child) otherwise take a right(repeat the step for the right child).
3. if the left/right child is a null insert your new value there.

guaranteed to produce a binary search tree - just not a balanced one.

回答2:

Firstly, you should choose a root node for your BST. Once you have chosen a root node, it is already easy to construct a BST taking into consideration the fact that: left children are less than the parent node and all right children are greater than the parent node.

private Node root;

public void insert(int val) {
    if (root == null) {
        root = new Node(val);
    } else {
        insertHelper(root, val);
    }
}

private void insertHelper(Node node, int val) {
    if (val < node.val) {
        if (node.left == null) {
            node.left = new Node(val);
        } else {
            insertHelper(node.left, val);
        }
    } else if (node.val < val) {
        if (node.right == null) {
            node.right = new Node(val);
        } else {
            insertHelper(node.right, val);
        }
    }
}

回答3:

If the given array is sorted, you can do the following:

1. Take the middle element of the array and make it the root of the tree
2. Take the left sub-array and make it the left sub-tree of the root recursively
3. Take the right sub-array and make it the right sub-tree of the root recursively

Otherwise you can always sort the array before applying the procedure

struct node* construct(int arr[], int start, int end)
{
    if(start>end)
       return;
    else if (start==end)
    {
    /*assuming we have a function newNode(int) which creates a new BST Node*/
        node* Node = newNode(arr[start]);
        return Node;
    }
    int mid  = (start+end)/2;
    node* root = newNode(arr[mid]);
    root->left = construct(arr,start,mid-1);
    root->right = construct(arr,mid+1,end);
    return root;
}