Trying to understand my mistakes – Beginner needs advice on how to make this dsi work

  Kiến thức lập trình

I have successfully completed 9 data structure exercises in C++ but the binary search tree dsi is stumping me. After it is compiled, everything looks fine, however when i try to execute this program, it crashed.

I would really appreciate some mentorship as to where my code goes wrong and how I might fix it.

#ifndef BINARYSEARCHTREE_HPP
#define BINARYSEARCHTREE_HPP

#include <iostream>

class BSTNode {
public:
    int data;
    BSTNode* left;
    BSTNode* right;
    BSTNode* parent;

    BSTNode(int value) {
        data = value;
        left = nullptr;
        right = nullptr;
        parent = nullptr;
    }

    ~BSTNode() {
        delete left;
        delete right;
    }
};

class BinarySearchTree {
private:
    BSTNode* root;

    BSTNode* maximum(BSTNode* node) {
        if(node == nullptr) {
            return nullptr;
        }
        while (node->right != nullptr) {
            node = node->right;
        }
        return node;
    }

    void replaceSubtree(BSTNode* oldSubtree, BSTNode* newSubtree) {
        if (oldSubtree->parent == nullptr) {
            root = newSubtree;
        } else if (oldSubtree == oldSubtree->parent->left) {
            oldSubtree->parent->left = newSubtree;
        } else {
            oldSubtree->parent->right = newSubtree;
        }
        if (newSubtree != nullptr) {
            newSubtree->parent = oldSubtree->parent;
        }
    }

    void print(BSTNode* node) {
        if (node != nullptr) {
            print(node->left);
            std::cout << node->data << " ";
            print(node->right);
        }
    }

public:
    BinarySearchTree() {
        root = nullptr;
    }

    BSTNode* predecessor(BSTNode* node) {
        if (node->left != nullptr) {
            return maximum(node->left);
        }
        BSTNode* y = node->parent;
        while (y != nullptr && node == y->left) {
            node = y;
            y = y->parent;
        }
        return y;
    }

    void insert(int value) {
        BSTNode* node = new BSTNode(value);
        BSTNode* y = nullptr;
        BSTNode* x = root;

        while (x != nullptr) {
            y = x;
            if (node->data < x->data) {
                x = x->left;
            } else {
                x = x->right;
            }
        }

        node->parent = y;
        if (y == nullptr) {
            root = node;
        } else if (node->data < y->data) {
            y->left = node;
        } else {
            y->right = node;
        }
    }

    BSTNode* searchNode(int val) {
        BSTNode* x = root;
        while (x != nullptr && val != x->data) {
            if (val < x->data) {
                x = x->left;
            } else {
                x = x->right;
            }
        }
        return x;
    }

    bool search(int val) {
        return searchNode(val) != nullptr;
    }

    void remove(int value) {
    BSTNode* node = searchNode(value);
    if (node == nullptr) {
        return;
    }
    if (node->left != nullptr) {
        replaceSubtree(node, node->right);
    } else if (node->right != nullptr) {
        replaceSubtree(node, node->left);
    } else {
        BSTNode* y = maximum(node->left);
        if (y != nullptr && y->parent != node) {
            replaceSubtree(y, y->left);
            if (y->left != nullptr) {
                y->left->parent = y;
            }
        }
        replaceSubtree(node, y);
        if (y->right != nullptr) {
            y->right->parent = y;
        }
    }
    node->left = nullptr; // Set node's left and right pointers to null before deletion
    node->right = nullptr;
    delete node;
}

    void print() {
        print(root);
        std::cout << std::endl;
    }
};

#endif

New contributor

Michael Wells is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

LEAVE A COMMENT