簡單二叉搜索樹非遞歸添加函數

我正在嘗試編寫一個BST（），它將字符串作爲節點，而不使用遞歸。這裏是我的代碼的添加功能，請你回顧一下，看看是否易於理解/遵循並指出錯誤。我是編程新手，希望得到任何反饋。簡單二叉搜索樹非遞歸添加函數

#include <iostream> 
#include <string> 
#include <stack> 
#include <queue> 
#include <fstream> 
#include <cstdlib> 
#include <cstring> 

using namespace std; 


int main() { 
class BST { 

private: 
    struct Node { 
     string value; 
     Node* left; 
     Node* right; 
    }; 

    Node* root; 

public: 

BST() 
{ 
root = NULL; 
} 

~BST() 
{ 
    stack<Node*> nodes; 
    nodes.push(root); 
    while(! nodes.empty()) 
    { 
     Node* topNode = nodes.top(); 
     nodes.pop(); 
     if (topNode->left) 
      nodes.push(topNode->left); 
     if (topNode->right) 
      nodes.push(topNode->right); 
     delete topNode; 
     } 
    } 
Node* GetNewNode(string data){ 
    Node* newNode = new Node(); 
    newNode->value=data; 
    newNode->left = newNode->right = NULL; 
    return root; 
} 

Node* Insert(Node* rootPtr,string data){ 
    if(rootPtr == NULL){ 
    rootPtr = GetNewNode(data); 
     return rootPtr; 
    } 
    else if(data<= rootPtr->value){ 
     rootPtr->left = Insert(rootPtr->left,data); 
    } 
    else { 
     rootPtr->right = Insert(rootPtr->right,data); 
    } 
    return rootPtr; 
    } 
    }; 
}

來源

2017-03-07 farah

請問您是否可以正確縮進您的代碼，這很難理解。 –

請提供編譯的代碼。 –

你好，當我上次編譯它時，代碼確實編譯了 – farah

1 - 插入函數：

 while (root != NULL) { // this shouldn't be root, the root isn't the node that traverse your tree, this has to be current 
      ..... 
     }

2 - 你永遠不添加新節點，你只是不斷循環，直到你到達一個空。你應該遍歷您的樹，直到ü找到合適的位置插入您的節點，然後添加新的節點，是這樣的：

current = root; 
prev = current; 
     while (current!= NULL) { 
      prev = current; 
      if (current->value.compare(word) < 0) 
       current = current->left; 
      else 
       current = current->right; 
     } 
//here your new node should be on the left or the right of the prev node

3 - 在「GetNewNode」返回新節點不是根

4 - 你的刪除功能是一團糟，你應該再考慮一遍，然後重新執行它。

最後，我強烈建議您從網上檢查並理解現成的實現，然後嘗試再次編寫您的BST。

來源

2017-03-07 19:00:29

簡單二叉搜索樹非遞歸添加函數

回答

相關問題