在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);