C语言循环实现BST：两段代码一正常一异常问题排查

我用C语言结合循环实现基于链表的二叉搜索树（BST），遇到一个问题：两段逻辑相似的代码，一段能正常运行，调用printBST()可打印所有节点；另一段却仅能打印根节点，无法正确插入其余节点。已经用GDB调试过，但没找到问题，求帮忙排查。

正常工作的代码 #

#include<stdio.h>
#include<stdlib.h>

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


typedef struct BST {
  Node* root;
}BST;



Node * createNode(int value) {
  Node * a= (Node* )malloc(sizeof(Node));
  a->left = NULL;
  a->right = NULL;
  a->data = value; 
  return a; 
}
void printBST(Node * bst) {
  if(bst == NULL) {return; } 
  printf("%d ", bst->data);
  printBST(bst->left);
  printBST(bst->right); 
}


Node* createRandomBST(size_t len){
  if(len == 0) {return NULL;}

  Node* tempBST = createNode(rand()%200);

  printf("   root: %d \n",  tempBST->data);

  Node* ptr_1;
  Node  *ptr_2;
  ptr_1 = tempBST;
  ptr_2 = tempBST;


  for(int  i = 0; i < len; i++) {
    int value = i*i+22;
    tempBST = ptr_1;
    while (1)
    {
      
      if(value >= tempBST->data) {
        
        if(tempBST->right == NULL) {
          tempBST->right = createNode(value);
          printf("right-I: %d, value:%d \n", i, tempBST->data);
          break;
        }
        tempBST = tempBST ->right;

      }else {
         
        if(tempBST->left == NULL) {
          tempBST->left = createNode(value);
          printf("left-I: %d, value:%d \n", i, value);
          break;
        }   
        tempBST= tempBST->left;    
      }
    }
      
    
  }
return ptr_2;
}

未正常工作的代码 #

#include<stdio.h>
#include<stdlib.h>

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


typedef struct BST {
  Node* root;
}BST;



Node * createNode(int value) {
  Node * a= (Node* )malloc(sizeof(Node));
  a->left = NULL;
  a->right = NULL;
  a->data = value; 
  return a; 
}
void printBST(Node * bst) {
  if(bst == NULL) {return; } 
  printf("%d ", bst->data);
  printBST(bst->left);
  printBST(bst->right); 
}

Node* createRandomBST(size_t len){
  if(len == 0) {return NULL;}

  Node* tempBST = createNode(rand()%200); //start by creating root node.

  printf("   root: %d \n",  tempBST->data); // print the root node

  Node* ptr_1; 
  Node  *ptr_2;
  ptr_1 = tempBST; // ptr_1 and ptr_2 are copy of the root node.
  ptr_2 = tempBST;


  for(int  i = 0; i < len; i++) {  // start the loop -- tempBST , ptr_1 and ptr_2 are all pointing to the root node 
    int value = i*i+22;    //the value needed to be inserted.
    tempBST = ptr_1;  // every time  need to insert a node it will  start from the root node.

    while (1)  //loop until insertion is happend 
    {
      
      if(value >= tempBST->data) {   //if the value greater than the root->data then go right 
         tempBST = tempBST ->right;  // now tempBST is pointing to tempBST->right not the root 
        if(tempBST == NULL) {       //if tempBST is null then the insertion will happened else loop with tempBST-> as the root..
          tempBST = createNode(value);     //if tempBST->right is empty insert the node.
          printf("right-I: %d, value:%d \n", i, tempBST->data);
          break; break;
        }
      }else { //if the value greater than the root->data then go left 

          tempBST = tempBST ->left; // now tempBST is pointing to tempBST->left not the root
          if(tempBST == NULL) {
          tempBST = createNode(value); //if tempBST->left is null then the insertion will happened else loop with tempBST-> as the root..
          printf("left-I: %d, value:%d \n", i, value);
          break; 
        }   
           
      }
    }
  }
return ptr_2;  //return  a pointer the root;
}




int main() {
  Node* tem; 
  tem = createRandomBST(20);
  printf("%d ", tem->data);
  printBST(tem);

}

问题原因与修正 #

核心错误 #

第二段代码的插入逻辑完全错误，没有将新节点正确关联到二叉搜索树的父节点上：

• 正常代码中，当找到合适的空位置时，直接修改父节点的left/right指针，把新节点挂载到树上：tempBST->right = createNode(value);，这样新节点就成为了原树的一部分。
• 第二段代码中，先将tempBST移动到tempBST->right/tempBST->left，当该位置为空时，直接给局部变量tempBST赋值新节点：tempBST = createNode(value);。这只是改变了局部指针的指向，并没有修改原树中父节点的left/right字段，新节点完全游离于BST之外，所以最终只有根节点存在。

修正方案 #

将第二段代码的while循环逻辑改成与第一段一致的写法，先检查父节点的子指针是否为空，为空则直接赋值该指针，否则再移动到子节点：

while (1)
{
    if(value >= tempBST->data) {
        // 先检查当前节点的右子节点是否为空
        if(tempBST->right == NULL) {
            tempBST->right = createNode(value);
            printf("right-I: %d, value:%d \n", i, value);
            break;
        }
        // 不为空则移动到右子节点继续查找
        tempBST = tempBST->right;
    } else {
        // 先检查当前节点的左子节点是否为空
        if(tempBST->left == NULL) {
            tempBST->left = createNode(value);
            printf("left-I: %d, value:%d \n", i, value);
            break;
        }
        // 不为空则移动到左子节点继续查找
        tempBST = tempBST->left;
    }
}

内容的提问来源于stack exchange，提问作者MAGED AL-WARD