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 并且总是 return root.

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

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;
}

C 中的迭代二叉搜索树插入

Iterative Binary Search Tree Insert in C

c

iteration

binary-tree

binary-search-tree