二叉搜索树中的插入问题

Question

我写了一个二叉搜索树的插入和遍历的代码。

class node
{
public:
    int data;
    node *left;
    node *right;
};
node* createNode(int value)
{
    node *temp = new node;
    temp->data = value;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}

node *start = NULL;

void insertNode(int val)
{
    if (start == NULL)
    {
        start = createNode(val);
        return;
    }

    node *temp = start;
    while ((temp->left != NULL) && (temp->right != NULL))
    {
        if (val < temp->data)
        {
            temp = temp->left;
        }
        else if (val > temp->data)
        {
            temp = temp->right;
        }
        else
        {
            cout << "Already exists in tree\n";
            return;
        }
    }
    if (val < temp->data)
    {
        temp->left = createNode(val);
        return;
    }
    else
    {
        temp->right = createNode(val);
        return;
    }


}

void inorder(node *root)
{
    if (root != NULL)
    {
        inorder(root->left);
        printf("%d \n", root->data);
        inorder(root->right);
    }
}

它在某些测试用例上无法正常工作。

比如先插入15、25再插入35，再遍历树，只打印15和25。

我无法找出代码中的问题。我的插入逻辑有什么问题？

Answer 1

让我们来看看这个行为 -

你插入 15。if (start == NULL)
- 此检查创建起始节点。现在有一个起始节点，值为15，左右为NULL.

你插入 25。(temp->left != NULL) && (temp->right != NULL)
- 事实证明这是错误的。
- (val < temp->data) 此检查创建一个正确的节点。

你插入35。(temp->left != NULL) && (temp->right != NULL)
- 还是原来是假的
- (val < temp->data) 此检查创建一个右节点（替换当前的右节点）。 这是不对的。

您需要更正此处的 while 循环条件。

二叉搜索树中的插入问题

Problem with insertion in Binary Search Tree

c++

binary-tree

dynamic-programming

binary-search-tree