插入节点

我试图写一个函数来插入到二叉搜索树中的节点，我有以下几点：插入节点

typedef struct Node { 
    int key; 
    struct Node *left; 
    struct Node *right; 
} Node; 

Node *createNode(int key) 
{ 
    Node *newNode = (Node *)malloc(sizeof(Node)); 
    newNode->key = key; 
    newNode->left = NULL; 
    newNode->right = NULL; 

    return newNode; 
} 

Node *insert(Node *node, int key) 
{ 
    if (node==NULL) 
    { 
     node = createNode(key); 
    } 
    else 
    { 
     if (node->key > key) 
     { 
      node->left = insert(node->left, key); 
     } 
     else 
     { 
      node->right = insert(node->right, key); 
     } 
    } 
    return node; 
} 

int main(int argc, char* argv[]) 
{ 
    Node *root = NULL; 
    root = insert(root, 10); 

    return 0; 
}

我知道这个工作的，如果我想插入5到根节点root的树，我可以写root = insert(root, 5);。我的问题是，如何编写insert的另一个版本，只需insert(root, 5);即可实现同样的功能？我尝试了以下但无济于事。

void insert(Node *node, int key) 
{ 
    if (node==NULL) 
    { 
     node = createNode(key); 
    } 
    else 
    { 
     if (node->key > key) 
     { 
      insert(node->left, key); 
     } 
     else 
     { 
      insert(node->right, key); 
     } 
    } 
}

这是什么问题，为什么不工作？任何指针（没有双关语意图）将不胜感激！

来源

2015-11-15 Kevin Hsu

简短的回答：没有。有些情况下您需要更改root的值。（例如：树为空时，root为NULL）一种方法是使用返回值的assignmnt（如在您的工作示例中）另一种方式是将指针传递给指针。（一个指向root的指针）。 – wildplasser

原因是，当你在BST中插入一个值时，你必须确保BST *仍然是一个BST，（例如，左边的子节点包含值小于父节点的节点，右边的子节点只包含节点值大于或等于父项）。这意味着您必须检查插入时的几个条件，并且您可能必须移动节点或叶节点（或根节点）以满足BST约束条件。 –

对我来说，你的第一个解决方案是优雅的。

现在，如果你想插入而不利用返回值，那么一种方法可能是使用指向指针的指针。

喜欢的东西：

void insert(Node ** node, int key) 
{ 
    if (*node == NULL) 
     *node = createNode(key); 
    else if ((*node)->key > key) 
     insert(&(*node)->left, key); 
    else 
     insert(&(*node)->right, key); 
}

和通话将

insert(&root, 10);

来源

2015-11-15 02:17:38 lrleon

回答

相关问题