迭代二叉搜索树插入 C 语言

Question

这似乎是一个简单的问题，我看了另一个线程，似乎我在做同样的事情，但没有结果。

这是我迭代插入二叉搜索树的代码，以及结构和如何创建新节点：

typedef struct node {
    int data;
    struct node *left;
    struct node *right;
} node;
node *create_node(int data) {
    node *n = calloc(1, sizeof(node));
    n->data = data;
    return n;
}
node *BST_insert_iterative(node *root, int data) {
    node *temp = root;
    if (root == NULL)
        return create_node(data);
    while (temp != NULL) {
        if (data > temp->data)
            temp = temp->right;
        else
            temp = temp->left;
    }
    temp = create_node(data);
    return root;
}

当我打印树时，我只收到第一个节点：

Inserting 8  into BST...
Inserting 50     into BST...
Inserting 74     into BST...
Inserting 59     into BST...
Inserting 31     into BST...
Inserting 73     into BST...
Inserting 45     into BST...
Inserting 79     into BST...
Inserting 24     into BST...
Inserting 10     into BST...
In order traversal
8
Height of tree: 0

但是，使用递归插入函数：

node *BST_insert(node *root, int data) {
    if (root == NULL)
        return create_node(data);
    if (root->data >= data)
        root->left = BST_insert(root->left, data);
    else (root->data < data)
        root->right = BST_insert(root->right, data);
    return root;
}

它工作得很好，我得到：

Inserting 8  into BST...
Inserting 50     into BST...
Inserting 74     into BST...
Inserting 59     into BST...
Inserting 31     into BST...
Inserting 73     into BST...
Inserting 45     into BST...
Inserting 79     into BST...
Inserting 24     into BST...
Inserting 10     into BST...
In order traversal
8
10
24
31
45
50
59
73
74
79
Height of tree: 4 

Answer 1

在插入函数中，不会将新节点存储到树中。您只需存储到局部变量temp并始终返回root 。

必须保留指向要更新的链接的指针，以便将新节点插入到树中或插入树的根目录中。这是一个修改版本：

typedef struct node {
    int data;
    struct node *left;
    struct node *right;
} node;
node *create_node(int data) {
    node *n = calloc(1, sizeof(node));
    n->data = data;
    n->left = n->right = NULL;
    return n;
}
node *BST_insert_iterative(node *root, int data) {
    node **pp = &root;
    while (*pp != NULL) {
        if (data > (*pp)->data)
            pp = &(*pp)->right;
        else
            pp = &(*pp)->left;
    }
    *pp = create_node(data);
    return root;
}

笔记：

• 空树没有特殊情况。
• 请注意，这种方法不足以保持树的平衡。

另请注意，递归函数在看起来像冗余测试的情况下存在语法错误。您应该以这种方式简化它：

node *BST_insert(node *root, int data) {
    if (root == NULL)
        return create_node(data);
    if (root->data >= data) {
        root->left = BST_insert(root->left, data);
    } else {
        root->right = BST_insert(root->right, data);
    }
    return root;
}

Answer 2

Chqrlie 的答案有效，但我想在不使用双指针的情况下做到这一点。

在意识到我的根没有连接到新创建的节点后，我能够做到这一点。

这是该解决方案：

node *BST_insert_iterative(node *root, int data)
{
    node *temp = root;
    int condition = 1;
    if (root == NULL)
        return create_node(data);
    while (condition)
    {
        if (data > temp->data)
        {
            if (temp->right == NULL)
            {
                temp->right = create_node(data);
                condition = 0;
            }
            else
                temp = temp->right;
        }
        else
        {
            if (temp->left == NULL)
            {
                temp->left = create_node(data);
                condition = 0;
            }
            else
                temp = temp->left;
        }
    }
    return root;
}