使用類的二進制搜索樹

Question

我一直在嘗試使用類實現二叉搜索樹。每次我嘗試編譯和運行程序時，程序都會結束。我已經嘗試了很多東西，比如讓* root公開在main中訪問它，這樣我就可以更新根目錄，但不知何故每次都會變爲null。 幫助將不勝感激。 這是我的大學項目。

#include <iostream> 
using namespace std; 
class tree; 
class Node { 
    friend class tree; 
private: 
    Node *lchild,*rchild; 
    int data; 
public: 
    Node (int x) { 
     data = x; 
     lchild = rchild = NULL; 
    } 
}; 
class tree { 
protected: 
    Node* root; 
    void inorder(const Node* root)const; 
public: 
    tree() { 
     root = NULL; 
    } 
    bool insert(int item); 
    void inorder() const {inorder(root);}; 
    Node* getroot() { 
     return root; 
    } 
}; 
bool tree :: insert(int item) { 
    if (root == NULL) { 
     Node *temp = new Node(item); 
     root = temp; 
     return (bool) root; 
    } 
    if (item < root -> data) { 
     insert(item); 
    } 
    if (item > root -> data) { 
     insert(item); 
    } 
    else if (item == root -> data) { 
     cout<<"Duplicate"; 
     exit (0); 
    } 
    return (bool) root; 
} 
void tree :: inorder(const Node *root)const { 
    if (root != NULL) { 
     inorder(root -> lchild); 
     cout<<root -> data; 
     inorder(root -> rchild); 
    } 
} 
int main() 
{ 
    tree obj1; 
    obj1.insert(3); 
    //obj1.insert(4); 
    obj1.insert(1); 
    //obj1.insert(5); 
    obj1.inorder(); 
} 

Answer 1

之所以root再次得到NULL，再次是，它實際上不會改變其值比NULL別的東西。 也許你在解決其他一些問題的過程中在代碼中引入了這種行爲;但你在構造函數中指定root=NULL;之後，您只分配obj.root1 = ...，而您在getroot() { return root; }中返回root。此外，您通過Node *root作爲您插入功能的參數;請注意，名爲root的本地變量隱藏數據成員root，因此這些函數中的root->...將始終處理本地變量而不是數據成員。

在介紹需要重新設計界面的代碼之前，我建議先調整設計，然後修改代碼;我很確定這些錯誤會消失。我建議如下改編class tree的接口並在其周圍編寫代碼。

成員函數inorder()應該是const以指示它不會更改對象的狀態。請注意，const - 成員函數可以 - 與其他非靜態成員函數相反 - 可在const對象上調用。

class Node { 
    friend class tree; 
private: 
    Node *lchild,*rchild; 
    int data; 
public: 
    Node (int x) { 
     data = x; 
     lchild = rchild = NULL; 
    } 
}; 
class tree { 
public: 
    tree() { root = NULL; } 
    bool insert(int item) { return insert(item,root); }; 
    void inorder() const { inorder(root);}; 

protected: 
    Node* root; 
    void inorder(const Node* curr) const; 
    bool insert(int item, Node* curr); 

}; 

bool tree :: insert(int item, Node *currNode) { 
    if (root == NULL) { 
     root = new Node(item); 
     return true; 
    } 
    else if (item < currNode->data) { 
     if (currNode->lchild == NULL) { 
      currNode->lchild = new Node(item); 
      return true; 
     } 
     else { 
      return insert(item, currNode->lchild); 
     } 
    } 
    else if (item > currNode->data) { 
     if (currNode->rchild == NULL) { 
      currNode->rchild = new Node(item); 
      return true; 
     } 
     else { 
      return insert(item, currNode->rchild); 
     } 
    } 
    else // item == currNode->data 
     return false; // duplicate; do not insert 
}