在 C 语言中实现二叉树的'insert'函数

Question

我正在尝试在 C 中为二叉树实现通常的"插入"功能，但我无法弄清楚我的代码哪里出了问题（当然是错误的，因为它不起作用......

有人可以帮助我弄清楚我做错了什么吗？

#include <stdio.h>
#include <stdlib.h>
typedef struct node {
    struct node *left;
    struct node *right;
    int data;
} node;
void insert (node *root, int n);
void print (node *root);
int main(void){
    node *root = malloc(sizeof(node));
    root->left = root->right = NULL; 
    root->data = 50;
    insert (root, 1);
}

void insert (node *root, int n){
    node *cursor = root;
    while (cursor != NULL){
        if (n <= cursor->data){
            cursor = cursor->left;
            printf("leftn");
        }
        else if (cursor->data < n){
            cursor = cursor->right;
            printf("rightn");
        }
        else {
            printf("Invalid data in the tree.n");
            return;
        }
    }
    cursor = malloc(sizeof(node));
    printf("%pn", root->left);
    cursor->data = n;
    cursor->left = NULL;
    cursor->right = NULL;
}
void print (node* root){
    if (root == NULL){
        return;
    }
    print(root->left);
    printf("%i ", root->data);
    print(root->right);
}

Answer 1

您正在分配给cursor，而cursor->left或cursor->right未分配。确保新分配的节点按 cursor->left 或 cursor->right 指向。

void insert (node *root, int n){
    node *cursor = root;
    while (cursor != NULL){
        if (n <= cursor->data){  /* Change 1 follows */
            printf("leftn");
            if(cursor->left == NULL) {
            cursor->left = malloc(sizeof(node));
            cursor = cursor->left;
            break;
           }
        }
        else if (cursor->data < n){
            printf("rightn");
            if(cursor->right == NULL) {  /* Change 2 follows */
              cursor->right = malloc(sizeof(node));
              cursor = cursor->right;
              break;
            }
        }
        else {
            printf("Invalid data in the tree.n");
            return;
        }
    }
    /* Change 3 : 1 line deleted */
    printf("%pn", root->left); /* Why? */
    cursor->data = n;
    cursor->left = NULL;
    cursor->right = NULL;
}

Answer 2

您需要

保留对上一个cursor的引用。您需要找到cursor->data为空的位置;但是如果你想找到cursor本身是空的位置，它对你没有任何作用，因为cursor不是对前一个cursor->data的引用，而是一个副本：当你改变cursor时，你的结构中没有任何变化。

Answer 3

您的代码：

#include <stdio.h>
#include <stdlib.h>
    
typedef struct node {
    struct node *left;
    struct node *right;
    int data;
} node;
    
void insert (node *root, int n);
void print (node *root);
    
int main(void){
    node *root = malloc(sizeof(node));
    root->left = root->right = NULL; 
    root->data = 50;
        
    insert (root, 1);
}
    
void insert (node *root, int n){
    node *cursor = root;
    
    while (cursor != NULL){
        if (n <= cursor->data){
            cursor = cursor->left;
            printf("leftn");
        }else if (cursor->data < n){
            cursor = cursor->right;
            printf("rightn");
        }else {
                printf("Invalid data in the tree.n");
            return;
        }
    }
        
    cursor = malloc(sizeof(node));
    printf("%pn", root->left);
    cursor->data = n;
    cursor->left = NULL;
    cursor->right = NULL;
}
void print (node* root){
        if (root == NULL){
            return;
        }
    
        print(root->left);
        printf("%i ", root->data);
        print(root->right);
}

假设您想在下面的树中添加 1

  5
 / 
2   8

代码具有光标指针。

该光标指针指向 5，然后指向 2，然后指向 NULL。

当它达到 NULL 时，您将分配新内存，并且光标指向该新内存。

就是这样。你还没有做出你想要的。

光标指针不是树的一部分。它只是您用来访问树节点的变量。

现在，节点 *left 和节点 *right 是树的一部分，这些是您必须为其分配内存的节点。

您的问题的一个解决方案是以下代码：

void insert (node **root, int n){
    node *cursor = *root;
    while (cursor != NULL){
        if (n <= cursor->data){
            cursor = *(root=&cursor->left);
            printf("leftn");
        }else if (cursor->data < n){
            cursor = *(root=&cursor->right);
            printf("rightn");
        }else {
            printf("Invalid data in the tree.n");
            return;
        }
    }
   
    *root = malloc(sizeof(node));
    cursor=*root;
    cursor->data = n;
    cursor->left = NULL;
    cursor->right = NULL;
}
int main(void){
    node *root = NULL; 
    
    insert (&root, 1);
}

进一步改进：

void insert (node **root, int n){
    node *cursor = *root;
    while (cursor != NULL) cursor=*(root=(n<cursor->data)?&cursor->left:&cursor->right);
        
    cursor=*root=malloc(sizeof(node));
    cursor->data = n;
    cursor->left = NULL;
    cursor->right = NULL;
}
int main(void){
    node *root = NULL; 
    
    insert (&root, 1);
}