在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(tree, temp);按值传递tree，这意味着您所做的更改发生的是被设置为它的值相同tree副本。如果您在该功能中更改data，则不会改变temp。

你要么需要改变InsertNode采取引用或双指针（所以你通过引用传递/地址，这样的变化对节点都取得了明显），或更改InsertNode返回新创建的节点（并将其分配给tree（但要确保你只是第一次分配它））。

Answer 2

当您调用insertNode（t-> right和t-> left ...）时，右侧和左侧始终为空。 你应该为他们先创建一个实例，像这样：

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