BST 递归插入 - 将新节点指针分配为叶子的子节点

Question

我正在尝试为二叉树实现插入方法，这是我得到的：

struct node * addNode(struct node ** root, struct node * node){
    //base case: when reach leaf
    if (*root == NULL){
        printf("reached with root with node key = %i", node->key);
        return node;
    }
    if ((node -> key) > ((*root)->key)){ //add to the right subtree
        printf("node key is : %i, tree's node key is: %i\n", (node -> key), ((*root)->key));
        (*root)->right = addNode(&((*root)->right), node);
    } else {
        printf("node key is : %i, tree's node key is: %i\n", (node -> key), ((*root)->key));
        (*root)->left = addNode(&((*root)->left), node);
    }
    return node;
}

在这种情况下，将叶子的子节点设置为 *node 的指针不起作用，但我不确定为什么。写了一个驱动程序来测试这个方法，我得到了分段错误。

Answer 1

更新*root后return是错误的node不是NULL.

您应该 return *root 而不是以错误的方式修改树。

Answer 2

如果函数是用 return 类型结构 node * 编写的，那么这意味着函数必须 return 指向根节点的指针。但是，如果树不为空（即当指向根节点的指针不等于 NULL 时），则函数 return 将指针 node.

struct node * addNode(struct node ** root, struct node * node){
    //...
    return node;
}

在这种情况下调用函数后

root = addNode( &root, node );

指向根节点的指针将始终等于node的值。

同样在这种情况下，将第一个参数声明为结构类型 node **.

是没有意义的

函数可以这样写

struct node * addNode( struct node *root, struct node * node )
{
    //base case: when reach leaf
    if ( root == NULL )
    {
        return node;
    }
    else if ( node -> key > root->key )
    {
        root->right = addNode( root->right, node );
        return root;
    } 
    else 
    {
        root->left = addNode( root->left, node );
        return root;
    }
}

并称赞

root = addNode( root, node );

BST 递归插入 - 将新节点指针分配为叶子的子节点

BST recursive insert - assign new node pointer as leaf's child

c

recursion

binary-tree

function-definition