我正在尝试使用节点和树的类为二叉搜索树实现递归删除功能,该功能根据节点的数据值删除节点。我有一个有效的添加和顺序遍历成员函数来测试删除。我的删除在大多数情况下都有效。但是,当我尝试删除根节点或有一个子树为空的树(也就是根只有 1 个子节点)或当我只有 1 个节点并尝试删除时,它不起作用并抛出异常那个(根)节点(又名根没有孩子)。当根有 2 个孩子时它有效。
当我调试它时,在某些情况下,指向根节点的指针似乎没有变为 null。
这些是我的课程
class TreeNode
{
friend class BinaryTree;
public:
TreeNode(int theData);
private:
TreeNode* leftPtr;
int data;
TreeNode* rightPtr;
};
class BinaryTree
{
public:
BinaryTree(); // A tree constructor and creates an empty tree
~BinaryTree();
void add(int); //Note : no Duplicates
void delete_value(int theInt);
void in_order();
protected:
void DestroyRecursive(TreeNode* node);
void add(TreeNode* toAdd, TreeNode* attachHere);
void in_order(TreeNode* subtreeRoot);
TreeNode* delete_value_recur(TreeNode* root, int data);
TreeNode* find_min(TreeNode* subtreeRoot);
private:
TreeNode* root;
};
TreeNode* BinaryTree::delete_value_recur(TreeNode* subtreeRoot, int data) // Returns the same node that's being deleted, which is most of the time is nullptr
{ // search for the node
if (subtreeRoot == nullptr) // Tree is empty.
return subtreeRoot;
else if (data < subtreeRoot->data) // If the data to be deleted is smaller than the root's data, then it lies in left subtree
subtreeRoot->leftPtr = delete_value_recur(subtreeRoot->leftPtr, data);
else if (data > subtreeRoot->data) // If the data to be deleted is bigger than the root's data, then it lies in right subtree
subtreeRoot->rightPtr = delete_value_recur(subtreeRoot->rightPtr, data);
// if data is same as root's data, then node with value has been found and now delete
else {
// Case 1: No child
if (subtreeRoot->leftPtr == nullptr && subtreeRoot->rightPtr == nullptr) {
TreeNode* temp = subtreeRoot;
subtreeRoot = nullptr; //root = nullptr;
delete temp;
}
//Case 2: One child
else if (subtreeRoot->leftPtr == nullptr && subtreeRoot->rightPtr != nullptr) { // one right child
TreeNode* temp = subtreeRoot;
subtreeRoot = subtreeRoot->rightPtr;
delete temp;
}
else if (subtreeRoot->rightPtr == nullptr && subtreeRoot->leftPtr != nullptr) { // one left child
TreeNode* temp = subtreeRoot;
subtreeRoot = subtreeRoot->leftPtr;
delete temp;
}
// case 3: 2 children find the min node of the right subtree
else {
TreeNode* temp = find_min(subtreeRoot->rightPtr);
subtreeRoot->data = temp->data;
subtreeRoot->rightPtr = delete_value_recur(subtreeRoot->rightPtr, temp->data);
}
}
return subtreeRoot;
}
TreeNode* BinaryTree::find_min(TreeNode* subtreeRoot)
{
{
while (subtreeRoot->leftPtr != nullptr)
subtreeRoot = subtreeRoot->leftPtr;
return subtreeRoot;
}
}
void BinaryTree::in_order()
{
if (root == nullptr)
cout << "The Tree is Empty" << endl;
else
in_order(root);
}
void BinaryTree::in_order(TreeNode* subtreeRoot)
{
if (subtreeRoot != nullptr) // base case
{
in_order(subtreeRoot->leftPtr);
cout << " The tree data is " << subtreeRoot->data << endl; //’visit’ the subtree root, then …
in_order(subtreeRoot->rightPtr);
}
}
void BinaryTree::add(TreeNode* toAdd, TreeNode* attachHere)
{
//we will attach to either right or left sub-tree of this node
//if num less than the num at location, go left
if (toAdd->data < attachHere->data)
if (attachHere->leftPtr == nullptr)
attachHere->leftPtr = toAdd;
else
add(toAdd, attachHere->leftPtr); //recursive call
else //go right
if (attachHere->rightPtr == nullptr)
attachHere->rightPtr = toAdd;
else
add(toAdd, attachHere->rightPtr); //recursive call
}
int main()
{
BinaryTree b;
b.add(6);
b.add(4);
b.add(2);
b.delete_value(6);
b.in_order();
return 0;
}