二進制搜索樹實現（C++）

Question

大部分代碼來自Weiss的「C++中的數據結構和算法分析」，在CodeBlock（gnu，gcc）上鍵入代碼後，編譯器報告沒有錯誤，但後來我嘗試創建一個實例並測試它出錯的一些函數。看起來BST（）或insert（）是錯誤的，因爲程序自運行後立即停止。 會有人幫我找出如何解決這個問題？萬分感謝！！！

#include <iostream> 
using namespace std; 
struct TreeNode 
{ 
    int element; 
    TreeNode*left,*right; 
    TreeNode(const int&e,TreeNode*le=NULL,TreeNode*rt=NULL):element(e),left(le),right(rt){}; 
}; 

class BST 
{ 
public: 
    BST(){root=NULL;}; 
    ~BST(){ makeEmpty(root); }; 
// use public member function to call private member functions. 
    void insert(const int & x){ insert(x, root); } 
    void remove(const int & x){ remove(x, root); } 
    TreeNode*findMin() const{ return findMin(root); } 
    bool contain(const int & x) const{ return contain(x,root); } 
    void printNodes() const{ printNodes(root); } 

private: 
    TreeNode*root; 

    void makeEmpty(TreeNode*&); 
    TreeNode* findMin(TreeNode*) const; 
    void insert(const int &, TreeNode*) const; 
    void remove(const int &, TreeNode*) const; 
    bool contain(const int &, TreeNode*) const; 
    void printNodes(TreeNode*) const; 
}; 

void BST::makeEmpty(TreeNode*&t) 
{ 
    if(t!=NULL) 
    { 
     makeEmpty(t->left); 
     makeEmpty(t->right); 
     delete t; 
    } 
    t=NULL; 
} 
TreeNode* BST::findMin(TreeNode*t) const 
{ 
    if(t->left==NULL) return t; 
    return findMin(t->left); 
} 
void BST::insert(const int & x, TreeNode* t) const 
{ 
    if(t==NULL) t=new TreeNode(x,NULL,NULL); 
    else if(x < t->element) insert(x,t->left); 
    else if(x > t->element) insert(x,t->right); 
    else; /// duplicate, do nothing 
} 
void BST::remove(const int & x, TreeNode* t) const 
{ 
    if(t==NULL) return; 
    if(t->element > x) remove(x, t->left); 
    else if(t->element < x) remove(x, t->right); 
    else if(t->left!=NULL && t->right!=NULL) 
    { 
     t->element=findMin(t->right)->element; 
     remove(t->element,t->right); 
    } 
    else 
    { 
     TreeNode*oldNode=t; 
     t=(t->left==NULL)?t->right:t->left; 
     delete oldNode; 
    } 
} 
bool BST::contain(const int & x, TreeNode*t) const 
{ 
    if(t==NULL) return false; 
    else if(x<t->element) return contain(x,t->left); 
    else if(x>t->element) return contain(x,t->right); 
    else return true; 
} 
void BST::printNodes(TreeNode*t) const 
{ 
    if(t==NULL) return; 
    cout<<t->element<<" "; 
    printNodes(t->left); 
    printNodes(t->right); 
    cout<<endl; 
}; 

下面是我寫的測試類BST代碼：

int main() 
{ 
    BST BinarySearchTree; 
    int element,node; 
    for(int i=0; i<5; i++) 
    { 
     cin>>element; 
     BinarySearchTree.insert(element); 
    } 
    BinarySearchTree.printNodes(); 

    cout<<BinarySearchTree.findMin()->element<<endl; 

    cin>>node; 
    if(BinarySearchTree.contain(node)){ cout<<"item "<<node<<" is in BST."<<endl; } 

    BinarySearchTree.remove(node); 
    BinarySearchTree.printNodes(); 
    return 0; 
} 

Answer 1

你的類BST只有一個成員變量。 TreeNode*root。 （有沒有問題與）

你insert和remove功能想必修改的BST，所以你需要修改與root東西。

（和你的編譯器會迅速指出，這些功能不應該const出於同樣的原因。）

Answer 2

您在insert()什麼也沒做有根，所以它什麼都不做（除了內存泄漏）。

Answer 3

void BST::makeEmpty(TreeNode*&t) 
{ 
    if(t==NULL) 
    { 
     makeEmpty(t->left); 
     makeEmpty(t->right); 
     delete t; 
    } 
    t=NULL; 
} 

這段代碼是錯誤的，如果t爲NULL，那麼你做t-> left和t-> right。這被稱爲取消引用空指針，並可能使您的程序立即崩潰。

這應該是

void BST::makeEmpty(TreeNode*&t) 
{ 
    if (t!=NULL) 
    { 
     makeEmpty(t->left); 
     makeEmpty(t->right); 
     delete t; 
    } 
    t=NULL; 
} 

Answer 4

如果要交叉檢查您的解決方案，你會發現在這裏https://siddharthjain094.wordpress.com/2014/07/13/binary-search-tree-implementation-in-ccpp/