如何添加孩子到BST

我想創建/創建一個BST，但它似乎不能正常工作。我真的一直坐在這裏好幾個小時，試圖弄清楚發生了什麼。它已經達到了我繪製了100萬張圖的目的，但我的代碼卻讓我失望。我需要將一個根節點傳遞給一個函數。然後我需要遍歷樹，直到找到函數的父字符串參數與樹父節點的字符串一致。如果我確實找到它，我必須將該字符串插入到父項中，並從該父項創建兩個新的子項。如果我找不到父字符串，那麼我返回false。如何添加孩子到BST

bool insertNode(BSTNode *n, char* parentQ, char* leftQ, char* rightQ) 
{ 
    if(n->Q == parentQ) 
    { 
    n->left = new BSTNode(leftQ); 
    n->right = new BSTNode(rightQ); 
    return true; 
    } 
    else if(n->Q != parent) 
    { 
    insertNode(n->left,parentQ,leftQ,rightQ); 
    insertNode(n->right,parentQ,leftQ,rightQ); 
    } 
    else 
    return false; 
}

此外，我需要另一種方法，採取我已建立的樹，並更正字符串。因此，該方法修改父字符串（如果找到），並查找其子級（如果找到），並將這些字符串替換爲在方法參數中找到的那些字符串。這就像添加一棵子樹而不用擰上整棵樹。提前致謝！

bool changeNode(BSTNode *n,char* parentQ, char* leftQ, char* rightQ) 
{ 
    if(n->Q == leftQ) 
    { 
    n->Q = parentQ; 
    n->left = new BSTNode(leftQ); 
    n->right = new BSTNode(rightQ); 
    return true; 
    } 
    else if(n->Q == rightQ) 
    { 
    n->Q = parentQ; 
    n->left = new BSTNode(leftQ); 
    n->right = new BSTNode(rightQ); 
    return true; 
    } 
    else if(n->Q != leftQ) 
    { 
    changeNode(n->left,parentQ,leftQ, rightQ); 
    } 
    else if(n->Q != rightQ) 
    { 
    changeNode(n->right,parentQ,leftQ,rightQ); 
    } 
    return false; 
}

來源

2013-06-04 umarqattan

你甚至沒有提到是什麼錯誤，例如輸入/輸出預期，但你不應該來檢查當前節點是否實際上有一個左右的孩子，調用函數與前兒童？

else if(n->Q != parentQ) // <--- you have a typo in this line, "parent" 
    {      //  (and you don't even need the 'if') 
    insertNode(n->left,parentQ,leftQ,rightQ); 
    insertNode(n->right,parentQ,leftQ,rightQ); 
    // in this case you return nothing! corrupted return value 
    }

^這似乎很容易出錯，特別是空指針。你應該把它變成類似：

else 
     { 
     if(n->left != NULL) // take a look at nullptr if you have C++11 
      if(insertNode(n->left,parentQ,leftQ,rightQ)) return true; 
     if(n->right != NULL) 
      if(insertNode(n->right,parentQ,leftQ,rightQ)) return true; 
     return false; 
     }

否則你true回報永遠不會被傳播回超過第一return，這樣的話你總是在樹的根實際上是唯一的情況下返回false除非你正在尋找的節點。

此外，不要使用==比較兩個char陣列，除非n->Q實際上是std::string。否則，您應該使用if(strcmp(n->Q, parentQ) == 0)。

然而，你的第二段代碼只是一團糟。你需要更好地瞭解你的else if究竟會發生什麼，看看它是否真的在做你想做的（提示：不是），因爲你目前只執行至多1個代碼塊，即使不止一個條件成立。

來源

2013-06-04 04:46:43

如何添加孩子到BST

回答

相關問題