我一直试图从树中删除25，但我无法删除它。我试过调试和创建断点，但什么都不起作用。我已经一年多没有这样编码了，事实证明这是非常令人生畏的。
请帮忙！
[输出](https://i.gyazo.com/8e953ebe14d9d33a2a0ffa233ccfacb1.png)
#ifndef BSTREE_H
#define BSTREE_H
#include <iostream>
#include <iomanip>
using namespace std;
// class must be templated
template <class DataType>
class BSTree
{
private:
// You may NOT add any data members
struct node;
typedef node* nodePtr;
struct node
{
DataType element;
nodePtr right;
nodePtr left;
};
int count;
nodePtr root;
// You may add any private member functions here
bool isEmpty() // helper funtion for determining if the tree is empty
{
return root == NULL;
}
void inOrderPrint(nodePtr x, ostream& out)
{
if (root != NULL)
{
inOrderPrint(x->left, out);
out << x->element << " ";
inOrderPrint(x->right, out);
}
}
void preOrderPrint(nodePtr x, ostream& out)
{
if (root != NULL)
{
out << x->element << " ";
preOrderPrint(x->left, out);
preOrderPrint(x->right, out);
}
}
bool search(DataType x) // helper function to check if item is in tree already
{
bool found = false;
if (isEmpty())
{
cout << "Nothing in the Tree!" << std::endl;
return false;
}
nodePtr current;
nodePtr parent;
current = root;
parent = NULL;
while (current != NULL)
{
if (current->element == x)
{
found = true;
break;
}
else
{
//parent = current;
if (x > current->element)
{
current = current->right;
}
else
{
current = current->left;
}
}
}
if (!found)
{
found = false;
}
else
{
found = true;
}
return found;
}
/*
nodePtr findNode(nodePtr x)
{
bool found = false;
if (isEmpty())
{
cout << "Nothing in the Tree!" << std::endl;
return;
}
nodePtr current;
nodePtr parent;
current = root;
parent = NULL;
while (current != NULL)
{
if (current->element == x->element)
{
found = true;
return x;
break;
}
else
{
parent = current;
if (x->element > current->element)
{
current = current->right;
}
else
{
current = current->left;
}
}
}
if (!found)
{
found = false;
return;
}
else
{
found = true;
}
return x;
}
*/
void destroyTree(nodePtr x)
{
if (x != NULL)
{
destroyTree(x->left);
destroyTree(x->right);
delete x;
}
}
// This method is given – it is called by printTree
void printTreeHelper(int depth, nodePtr cur) const
{
const int spacing = 4;
if (cur != NULL)
{
if (depth == 0)
cout << cur->element;
else
cout << setw(spacing * depth) << " " << cur->element;
cout << endl;
printTreeHelper(depth + 1, cur->right);
printTreeHelper(depth + 1, cur->left);
}
else
cout << setw(spacing * depth) << " " << "****" << endl;
}
void copyTreeHelper(nodePtr x)
{
if (x != NULL)
{
insert(x->element);
copyTreeHelper(x->left);
copyTreeHelper(x->right);
}
}
nodePtr minNodeFinder(nodePtr min)
{
nodePtr curr = min;
while ((curr != NULL) && (curr->left != NULL))
{
curr = curr->left;
}
return curr;
}
public:
// Default constructor
BSTree()
{
root = NULL;
}
// Copy constructor
BSTree(const BSTree<DataType>& copyTree)
{
root = NULL;
copyTreeHelper(copyTree.root);
}
// Equal overload
const BSTree& operator =(const BSTree& rhs)
{
if (this == &rhs)
{
return *this;
}
else
{
copyTreeHelper(rhs.root);
deleteTree();
return *this;
}
}
// Destructor
~BSTree()
{
deleteTree();
}
// Inserts element into the tree
// If value is already in the tree do NOt add it
// a second time
void insert(DataType x)
{
if (search(x))
{
cout << "item already in tree" << std::endl;
}
else
{
nodePtr temp = new node();
nodePtr parent;
temp->element = x;
temp->left = NULL;
temp->right = NULL;
parent = NULL;
if (isEmpty())
{
root = temp;
}
else
{
nodePtr current;
current = root;
while (current)
{
parent = current;
if (temp->element > current->element)
{
current = current->right;
}
else
{
current = current->left;
}
}
if (temp->element < parent->element)
{
parent->left = temp;
}
else
{
parent->right = temp;
}
}
}
}
//Print the tree as a tree
// This (and its helper function) is given to you
// See sample output and understand how the tree is displayed
// because it can help when testing the code
bool printTree() const
{
if (root == NULL)
return false;
else
{
printTreeHelper(0, root);
return true;
}
}
// Prints tree in order to the screen
// call printInOrder with cout passed in
// This function is done for you
void printInOrder()
{
printInOrder(cout);
}
// Prints the tree in order to
// the ostream passed into it
void printInOrder(ostream& out)
{
inOrderPrint(root, out);
out << std::endl;
}
// Prints tree in preorder to the screen
// call printPreOrder with cout passed in
// This function is done for you
void printPreOrder()
{
printPreOrder(cout);
}
// Prints the tree in preorder to
// the ostream passed into it
void printPreOrder(ostream& out)
{
preOrderPrint(root, out);
out << std::endl;
}
// Deletes the item passed in from the tree
// It returns a true if it finds it and deletes it, otherwise
// It returns a false
bool deleteNode(DataType x)
{
if (!search(x))
{
cout << "Item not found" << std::endl;
return false;
}
nodePtr current;
nodePtr parent;
current = root;
parent = NULL;
//Node is a single node with one child
if((current->left == NULL && current->right != NULL) ||
(current->left != NULL && current->right == NULL))
{
if(current->left == NULL && current->right != NULL) // right child is present
{
if(parent->left == current)
{
parent->left = current->right;
delete current;
}
else
{
parent->right = current->right;
delete current;
}
}
else // left child is present
{
if (parent->left == current)
{
parent->left = current->left;
delete current;
}
else
{
parent->right = current->left;
delete current;
}
}
return true;
}
// node is a leaf node
if (current->left == NULL && current->right == NULL)
{
if(parent == NULL)
{
delete current;
}
else
{
if(parent->left == current)
{
parent->left = NULL;
}
else
{
parent->right = NULL;
}
delete current;
return true;
}
}
// node has two children i.e parent node
if (current->left != NULL && current->right != NULL)
{
nodePtr checker;
checker = current->right;
if ((checker->left == NULL) && (current->right == NULL))
{
current = checker;
delete current;
current->right = NULL;
}
else // right child has children
{
//nodes right child has a left child
if ((current->right)->left != NULL)
{
nodePtr left_current;
nodePtr left_current_parent;
left_current_parent = current->right;
left_current = (current->right)->left;
while (left_current->left != NULL)
{
left_current_parent = left_current;
left_current = left_current->left;
}
current->element = left_current->element;
delete left_current;
left_current_parent->left = NULL;
}
else
{
nodePtr temp;
temp = current->right;
current->element = temp->element;
current->right = temp->right;
delete temp;
}
}
}
return true;
}
// Deletes the item passed in from the tree
// It also passes back the item to the calling function
// It returns a true if it finds it and deletes it, otherwise
// It returns a false
bool deleteNodePassBackData(DataType x, DataType& temp)
{
if (search(x))
{
nodePtr itemToDelete = findNode(x);
temp = itemToDelete->element;
deleteNode(x);
return true;
}
else
{
return false;
}
}
// Deletes the whole tree
void deleteTree()
{
destroyTree(root);
}
};
#endif
BSTree<int> t1;
t1.insert(50);
t1.insert(75);
t1.insert(25);
t1.insert(22);
t1.insert(5);
t1.insert(85);
t1.insert(95);
t1.insert(82);
t1.insert(76);
t1.printTree();
BSTree<int> t2(t1);
t2.deleteNode(25);
t2.deleteNode(75);
t2.deleteNode(50);
cout << "After copy constructor and deletes" << endl;
cout << "T1" << endl;
t1.printTree();
cout << "T2" << endl;
t2.printTree();
首先，您应该始终发布完整的代码供其他人调试。如果我不能运行你的代码，我到底该怎么调试它呢？
但除此之外，您的代码中的deleteNode(DataType x)存在严重问题current永远不要遍历树deleteNode()函数将始终删除树的根，如果项存在于树中
您应该像在deleteNode()函数中的search()函数中那样遍历树。
顺便问一下，search()中的以下代码有什么意义？
if (!found)
{
found = false;
}
else
{
found = true;
}