在 C 处的二叉搜索树中插入新节点

Question

我已经有一个 5 级的二叉搜索树，我正在尝试创建一个插入新节点的函数，但我无法正常工作。如何编辑代码以执行插入？

TREE *insertion(TREE *root, int num){
TREE *node, *new_node;
node = root;
new_node=(TREE *)malloc(sizeof(TREE));
new_node->rec = num;
new_node->lp = NULL;
new_node->rp = NULL;
while(node != NULL ){
//      if(node->rec == num){
//          printf("This value existsn");
//          return NULL;            
//      }
if(num > node->rec){
node = node->rp;    
}
else
node = node->lp;
}
if(num>node->rec)
node = new_node;
else
node = new_node;
return root;}

Answer 1

如果此num > node->rec为真，则需要检查node->rp是否NULL，而您没有检查。

还要将head的地址传递给insertion()，以便传递的变量head中的修改会影响调用函数，并且无需返回任何内容。

假设您正在调用如下所示的insertion()

int main(void) {
TREE *head = NULL;
insertion(&head,10);/* pass the  address of head so that modification will affect here also otherwise just passing head means it will treat as call by value */
insertion(&head,5);
insertion(&head,15);
return 0;
}

insertion()函数看起来像

int  insertion(TREE **root, int num) {
TREE *node, *new_node;
node = *root;
new_node = malloc(sizeof(TREE)); /* no need of casting malloc() results */
new_node->rec = num;
new_node->lp = NULL;
new_node->rp = NULL;
while(node != NULL ){
if(node->rec == num){
printf("This value existsn");
return NULL;`
}
if(num > node->rec){ /* right child of root node */
if(node->rp != NULL) { /* check node->rp is empty or not
if not, update node.. check here itself */
node = node->rp; /* update node */
}
else {
node->rp = new_node; /* insert new node */
return; /* new node added at correct position , so no need of any further processing, jut return */
}
}
else {
if(node->lp != NULL) {
node = node->lp;
}
else {
node->lp = new_node;
return;
}
}
}
}