Как удалить узел из дерева двоичного поиска в C ++ - PullRequest
Новая
       63

Как удалить узел из дерева двоичного поиска в C ++

0 голосов
/ 25 апреля 2020 
#include <iostream>
using namespace std;

class Node{
    public:
     int data;
     Node* left, *right;
     Node(int n){
         data = n;
         left = right = NULL;
     }
};  

void PrintInorder(Node* node){
    // ?? Function to print node inorderly which is left, root, right
    if(node == NULL){
        return;
    }else{
        //?? Print Left first
        PrintInorder(node->left);

        //?? Print the data of the node
        cout << node->data << " ";

        //?? Finally print the right of the node
        PrintInorder(node->right);
    }
}

Node* insert(Node* node, int key){
    if (node == NULL) return new Node(key);

    if(key < node->data){
        node->left = insert(node->left, key);
    }else if(key > node->data){
        node->right = insert(node->right, key);
    }

    return node;
}

Node* minValueNode(Node* node){
    Node* current = node;

    while (current && current->left !=NULL)
        current = current->left;

    return current;
}

Node* deleteNode(Node* node, int key){
    if (node == NULL) return node;

    if (key < node->data)
        deleteNode(node->left, key);
    else if (key > node->data)
        deleteNode(node->right, key);
    else{
        // If node only has one child
        if (node->left == NULL){
            Node* temp = node->right;
            free(node);
            return temp;
        }else if (node->right == NULL){
            Node* temp = node->left;
            free(node);
            return temp;
        } 

        // If node has two child. Get Smallest Inorder Successor
        Node* temp = minValueNode(node->right);

        // Copy the smallest successo's content to this node
        node->data = temp->data;

        // Delete the smallest successor's node
        deleteNode(node->right, temp->data);
    }
    return node;
}

int main(){
    Node* head = NULL;
    head = new Node(5);

    int arr[3] = {7,6,9};
    for (int i = 0; i < 3; i++)
    {
        insert(head, arr[i]);
    }

    cout << "Print Inorderly : ";
    PrintInorder(head);
    cout << endl;

    deleteNode(head, 7);
    cout << "Print Inorderly : ";
    PrintInorder(head);
    cout << endl;
}

Мне не удалось удалить 7 из этого BST-узла, когда я использовал free (node) в функции deleteNode. Это результат функции free (node). 

Print Inorderly : 5 6 7 9

Когда я вызывал функцию deleteNode (head, 7), он не будет запускать приведенный ниже код. Но когда я вызвал функцию deleteNode без свободной функции, она может удалить 7, но все равно дважды вызывала преемника. Это результат без свободной функции. 

Print Inorderly : 5 6 7 9 
Print Inorderly : 5 6 9 9

Как удалить узел с ключом 7, чтобы его можно было напечатать 5 6 9.

...