爲什麼這個二進制搜索樹導致堆棧溢出？

-1

#include<iostream> 
using namespace std; 
/*main idea is to construct ordered statistic tree,which is similar of 
binary search tree,width addition of one key,which shows us it's rank in given 
tree,for this i introduced additional one key-rank 
*/ 
struct node 
{ 
    int val; 
    node *left,*right; 
    int rank; 
    node(int t) { val=t;left=right=NULL;} 


}; 
node *root; 
void insert(node *p,int ele) 
{ 
    if(p==NULL){ 
     p=new node(ele); 
     return ; 


    } 
    else if(ele<p->val) 
    { 
     insert(p->left,ele); 

    } 
    else if(ele>p->val) 
    { 
     insert(p->right,ele); 

    } 

} 
void inorder (node *p) 
{ 
    if(p!=NULL){ inorder(p->left); 
    cout<<p->val<<" "<<p->rank; 
    inorder(p->right); 
    } 

} 
int count_node(node *t) 
{ 
    int sum=0; 
    if(t==NULL) return 0; 
    else sum=1; 
    if(t->left) sum+=count_node(t->left); 
    if(t->right) sum+=count_node(t->right); 
    return sum; 
} 

int main() 
{ 
    root=NULL; 
    root->rank=0; 
    insert(root,26); 
    insert(root,17); 
    insert(root,41); 
    insert(root,14); 
    insert(root,30); 
    insert(root,21); 
    insert(root,47); 
    insert(root,10); 
    insert(root,16); 
    insert(root,28); 
    insert(root,38); 
    insert(root,35); 
    insert(root,39); 
    insert(root,19); 
    insert(root,21); 
    insert(root,20); 
    insert(root,7); 
    insert(root,12); 
    insert(root,3); 
    inorder(root); 

    return 0; 
}

此代碼會導致溢出，但我不明白爲什麼，因爲我已經正確構造了構造函數。爲什麼這個二進制搜索樹導致堆棧溢出？

來源

2012-03-27 dato datuashvili

您是否調試過代碼？ – 2012-03-27 08:15:09

的問題是：

root=NULL; 
root->rank=0;

這個原因不確定的行爲因爲取消引用NULL指針。任何事情都可能發生。

另外：

void insert(node *p,int ele) 
{ 
    if(p==NULL){ 
     p=new node(ele); 
     return ; 


    } 
    //... 
}

這不會修改原始指針。如果您在NULL指針上調用insert，則函數返回時將爲NULL。您需要按引用傳遞它：

void insert(node *& p,int ele)

來源

2012-03-27 08:16:08

除了什麼Luchian說，你也有這樣的問題：

void insert(node *p,int ele) 
{ 
    if(p==NULL){ 
     p=new node(ele); 
     return ; 
    } 
....

在指針p是按值傳遞。當您說p=...時，您正在更改僅對該函數可見的指針副本。您可能需要一個reference指針你改變：

void insert(node *&p, int ele){ ... }

來源

2012-03-27 08:18:36 Vlad

那麼如何在主要部分調用插入方法？ – 2012-03-27 08:22:50

如果您通過[reference]（http://www.parashift.com/c++-faq-lite/references.html#faq-8.1）（在函數簽名中使用'＆'）傳遞它，則將其稱爲之前，編譯器確保爲該函數提供'root'變量的地址，而不僅僅是它的值（最初是'NULL'）。 – Vlad 2012-03-27 14:48:36

root=NULL; 
root->rank=0;

這可能是問題，你不應該尊重一個NULL對象。

來源

2012-03-27 08:19:03 Sanish

是的，但我無法打印值，我已經改變了它，但仍然不起作用 – 2012-03-27 08:34:03

希望你已經改變了使用'new'創建了一個'node'類型的對象。你現在得到的錯誤是什麼？ – Sanish 2012-03-27 08:53:48

它現在有效，謝謝你們 – 2012-03-27 08:54:26

你有一個非常大的問題，您main功能的前兩行：

root=NULL; 
root->rank=0;

如果你看看你自己定義的上方，該root被定義爲節點指針，那就是它不爲實際節點保留任何空間。

如果您自己不預留空間，那麼您嘗試通過未初始化的內存進行寫入。更重要的是，你明確地說根指向沒有什麼，那就是NULL。在下一行中，您嘗試訪問它的名爲rank的成員。

你應該嘗試更換行：

root = NULL;

隨着

root = new node(0);

或類似的東西，實際上保留了空間，並構建了一個節點。

或者，您可以嘗試在最後根據等級排序，因爲如果該函數不存在，您實際上會構造根。編輯作爲陸建說，你只有嘗試來構建insert方法的根。如果您按照他所建議的方式重新編寫插入方法，則只需將root->rank=0;行移動到插入過程的末尾即可。

來源

2012-03-27 08:19:31 penelope

爲什麼這個二進制搜索樹導致堆棧溢出？

回答

相關問題