235150301111015-Tugas8-GraphBFSnDFS

#include <iostream>
using namespace std;

struct Node {
    int key;
    struct Node *left, *right;
};


Node *newNode(int item) {
    Node *temp = new Node();
    temp->key = item;
    temp->left = temp->right = nullptr;
    return temp;
}


void inorder(Node *root) {
    if (root != nullptr) {
        inorder(root->left);
        cout << root->key << " ";
        inorder(root->right);
    }
}


void reverseInorder(Node *root) {
    if (root != nullptr) {
        reverseInorder(root->right);
        cout << root->key << " ";
        reverseInorder(root->left);
    }
}


Node* insert(Node* node, int key) {
    if (node == nullptr) return newNode(key);
    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);


    return node;
}

Node* minValueNode(Node* node) {
    Node* current = node;
    while (current && current->left != nullptr)
        current = current->left;

    return current;
}

Node* deleteNode(Node* root, int key) {
    if (root == nullptr) return root;

    if (key < root->key)
        root->left = deleteNode(root->left, key);
    else if (key > root->key)
        root->right = deleteNode(root->right, key);

    else {
        if (root->left == nullptr) {
            Node *temp = root->right;
            delete root;
            return temp;
        } else if (root->right == nullptr) {
            Node *temp = root->left;
            delete root;
            return temp;
        }

        Node* temp = minValueNode(root->right);
        root->key = temp->key;
        root->right = deleteNode(root->right, temp->key);
    }
    return root;
}

int main() {
    Node *root = nullptr;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);

    cout << "Mencetak data yang ada: " << endl;
    inorder(root);


    root = deleteNode(root, 20);
    root = deleteNode(root, 30);
    root = deleteNode(root, 40);
    root = deleteNode(root, 50);
    root = deleteNode(root, 60);
    root = deleteNode(root, 70);
    root = deleteNode(root, 80);

    cout << "\nData Setelah Menghapus semua node:" << endl;
    inorder(root);


    root = insert(root, 2);
    root = insert(root, 7);
    root = insert(root, 1);
    root = insert(root, 89);
    root = insert(root, 5);
    root = insert(root, 23);
    root = insert(root, 1);
    cout << "\nData Setelah Menambahkan node 2, 7, 1, 89, 5, 23, 1:" << endl;
    inorder(root);


    root = deleteNode(root, 89);
    root = deleteNode(root, 5);
    root = deleteNode(root, 23);

    cout << "\nData Setelah Menghapus nilai 89, 5, 23:" << endl;
    inorder(root);

    cout << "\nData setelah menghapus node terkecil right subtree:" << endl;
    inorder(root);

    cout << "\nTraversal dari nilai terbesar ke terkecil:" << endl;
    reverseInorder(root);

    return 0;
}