我的二叉树插入逻辑的缺陷在哪里？

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; 
}