Удаление узла из двоичного дерева поиска ошибка? - PullRequest
Новая
       38

Удаление узла из двоичного дерева поиска ошибка?

0 голосов
/ 23 декабря 2018

Я пытаюсь выполнить задачу leetcode по удалению узла в BST.Мой удаляет его, но возвращает испорченное дерево, не знаю почему. 

struct TreeNode* deleteNode(struct TreeNode* root, int key) {

    if (root == NULL){return root;}
    else if(root->val == key){return root;}
    if(key < root->right->val){
        if( key == root->left->val){
            root->left = root->left->left;
        }
        else{
            deleteNode(root->left, key);
        }
    }
    else if( key < root->left->val){
        if ( key == root->right->val){
            root->right = root->right->right;
        }else{
            deleteNode(root->right, key);
        }
    }

    return root;
    }

1 Ответ

0 голосов
/ 23 декабря 2018

Вам нужно исправить некоторые вещи и обратиться к случаю, когда узел, который вы пытаетесь удалить, является корневым.

Кроме того, необходимо исправить способ обновления дерева при удалении узла.Возможно, вы захотите рассмотреть функцию, которая возвращает узел минимального значения в правом поддереве.Прототип может выглядеть примерно так: Node *minValueNode(Node *root).

Затем, когда вы удаляете узел, имеющий два дочерних узла, вы заменяете его узлом минимального значения в его правом поддереве.

Рассмотрим эту реализацию, которая работает с узлами, которые хранят строки: 

TreeNode *removeWord(TreeNode *tree, char* word){
    if(tree == NULL) return tree;

    if(strcmp(tree->word, word) > 0 ){
        tree->left = removeWord(tree->left, word);
    }
    else if(strcmp(tree->word, word) < 0){
        tree->right = removeWord(tree->right, word);
    }

    else{
        if(tree->left == NULL){
            TreeNode *temp = tree->right;
            free(tree);
            return temp;
        }
        else if(tree->right == NULL){
            TreeNode *temp = tree->left;
            free(tree);
            return temp;
        }

        /* Smallest Node in the right subtree */
        TreeNode *temp = minValueNode(tree->right);

        tree->word = temp->word;
        tree->pos = temp->pos;
        tree->right = removeWord(tree->right, temp->word);
    }
    return tree;
}
...