c - 在 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("left\n");
        }

        else if (cursor->data < n){
            cursor = cursor->right;
            printf("right\n");
        }

        else {
            printf("Invalid data in the tree.\n");
            return;
        }
    }

    cursor = malloc(sizeof(node));
    printf("%p\n", 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("left\n");
            if(cursor->left == NULL) {
            cursor->left = malloc(sizeof(node));
            cursor = cursor->left;
            break;
           }
        }

        else if (cursor->data < n){
            printf("right\n");
            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("%p\n", root->left); /* Why? */
    cursor->data = n;
    cursor->left = NULL;
    cursor->right = NULL;

}