在BST中插入元素 [英] Inserting elements in a BST

问题描述

我正在尝试在BST中插入元素，但未获得正确的结果.除了只打印出所有数组元素，我只打印了 1,11,14 元素，而不是整个数组元素.

I am trying to insert elements in a BST and not getting correct results. Instead of getting all the array elements printed out, I only get 1,11,14 elements printed instead of entire array elements.

int arr[10] = { 11, 2, 4, 23, 1, 98, 88, 65, 33, 14 };
void insertNodeinBST(int data,node **root){

    node *new_n = (node*)malloc(sizeof(node));
    new_n->leftChild = new_n->rightChild = NULL;
    new_n->data = data;
      //check if root is null
    if (*root == NULL) {
        *root = new_n;   
    }
    else if (data < (*root)->data){
        //if data is less than current root's data add it to left child
        insertNodeinBST(data, &(*root)->leftChild);
        (*root)->leftChild = new_n;
    }
    else {
      //if data is more than current root's data add it to right child
        insertNodeinBST(data, &(*root)->rightChild);   
        (*root)->rightChild = new_n;
    }

}

//print BST 
void printInorder(node *root){

        if (root == NULL)
            return;

        /* first recur on left child */
        printInorder(root->leftChild);

        /* then print the data of node */
        printf("%d ", root->data);

        /* now recur on right child */
        printInorder(root->rightChild);

}

int _tmain(int argc, _TCHAR* argv[])
{

    int i = 0;
    node *root = NULL;
    for (i = 0; i < 10; i++){
        //inserting nodes
        insertNodeinBST(arr[i], &root);
    }
    printInorder(root);
    return 0;
}

请让我知道我在这里想念的东西.

Please let me know what I am missing here.

推荐答案

您几乎拥有了它，只是 insertNodeinBST()中的几件事情:

You almost had it, just a couple things in insertNodeinBST():

仅应在 root 为 NULL 的情况下创建新节点，否则，每次访问新节点时都将继续创建新节点，以寻找放置位置.插入:

You should only create the new node when root is NULL, otherwise, you keep creating a new node every time you visit a new node, looking for the place to insert:

//check if root is null
if (*root == NULL) {
    node *new_n = (node*)malloc(sizeof(node));
    new_n->leftChild = new_n->rightChild = NULL;
    new_n->data = data;

    *root = new_n;
}

上面的代码负责插入新节点，因此您不需要其他分配，只需更改:

The code above takes care of inserting the new node, so you don't need the other assigns, change:

} else if (data < (*root)->data) {
    //if data is less than current root's data add it to left child
    insertNodeinBST(data, &(*root)->leftChild);
    (*root)->leftChild = new_n;
} else {
    //if data is more than current root's data add it to right child
    insertNodeinBST(data, &(*root)->rightChild);
    (*root)->rightChild = new_n;
}

到

} else if (data < (*root)->data) {
    //if data is less than current root's data add it to left child
    insertNodeinBST(data, &(*root)->leftChild);
} else {
    //if data is more than current root's data add it to right child
    insertNodeinBST(data, &(*root)->rightChild);
}

当到达正确的空节点时，递归调用会将指针设置为新节点.

the recursive call will set the pointer to the new node when it reaches the correct empty node.

这篇关于在BST中插入元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！