迭代插入二进制搜索tree.Debug C++代码

Question

这里是一个C++函数来从一个整数数组创建一个BST树？
很简单。
取第一个元素，生根。
取下一个数组元素并将其插入树中。
为什么循环从i = 2开始，而不是i = 1？

node* buildtree(int a[], int len) 
{ 
    node* root=new node(a[0]); 
    node* temp=root; 
    for(int i=1;i<len;i++) 
    { 
     while(!(root->left==NULL && root->right==NULL)) 
     { 
      cout<<"here"<<i<<" "<<a[i]<<" " << root->val<<"\n"; 
      if(root->val>a[i]) 
       root=root->left; 
      else 
       root=root->right; 
     } 
     node* currnode=new node(a[i]); 
     if(root->val>a[i]) 
      root->left=currnode; 
     else 
      root->right=currnode; 

     if(root==NULL) 
      cout<<"error...never.here"; 
     root=temp; 
    } 
    return root; 
} 

非常感谢你的解释。我试了另一种方式，但它只找到root.What里面的问题是什么？

node* buildtree(int a[],int len) 
    { node* root=new node(a[0]); 
    node* curr; 
    for(int i=1;i<len;i++) 
    { curr=root; 
     while(curr!=NULL)  
     { 
     if(curr->val>a[i]) 
     curr=curr->left; 
     else 
     curr=curr->right; 
     } 
    curr=new node(a[i]); 
    } 
return root;    
    } 

Answer 1

当试图找到插入点，

while(!(root->left==NULL && root->right==NULL)) 
{ 
    cout<<"here"<<i<<" "<<a[i]<<" " << root->val<<"\n"; 
    if(root->val>a[i]) 
     root=root->left; 
    else 
     root=root->right; 
} 

你只有两个孩子是NULL停止，所以在某些时候或其他，你将设置root到NULL。考虑数组以[5, 3, 6, ... ]开头。你开始

NULL <- node(5) -> NULL 
node(3) <- node(5) ->NULL 

，然后尝试插入3.由于没有两个孩子都是NULL，该while循环运行

if (5 > 7) // false 
    root = root->left; 
else 
    root = root->right; // now root == NULL, oops 

和控制条件检查重新

while(!(NULL->left == NULL && NULL->right == NULL)) 

可能在这里发生segfault，调用未定义的行为。

你应该这样做

while(true) { 
    if (root->val > a[i]) { 
     if (root->left == NULL) { 
      root->left = new node(a[i]); 
      break; 
     } else { 
      root = root->left; 
     } 
    } else { 
     if (root->right == NULL) { 
      root->right = new node(a[i]); 
      break; 
     } else { 
      root = root->right; 
     } 
    } 
} 

Answer 2

因为在循环的第一次迭代，因为根节点没有子节点的while条件是不正确的。

while(!(root->left==NULL && root->right==NULL)

对于i = 1的左侧和右侧节点为NULL和左节点在第一迭代结束填充。