BST插入功能幫助

Question

嘿所以我試圖寫一個BST，但我有很多錯誤，我很不知所措，並失去了做什麼。你們可以看一看，指出什麼是關閉的。老師在解釋任何事情時都沒什麼用處。

頭在.h文件

class Tree 
{ 
public: 
    bool insert(int k, string s); 

private: 
    struct Node 
    { 
     int key; 
     string data; 
     Node *left; 
     Node *right; 
    }; 
    Node* root; 
    bool insert(Node *& root, int k, string s); 
}; 

.cpp文件

bool Tree::insert(int k, string s) 
{ 
    return insert(root, k, s); 
} 
bool Tree::insert (Node *& root, int k, string s) 
{ 
    if (root == NULL){ 
     root = new Node; 
     root->key = k; 
     root->data = s; 
     root->left = NULL; 
     root->right = NULL; 
    } 
    else if (root == k) 
     return false; 
    else if (root->key < k) 
     insert (root ->left, k); 
    else 
     insert (root -> right, k); 
} 

Answer 1

看來你有很多未經測試的代碼。您將不得不一次性地使用這些功能。

此外，我已經看到至少有一個重複努力的實例。方法preOrder和postOrder應該是相同算法的輕微變化，但一個是基於循環的，另一個是通過函數遞歸來工作的。

將這些源文件放在一邊，創建一個新項目，並一次複製粘貼一個功能。在開始下一個功能之前，請先徹底測試一下。如果您到達現有代碼中可能已存在的功能，請不要從舊代碼複製粘貼，而是使用現有的測試代碼。

編輯

看起來應該是這樣。如果你想要他們，這裏有幾個風格批評：v）。

1. Node結構應該有它自己的構造函數。總是提供一個構造函數來幫助保證沒有任何東西可以處於無效狀態。
2. 同樣，當您創建新的Tree時，需要將root設置爲NULL。
3. 更改root參數的值不是很好的風格。乍一看，它看起來像left和right永遠不會收到非NULL值。就我個人而言，我喜歡這裏的指針指針，但有些人可能會贊同您的實現。

Answer 2

一件事，你必須在你的代碼的末尾缺少支架。

Answer 3

沒有看實際的實現，有很多與界面相關的陷阱。這裏有一些是：

• 您在頭文件中缺少include guard。
• 在被包含的頭文件的全局範圍內說「using namespace std」是允許的，但是它的風格很糟糕。
• Tree::findKey方法接受字符串作爲非常量引用，爲什麼？
• Tree::insert接受字符串的值，這涉及到不必要的複製，爲什麼？
• preOrder和levelOrder需要指向函數的指針。如果我想調用一個類方法或傳遞其他參數呢？我會說你有更好的預測，或者說boost::function。
• 不修改狀態（類內數據）的方法不是市場常數（const修飾符）。例如，isEmpty()方法。方法不是exception-safe。
• 使用帶符號整數代替size_t。

希望它有幫助。

Answer 4

編寫你的第一個BST可能很難...接受Potatoswatter的建議，我首先要確保你有一個非常實用的插入函數，然後再去任何其他地方。所以，你可以創建一個類爲您的BST，包括聲明的功能，但在他們的定義，只是讓他們空的功能，例如：

在你的頭文件：

class BST 
{ 
    public: 
     BST(); 
     bool insert(int k, const string& s); 
     bool findKey(int k, string& s); 
     int maxKey(); 

     /* ... the rest of your class ...*/ 
}; 

在你。 CPP文件：

#include "BST.h" 

BST::BST() 
{ 
    /*initialize anything required for your insert function to work*/ 
} 

//pass in a const reference for your string argument, 
//or else you could end up doing a lot 
//of extra processing creating a new copy of your string on the stack for 
//each insertion call 
bool BST::insert(int k, const string& s) 
{ 
    /* write your insertion algorithm implementation */ 
} 

//make the rest of your function definitions that don't 
//apply to insertion empty so you can compile and test your insertion algorithm 
//without adding more cruft 
bool BST::findKey(int k, string& s) {} 

int BST::maxKey() {} 

/* continue process for the rest of the class */ 

這種方法

現在，你可以測試，以確保正確插入節點到您的樹沒有崩潰等，一旦做到這一點，你可以測試一下，看看你能不能找到你插入的節點。之後，您可以完成剩下的功能的定義，以完成刪除，迭代等功能。但是，通過將定義留空而不需要每個階段的功能，您可以正確構建解決方案，而無需編譯器錯誤和其他非相關項目的混亂使您無法構建手頭任務的實際界面。換句話說，您無法從沒有正確插入節點的樹中找到或刪除沒有問題的節點，所以當您不想在這些步驟中追逐尾巴時沒有正確的第一步。你也可能會發現，當你執行後面的步驟，比如找到一個節點時，仍然存在插入問題......如果你只實現了插入和查找節點的完整定義，那麼這些是唯一的兩個函數，將不得不擔心修復。

所以把它分解成它的基本部件（插入，查找，刪除，然後一切），你就會把工作做:-)