二叉搜索树类的递归删除函数

问题描述 投票:0回答:0

我正在尝试使用节点和树的类为二叉搜索树实现递归删除功能,该功能根据节点的数据值删除节点。我有一个有效的添加和顺序遍历成员函数来测试删除。我的删除在大多数情况下都有效。但是,当我尝试删除根节点或有一个子树为空的树(也就是根只有 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;
}

c++ recursion binary-search-tree
© www.soinside.com 2019 - 2024. All rights reserved.