tree.cc

/**
 * Tree:
 * - A tree is a hierarchical data structure consisting of nodes connected by edges.
 * - It consists of a root node, which is the topmost node, and zero or more child nodes.
 * - Each node can have an arbitrary number of children, unlike a binary tree which restricts each node to have at most two children.
 * - Trees are used to represent hierarchical relationships such as organizational charts, file systems, and HTML DOM structures.
 */

#include "iostream"
#include "vector"
#include "queue"
#include "stack"

struct Node {
    int item;
    Node *child1;
    Node *child2;
    Node *child3;
    Node *child4;

    explicit Node(int item, Node *child1 = nullptr, Node *child2 = nullptr, Node *child3 = nullptr, Node *child4 = nullptr) :
            item(item), child1(child1), child2(child2), child3(child3), child4(child4) {};
};

class Tree {
private:
    struct Node *m_head = nullptr;
public:
    Tree() : m_head(nullptr) {}

    ~Tree() {
        if (!m_head)
            return;

        std::stack<Node *> queue;
        queue.push(m_head);
        Node *current;

        while (!queue.empty()) {
            current = queue.top();
            queue.pop();

            if (current->child1)
                queue.push(current->child1);
            if (current->child2)
                queue.push(current->child2);
            if (current->child3)
                queue.push(current->child3);
            if (current->child4)
                queue.push(current->child4);

            delete current;
        }
    }

    void insert(int item) {
        Node *new_node = new Node(item);

        if (!m_head) {
            m_head = new_node;
            return;
        }

        std::queue<Node *> queue;
        queue.push(m_head);

        while (!queue.empty()) {
            Node *current = queue.front();
            queue.pop();

            if (!current->child1) {
                current->child1 = new_node;
                return;
            } else if (!current->child2) {
                current->child2 = new_node;
                return;
            } else if (!current->child3) {
                current->child3 = new_node;
                return;
            } else if (!current->child4) {
                current->child4 = new_node;
                return;
            }

            if (current->child1)
                queue.push(current->child1);

            if (current->child2)
                queue.push(current->child2);

            if (current->child3)
                queue.push(current->child3);

            if (current->child4)
                queue.push(current->child4);
        }
    }

    void print() {
        if (!m_head)
            return;

        m_print(m_head);
    }

    bool search(int find) {
        if (!m_head)
            return false;

        if (m_head->item == find)
            return true;

        return m_search(find, m_head);
    }

    void delete_node(int find) {
        if (!m_head)
            return;

        // Use level-order traversal to find the node to delete
        std::queue<Node *> queue;
        queue.push(m_head);
        Node *current = nullptr;
        Node *to_delete = nullptr;

        while (!queue.empty()) {
            current = queue.front();
            queue.pop();

            if (current->item == find) {
                to_delete = current;
                break;
            }

            if (current->child1)
                queue.push(current->child1);
            if (current->child2)
                queue.push(current->child2);
            if (current->child3)
                queue.push(current->child3);
            if (current->child4)
                queue.push(current->child4);
        }

        if (!to_delete) {
            std::cout << "Node with value " << find << " not found in the tree." << std::endl;
            return;
        }

        // Find the deepest node
        queue.push(m_head);
        Node *deepest_node = nullptr;
        while (!queue.empty()) {
            current = queue.front();
            queue.pop();

            if (current != to_delete) {
                deepest_node = current;
            }

            if (current->child1)
                queue.push(current->child1);
            if (current->child2)
                queue.push(current->child2);
            if (current->child3)
                queue.push(current->child3);
            if (current->child4)
                queue.push(current->child4);
        }

        // Swap values between to_delete and deepest_node
        if (deepest_node) {
            to_delete->item = deepest_node->item;

            // Delete deepest_node
            queue.push(m_head);
            while (!queue.empty()) {
                current = queue.front();
                queue.pop();

                if (current->child1 == deepest_node) {
                    delete current->child1;
                    current->child1 = nullptr;
                    break;
                } else if (current->child2 == deepest_node) {
                    delete current->child2;
                    current->child2 = nullptr;
                    break;
                } else if (current->child3 == deepest_node) {
                    delete current->child3;
                    current->child3 = nullptr;
                    break;
                } else if (current->child4 == deepest_node) {
                    delete current->child4;
                    current->child4 = nullptr;
                    break;
                }

                if (current->child1)
                    queue.push(current->child1);
                if (current->child2)
                    queue.push(current->child2);
                if (current->child3)
                    queue.push(current->child3);
                if (current->child4)
                    queue.push(current->child4);
            }
        } else {
            // If deepest_node is nullptr, it means to_delete is the root and the only node
            delete m_head;
            m_head = nullptr;
        }
    }

private:
    void m_print(Node *node) {
        if (!node)
            return;

        std::cout << node->item << ' ';

        m_print(node->child1);
        m_print(node->child2);
        m_print(node->child3);
        m_print(node->child4);
    }

    bool m_search(int find, Node *node) {
        if (!node)
            return false;

        if (find == node->item)
            return true;

        return m_search(find, node->child1) ||
               m_search(find, node->child2) ||
               m_search(find, node->child3) ||
               m_search(find, node->child4);
    }
};

int main() {
    Tree tree;
    std::vector<int> data/* = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21}*/;

    for (int i = 1; i < 100; i++)
        data.push_back(i);

    for (const int d: data)
        tree.insert(d);

    if (tree.search(30))
        std::cout << "Search: find";
    else
        std::cout << "Search: not-find";

    tree.delete_node(99);

    std::cout << std::endl;
    tree.print();
    std::cout << std::endl;

    return 0;
}