c++ - 使用模板在 C++ 中构建 BST

Question

我试图在 c++ 中使用模板实现通用 BST。但是，当我使用 gdb 调试它时。我发现每当我调用 InsertNode 时，它​​都会将 t 视为 NULL。当我单步执行 insertFunction 时，它运行正常。使用模板时声明树有什么问题吗？

//
//  main.cpp
//  c++_project
//
//  Created by Timothy Leung on 5/5/13.
//  Copyright 2013 __MyCompanyName__. All rights reserved.
//

#include <iostream>

using namespace std;

template <typename data_t>
struct nodeT{
    data_t data;
    nodeT *left, *right;
};

template <typename data_t>
nodeT<data_t> *FindNode(nodeT<data_t> *t, data_t data);

template <typename data_t>
void InsertNode(nodeT<data_t> *t, data_t data); 

template <typename data_t>
void display_tree(nodeT<data_t> *t);

int main (int argc, const char * argv[])
{

    cout << "Welcome to my BST! " << endl;
    nodeT<int> *tree;
    cout << "How many items do you have? \n";
    int num, temp;
    cin >> num;
    for (int i=0; i<num; ++i) {
        cout << "Number please :) \n";
        cin >> temp;
        InsertNode(tree, temp);
    }
    cout << "In order treeeeeee \n"<<endl;
    display_tree(tree);
}

template <typename data_t>
nodeT<data_t> *FindNode(nodeT<data_t> *t, data_t data){
    if(t==NULL) return NULL;
    if(data==t->data) return t;
    if (data < t->data) {
        FindNode(t->left, data);
    } else
        FindNode(t->right, data);
}

template <typename data_t>
void InsertNode(nodeT<data_t> *t, data_t data){
    if(t==NULL){
        t = new nodeT<data_t>;
        t->data = data;
        t->left = NULL;
        t->right = NULL;
        return;
    } 
    if(t->data < data){
        InsertNode(t->right, data);
    } else
        InsertNode(t->left, data);
}

template <typename data_t>
void display_tree(nodeT<data_t> *t){
    if (t!=NULL) {
        display_tree(t->left);
        cout << t->data << endl;
        display_tree(t->right);
    }
}

Answer 1

当您调用 insertNode(t->right and t->left...) 时，right 和 left 始终为 null。您应该首先为它们创建一个实例，如下所示：

t->right = new nodeT<data_t>;
insertNode(t->right,data);

Answer 2

InsertNode(tree, temp);按值传递tree，这意味着您所做的更改会发生一个副本，tree该副本已设置为相同的值。同理，如果你要改变data函数，你就不会改变temp.

您要么需要更改InsertNode以获取引用或双指针（因此您通过引用/地址传递，因此对节点的更改显而易见），或者更改InsertNode以返回新创建的节点（并将其分配给tree（但请确保您只第一次分配它））。