c - 二叉树插入节点时原节点发生变化

Question

我正在尝试使用递归插入函数创建二叉树，但我的根节点似乎不断变化(如果没有，printf 应始终在下面的代码中给出相同的输出)。关于如何解决这个问题有什么想法吗？

typedef struct Tnode{

    char name[30];
    int value;

    struct Tnode *left;
    struct Tnode *right;

} Tnode;


Tnode *insert(Tnode *node, char *name, int value){ 

    if(node==NULL){

        Tnode *temp = malloc(sizeof(struct Tnode));

        sprintf(temp->name,"%s",name);
        temp->value = value;

        temp->left = NULL;
        temp->right = NULL;

        return temp;

    }

    else if(strcmp(name,node->name)<0)
    {
        node->left = insert(node->left, name, value);   
    }

    else if(strcmp(name,node->name)>0)
    {
        node->right = insert(node->right, name, value);
    }   
    else{
        printf("something went wrong\n");
    }   

}


int main(){

    Tnode *root = NULL;

    root = insert(root,"george",11);
    root = insert(root,"dick",12);
    printf("%s\n",root->name);  
    root = insert(root,"walter",13);
    root = insert(root,"harry",13);
    printf("%s\n",root->name);  
    root = insert(root,"zink",40);
    printf("%s\n",root->name);  


}

Answer 1

好的，现在我们已经一起解决了。您的 insert() 声明为

Tnode *insert(...)

所以它总是需要返回一个指向 Tnode 的指针，但是在 if 子句中有些情况会导致执行分支不返回任何内容。我猜返回值是未定义的。

由于 insert() 通过传递调用“如果您是叶子，请将值放在这里并返回自己”来递归操作，因此您需要处理这种情况“如果您不是叶子，则执行... 然后返回...”。因此，假设您已经有一棵大树并且插入了一个值，根将调用传递到二进制结构，直到找到正确的位置。最后的调用(递归结束的地方)将返回一个 *Tnode 到该叶子，以便之前的调用可以正确设置 node->left = insert(...);，但仍然有“open”调用堆栈(因为它是递归)需要关闭，即函数终止并且每个节点都向 node->left 或 node->right 写入内容>。如果您不返回任何内容，则可能有一些任意值会破坏您的数据结构并导致未定义的行为。

因此，解决方案只是在末尾添加一个返回节点；，以便可以通过保持根和新叶子之间的“传递”节点不变来完成递归调用。