递归插入到二叉树中，按值传递指针？

这是我的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

递归插入到二叉树中，按值传递指针？

回答

相关问题