這個問題比我以前帶來的問題稍微複雜一點，所以我會試着非常明確地說明我已經將其縮小到。添加葉函數「懸掛」，在C++中定製BST類
我正在C++中編寫一個二進制搜索樹數據類，它的功能類似於標準BST，只是它使用BST節點中的「count」字段存儲奇數的重複項。
我寫了一個測試驅動程序來測試類的成員函數，並遇到了一個我似乎無法解決的錯誤。當我嘗試向BST對象中添加一組隨機整數時，它們似乎都沒有進入樹狀結構。要檢查內容，我使用了已確認的printInOrder函數正常工作，所以我知道問題不在那裏。對於初學者，我將發佈addLeaf，printInOrder和createLeaf函數，以及在我的驅動程序文件中調用它們的小塊代碼。
bool fixedDupBST::addLeaf(int key)
{
if(root == nullptr){
root = createLeaf(key);
assert(root != nullptr);
}
else {
node *prev = nullptr;
node *scanPtr = root;
bool right, dupe = false;
while(scanPtr != nullptr) {
prev = scanPtr;
if(key < scanPtr->key) {
scanPtr = scanPtr->left;
right = false;
}
else if (key == scanPtr->key) {
if (scanPtr->keyCount >= 1)
dupe = true;
else{
dupe = false;
scanPtr = nullptr;
}
}
else {
scanPtr = scanPtr->right;
right = true;
}
}
if (dupe)
prev->keyCount++;
else if (!dupe)
return false;
else if (right) {
prev->right = createLeaf(key);
assert(prev->right != nullptr);
}
else {
prev->left = createLeaf(key);
assert(prev->left != nullptr);
}
}
return true;
}
fixedDupBST::node* fixedDupBST::createLeaf(int key)
{
node* newNode = new node;
assert(newNode != nullptr);
newNode->key = key;
newNode->left = nullptr;
newNode->right = nullptr;
if (key % 2 != 0)
newNode->keyCount = 1;
else
newNode->keyCount = 0;
return newNode;
}
void fixedDupBST::printInOrder()
{
printInOrderPr(root);
}
void fixedDupBST::printInOrderPr(node* Ptr)
{
if(root != nullptr) {
if(Ptr->left != nullptr){
printInOrderPr(Ptr->left);
}
cout << Ptr->key << ' ';
if(Ptr->right != nullptr) {
printInOrderPr(Ptr->right);
}
}
else {
cout << "The tree is empty" << endl;
}
return;
}
void testInsert(fixedDupBST &BST)
{
int temp;
for (int i = 0; i < TEST_PARAM; i++) {
temp = randNum();
BST.addLeaf(temp);
}
BST.printInOrder();
return;
}
我得到的問題是，當我打電話printInOrder（）它總是給「樹是空的」。起初我認爲這可能是一個問題，我如何在類成員函數中傳遞參數（通過引用傳遞值傳遞），但沒有提供任何解決方案。如果在函數的其餘部分有任何問題，它似乎並不重要，因爲根永遠不會分配給第一個節點，（因此爲什麼按順序打印只是說「樹是空的」。）
I需要第二套眼睛在此;感謝先進的你的幫助，並讓我知道如果我可以重新修改我的問題或提供更多的信息，以幫助使情況更清楚
編輯：R Sahu錯誤正確，但他的回答有點偏離，我意識到一個布爾不會乾淨地爲我正在嘗試做的事情工作，因爲實際上有三種情況： 該數字是重複的並且是奇數， 該數字是重複的，並且是甚至 和數字不是一個重複icate。
該問題源於這樣的事實：while循環的退出條件是scanPtr爲空，並且最後的if/else-if語句無法知道它是否爲null，因爲它到達了子樹，並準備插入，或者如果我已經手動將其設置爲null，一旦找到重複以適當地打破循環。
這是我提出的解決方案。
bool fixedDupBST::addLeaf(int key)
{
if(root == nullptr){
root = createLeaf(key);
assert(root != nullptr);
}
else {
node *prev = nullptr;
node *scanPtr = root;
bool right;
int dupe = 0; // switch variable
while(scanPtr != nullptr) {
prev = scanPtr;
if(key < scanPtr->key) {
scanPtr = scanPtr->left;
right = false;
}
else if (key == scanPtr->key) {
if (key % 2 != 0) {
dupe = 1;
scanPtr = nullptr;
}
else{
dupe = 2;
scanPtr = nullptr;
}
}
else {
scanPtr = scanPtr->right;
right = true;
}
}
if (dupe == 2)
return false;
if (dupe == 1)
prev->keyCount++;
else if (right) {
prev->right = createLeaf(key);
assert(prev->right != nullptr);
}
else {
prev->left = createLeaf(key);
assert(prev->left != nullptr);
}
}
return true;
}
現在一切正常工作。
我不明白爲什麼這段代碼不起作用。嘗試使用調試器？在所有方法中特別注意'this'的值。將您的測試減少爲爲初學者插入一個節點。 – Arkadiy 2014-11-03 20:50:47
它會添加一個節點。我只是從main（）調用BST.addLeaf（）。它只會添加第一個節點，但我試着用幾個硬編碼值從main手動調用它，並且只有第一個int被printInOrder打印。所以它要麼沒有被添加，要麼沒有被打印。 – user3776749 2014-11-03 21:02:08