遞歸插入到二叉樹中，按值傳遞指針？

這是我的Node類。遞歸插入到二叉樹中，按值傳遞指針？

class Node 
{ 
private: 
public: 
    T data; 
    Node<T>* left; 
    Node<T>* right; 
    Node(T dat) : data(dat), left(NULL), right(NULL) 
    {} 
};

這裏是我的插入功能，在我的B樹類中定義：

public: 
    Node<T>* root; 
    Btree() : root(NULL){} 
    void insert(T data, Node<T>* parent) 
    { 
     if(!parent ) 
     { 
     parent = new Node<T>(data); 
     return; 
     } 
     else if(data < parent->data) 
     { 
     insert(data, parent->left); 
     } 
     else if(data > parent->data) 
     { 
     insert(data, parent->right); 
     } 
    } 

};

這裏是我的主要功能：

int main() 
{ 
    Btree<int> tree; 

    tree.insert(5, tree.root); 

    cout << tree.root->data << endl; 

    tree.insert(6, tree.root); 

    cout << tree.root->right->data << endl; 

}

當我跑，我得到了賽格故障。

我認爲這是因爲指針變量parent是通過值傳遞的，所以當我創建一個由父指向的新節點時，一旦我退出插入函數，就會丟失它？這是否意味着我必須在這裏使用雙指針？

有人可以給我一個關於內存中發生了什麼事情的詳細解釋，這使得這不能按計劃進行。我的診斷是否正確？還是有其他問題？

當我通過tree.root作爲插入的第二個參數時，我傳遞了一個Node *，我知道那麼多。現在，即使按值傳遞，它是否與我從調用main函數傳遞的地址不同。所以當我說parent（這是我從main，tree.root傳遞的地址）= new Node時，是不是應該在堆的父地址上創建一個新的節點，也就是tree.root的地址？爲什麼通過價值傳遞這一點呢？

來源

2012-07-14 ordinary

而不是猜測，你可以運行你的程序在調試器中，它會告訴你**確切地說**哪一行導致了seg-fault。然後，您可以檢查變量值等，以瞭解發生了什麼。 – 2012-07-14 23:11:23

我知道哪一行導致seg錯誤，我要求通過值來澄清傳遞地址。 – ordinary 2012-07-14 23:12:30

在這種情況下傳遞值的問題是，對函數內的形式參數所做的所有賦值對調用者都是不可見的。因此，這種分配

if(!parent ) 
{ 
    parent = new Node<T>(data); // <<== HERE 
    return; 
}

在呼叫者對tree.root沒有影響：

tree.insert(5, tree.root);

在函數中parent指針的值被改變，並且然後迅速丟棄;樹的root仍然是NULL。

甲對此問題修復將指針傳遞到一個指針，這樣的：

void insert(T data, Node<T>** parent) { 
    if(!*parent ) 
    { 
     *parent = new Node<T>(data); 
     return; 
    } 
    else if(data < (*parent)->data) 
    { 
     insert(data, &((*parent)->left)); 
    } 
    else if(data > (*parent)->data) 
    { 
     insert(data, &((*parent)->right)); 
    } 
}

來源

2012-07-14 23:26:37 dasblinkenlight

C++經過值，從而parent是傳入的指針的一個拷貝。因此分配給它沒有持久效果。解決此問題的最簡單方法是更改方法的簽名，以便它接受對指針的引用。這將自動使編譯器更新原始指針，同時避免必須更改程序的其餘部分。

來源

2012-07-14 23:27:09 Neil

dasblinkenlight回答了最好。但是，還有一個更簡潔的解決方案：

得到的指針（被稱爲參考指針）的參考：

void insert(T data, Node<T>*& parent) 
    { 
     if(!parent ) 
     { 
     parent = new Node<T>(data); 
     return; 
     } 
     else if(data < parent->data) 
     { 
     insert(data, parent->left); 
     } 
     else if(data > parent->data) 
     { 
     insert(data, parent->right); 
     } 
    }

來源

2012-07-14 23:39:32 jrd1

遞歸插入到二叉樹中，按值傳遞指針？

回答

相關問題