我的二叉樹插入邏輯的缺陷在哪裏？

Question

我的解決辦法是像

/* 
Node is defined as 

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

*/ 


node * insert (node * root, int value) 
{ 
    bool inTreeAlready = false; 
    node * cur = root; 
    while(cur != NULL) 
    { 
     if(cur->data < value) 
      cur = cur->right; 
     else if(cur->data > value) 
      cur = cur->left; 
     else 
     { 
      inTreeAlready = true; 
      break; 
     } 
    } 
    if(!inTreeAlready) 
    { 
     cur = new node; 
     cur->data = value; 
     cur->left = NULL; 
     cur->right = NULL; 
    } 
    return root; 
} 

其中提示的問題說你應該插入後返回樹的根。

這顯然錯了，因爲輸出是

Wrong Answer! 
Some possible errors: 
1. You returned a NULL value from the function. 
2. There is a problem with your logic 
3. You are printing some value from the function 

這是不是很描述。

我仔細檢查了我的邏輯，不知道交易是什麼。

Answer 1

您沒有將新節點添加到樹中。這是一個修改後的版本。

node * insert (node * root, int value) 
{ 
    bool inTreeAlready = false; 
    node * cur = root; 
    node *parent; 
    bool right; 
    while(cur != NULL) 
    { 
     parent = cur; 
     if(cur->data < value) 
     { 
      cur = cur->right; 
      right = true; 
     } 
     else if(cur->data > value) 
     { 
      cur = cur->left; 
      right = false; 
     } 
     else 
     { 
      inTreeAlready = true; 
      break; 
     } 
    } 
    if(!inTreeAlready) 
    { 
     cur = new node; 
     cur->data = value; 
     cur->left = NULL; 
     cur->right = NULL; 
     if(root == NULL) root = cur; 
     else if(right) parent->right = cur; 
     else parent->left = cur; 
    } 
    return root; 
}