迭代插入二進制搜索tree.Debug C++代碼

這裏是一個C++函數來從一個整數數組創建一個BST樹？
很簡單。
取第一個元素，生根。
取下一個數組元素並將其插入樹中。
爲什麼循環從i = 2開始，而不是i = 1？迭代插入二進制搜索tree.Debug C++代碼

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

來源

2012-02-20 bl3e

它是一個二進制樹BST，或者只是一個任意？ – 2012-02-20 19:28:34

for循環代碼從i = 2開始，而不是i = 1。這是一個錯字嗎？ – MARK 2012-02-20 19:33:31

當試圖找到插入點，

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

來源

2012-02-20 20:59:04

因爲在循環的第一次迭代，因爲根節點沒有子節點的while條件是不正確的。

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

對於i = 1的左側和右側節點爲NULL和左節點在第一迭代結束填充。

來源

2012-02-20 19:31:08 grundprinzip

@grudprinzip謝謝..因爲我沒有注意到這麼愚蠢。 – bl3e 2012-02-20 19:58:22

但爲什麼代碼無法正常工作，儘管root在循環中從不爲空仍然存在分段錯誤 – bl3e 2012-02-20 20:00:00

迭代插入二進制搜索tree.Debug C++代碼

回答

相關問題