2
我試圖在C++中管理BST以達到我的學術目的。從C++二進制搜索樹中刪除一個節點（類不是結構體）
我並沒有問題，除了DeleteNode函數的任何位置，也 我選擇來實現與class，而不是用struct這個數據結構。
問題是，我無法弄清楚如何使刪除功能正常工作，通常我得到0xDDDDDDDDD錯誤我的調試器說，有時我可以刪除節點，有時我的程序崩潰。
我認爲這是指針的一個可能的問題，但我無法弄清楚我做錯了什麼地方。
這是我刪除節點的功能，一個我得到約很大的麻煩：
編輯：沒有兒子刪除的情況下工作完美，一個我越來越生氣的就是單子案刪除。
//function that delete a selected node
void DeleteNode(TreeNode* root,int key) {
/*we got three case here:*/
//until we find the right node with value in the tree
if (root->getValue() != key && root != nullptr) {
if (root->getValue() > key) {
DeleteNode(root->Left, key);
}
else if (root->getValue() < key) {
DeleteNode(root->Right, key);
}
}
else { //when we found the right node, then operate
/* THIS WORKS PERFECTLY! */
//first case: our node got no right and left son
if (!root->Left && !root->Right) {
TreeNode* tmp = root->Father;
if (tmp->Left == root) { //if the son is a left son
tmp->Left = nullptr;
delete root;
}
else if (tmp->Right == root) { //if the son is a right son
tmp->Right = nullptr;
delete root;
}
}
//second case: our node got a left but no right son
/* THIS ONE DOESN'T WORK. */
else if (!root->Right) {
TreeNode *tmp = root;
root = root->Left; //new root is the left son of the root
root->Father = tmp->Father; //linking the father to the new son
tmp->Father->Left = root; //linking the son to the new father
delete tmp;
std::cout << "Erased!" << std::endl;
}
else if (!root->Left) {
TreeNode *tmp = root;
root = root->Right; //new root is the right son of the root
root->Father = tmp->Father; //linking the father to the new son
tmp->Father->Right = root; //linking the son to the new father
delete tmp;
std::cout << "Erased!" << std::endl;
}
}
}
我嘗試了很多組合的，但結果是相同的，每次：它崩潰上InOrder顯示功能的第一次出現。 （當它不，該功能只刪除第一個節點，然後崩潰當我嘗試刪除一個新的）
這裏有一個簡單的主那裏我試圖採取行動刪除：
int main()
{
TreeNode root;
root.insertNode(&root,50);
root.insertNode(&root,30);
root.insertNode(&root,20);
root.insertNode(&root,40);
root.insertNode(&root,70);
root.insertNode(&root,60);
root.insertNode(&root,80);
for (int i = 0; i < 5; i++) {
int n;
cin >> n;
root.DeleteNode(&root, n);
cout << "In-Order: "; root.inOrder(&root);
cout << endl;
cout << "Pre-Order: "; root.preOrder(&root);
cout << endl;
cout << "Post-Order: "; root.postOrder(&root);
cout << endl;
}
}
這裏是我的全BST代碼（除刪除一個，我之前遞交，僅僅因爲是在我的代碼的理解更完整）
class TreeNode {
private:
int value;
TreeNode* Left;
TreeNode* Right;
TreeNode* Father;
public:
//constructor
TreeNode() {
this->Right = nullptr;
this->Left = nullptr;
this->Father = nullptr;
}
TreeNode(int value) {
this->value = value;
this->Right = nullptr;
this->Left = nullptr;
this->Father = nullptr;
}
//functions
int getValue() { return value; }
void setValue(int value) { this->value = value; }
//function to create a new node and insert a value into it
TreeNode* insertNode(TreeNode* root, int value) {
if (root->getValue() == NULL) {
root->setValue(value);
root->Father = nullptr;
}
else {
if (value > root->getValue()) {
if (root->Right) {
insertNode(root->Right, value);
}
else
root->Right = new TreeNode(value);
root->Right->Father = root;
}
else if (value < root->getValue()) {
if (root->Left) {
insertNode(root->Left, value);
}
else
root->Left = new TreeNode(value);
root->Left->Father = root;
}
}
return root;
}
//function to search a value into a BST
TreeNode* SearchNode(TreeNode* root, int key) {
if (root->getValue() == key) {
return root;
}
else if (root->getValue() < key) {
if (root->Right) {
SearchNode(root->Right, key);
}
else return nullptr;
}
else if (root->getValue() > key) {
if (root->Left) {
SearchNode(root->Left, key);
}
else return nullptr;
}
}
//function that return the height of the tree
int TreeHeigth(TreeNode* root) {
int heigth;
if (root == nullptr) {
return 0;
}
else {
return heigth = 1 + max(TreeHeigth(root->Left), TreeHeigth(root->Right));
}
}
//function that returns the number of the nodes
int CountTreeNode(TreeNode* root) {
if (root == nullptr) {
return 0;
}
else {
return CountTreeNode(root->Left) + CountTreeNode(root->Right) + 1;
}
}
//function that returns the minimum values into the tree
TreeNode* MinimumNode(TreeNode* root) {
if (root == nullptr) {
return nullptr;
}
while (root->Left != nullptr) {
root = root->Left;
}
return root;
}
//function that returns the maximum value into the tree
TreeNode* MaximumNode(TreeNode* root) {
if (root == nullptr) {
return nullptr;
}
while (root->Right != nullptr) {
root = root->Right;
}
return root;
}
//function that returns a successor of a given nodeb
TreeNode* SuccessorNode(TreeNode* node) {
//first case: our node got a rigth subtree:
if (node->Right != nullptr) {
return MinimumNode(node->Right);
}
//second case: our node doesnt got a right subtree: lets get
//upper in the tree until our node isn't a left child.
TreeNode* Ancestor = node->Father;
while (Ancestor != nullptr && node == Ancestor->Right) {
node = Ancestor;
Ancestor = Ancestor->Father;
}
}
//function tht returns a predecessor of a given node
TreeNode* PredecessorNode(TreeNode* node) {
//first case: (inverse to successor) our node got a left subtree:
if (node->Left != nullptr) {
return MaximumNode(node->Left);
}
TreeNode* Ancestor;
if (node->Father == nullptr)
return nullptr;
else
Ancestor = node->Father;
while (Ancestor != nullptr && node == Ancestor->Left) {
node = Ancestor;
Ancestor = Ancestor->Father;
}
return Ancestor;
}
//function that prints information about nodes
void InfoNode(TreeNode *root) {
root != nullptr ? std::cout << "Nodo corrente: " << root->getValue() << std::endl
: std::cout << "Nodo corrente: " << "NULL" << std::endl;
root->Father != nullptr? std::cout << "Padre: " << root->Father->getValue() << std::endl
: std::cout << "Padre: " << "NULL" << std::endl;
root->Left != nullptr ? std::cout << "Figlio SX: " << root->Left->getValue() << std::endl
: std::cout << "Figlio SX: " << "NULL" << std::endl;
root->Right!= nullptr ? std::cout << "Figlio DX: " << (root->Right)->getValue() << std::endl
: std::cout << "Figlio DX: " << "NULL" << std::endl;
}
//visits of a tree
void preOrder(TreeNode* root) {
if (root != nullptr) {
std::cout << root->getValue() << " ";
preOrder(root->Left);
preOrder(root->Right);
}
}
void inOrder(TreeNode* root) {
if (root != nullptr) {
inOrder(root->Left);
std::cout << root->getValue() << " ";
inOrder(root->Right);
}
}
void postOrder(TreeNode *root) {
if (root != nullptr) {
postOrder(root->Left);
postOrder(root->Right);
std::cout << root->getValue() << " ";
}
}
//max between 2 numbers
int max(int a, int b) {
return a > b ? a : b;
}
};
還有就是我努力工作，在樹的表示：
50
/ \
30 70
/\ /\
20 40 60 80
我在哪裏做錯了？
注意：類和結構之間沒有根本的區別。一個結構默認情況下所有成員都是'public'，而一個類有'private'。 – Darhuuk
我也嘗試設置所有的指針，父親，左，右兒子公共，但這根本沒有幫助。 – Asynchronousx
另一個邊節點：這看起來像是從二叉樹中刪除節點的代碼，而不是二叉搜索樹（它需要在刪除內部節點後重新排序節點）。 – Darhuuk