二叉树插入不起作用

Question

我有以下用于将节点插入树中的代码。问题是代码不工作，没有编译错误，但输出不正确。代码如下：

#include <stdio.h>

struct node {
    int data;
    node *left;
    node *right;
};

node * insertNode(node *root, int value) {
    if(root == NULL) {
        printf("%s\n", "root is null, making new node");
        node * new_node = new node;
        new_node->data = value;
        new_node->left = NULL;
        new_node->right = NULL;
        root = new_node;
        printf("%s\n", "root assigned to new node");
    }
    else {
        if(root->data < value) {
            printf("%s\n", "Right subtree");
            insertNode(root->right, value);
        } else {
            printf("%s\n", "Left subtree");
            insertNode(root->left, value);
        }
    }
    return root;
}

void printTree(node *root) {
    if(root != NULL) {
    if(root->left != NULL) {
        printTree(root->left);
    }
    printf("%d ", root->data);
    if(root->right != NULL) {
        printTree(root->right);
    }
    }
    else {
        printf("%s\n", "root is null");
        return;
    }
}

int main()
{
    node *root = new node;
    root->data = 1;
    root->left = NULL;
    root->right = NULL;
    root = insertNode(root, 2);
    printTree(root);
    return 0;
}

我哪里错了？

Answer 1

您忘记为递归函数 insertNode 赋值 return。将 insertNode(root->right, value) 更改为 root->right = insertNode(root->right, value);，将 insertNode(root->left, value) 更改为 root->left = insertNode(root->left, value);。你的函数的第一个参数 insertNode 只是一个输入参数，输出是你的 return 值。像这样调整您的代码：

node * insertNode(node *root, int value) {
    if( root == NULL ) {
        printf("%s\n", "root is null, making new node");
        node * new_node = new node;
        new_node->data  = value;
        new_node->left  = NULL;
        new_node->right = NULL;
        root = new_node;
        printf("%s\n", "root assigned to new node");
    }
    else {
        if( root->data < value ) {
            printf("%s\n", "Right subtree");
            root->right = insertNode( root->right, value );
          //            ^ assigne possibly new right node
        } else {
            printf("%s\n", "Left subtree");
            root->left = insertNode( root->left, value );
          //           ^ assigne possibly new left node
        }
    }
    return root;
}

另一种解决方案是更改函数的签名insertNode并通过指针传递参数：

void insertNode(node **root, int value) {
                 //  ^^ in and output parameter
    if( *root == NULL ) {
        printf("%s\n", "root is null, making new node");
        node * new_node = new node;
        new_node->data  = value;
        new_node->left  = NULL;
        new_node->right = NULL;
        *root = new_node;
        printf("%s\n", "root assigned to new node");
    }
    else {
        if( (*root)->data < value ) {
            printf("%s\n", "Right subtree");
            insertNode( &((*root)->right), value );
        } else {
            printf("%s\n", "Left subtree");
            insertNode( &((*root)->left), value );
        }
    }
}

int main()
{
    node *root  = new node;
    root->data  = 1;
    root->left  = NULL;
    root->right = NULL;
    insertNode( &root, 2 );
             // ^
    printTree(root);
    return 0;
}

请注意，您永远不会删除分配的节点。

二叉树插入不起作用

Binary Tree Insertion Not Working

c++

binary-tree

insertion