Блог

Главная - Вопросы по программированию - Поиск и удаление неправильных узлов по британскому летнему времени в C

Поиск и удаление неправильных узлов по британскому летнему времени в C

#c #algorithm #pointers #data-structures #binary-search-tree

#c #алгоритм #указатели #структуры данных #двоичный поиск-дерево

Вопрос:

У меня есть проблема C, в которой мне нужно проверить, является ли данное дерево бинарным деревом поиска или нет, а затем найти, какой узел неверен, и удалить его (из определения проблемы это всегда будет только один неправильный узел). Например:

        10
       |
       |
 9          12
 |          |
 |          |
7  3       11  14

В этом дереве элемент 3 является некорректным и должен быть удален. В случае данного дерева-это уже по британскому летнему времени, алгоритм не должен ничего делать. Я пытаюсь адаптировать решение из CodeForGeeks который проверяет, если дерево находится по британскому летнему времени или не вместо возвращающий логическое значение, возвращает указатель на узел, который является неправильным, но это не работает хорошо. Вот метод, который я придумал:

 NODE* verifyBinaryTree(NODE* root, NO** previous){
    if(node != NULL){
        NODE* left= verifyBinaryTree(root->left, previous);
        if(left != NULL){
            return left;
        }

        if(*previous amp;amp; root->data <= (*previous)->data) return root;

        *previous = root;

        return(verifyBinaryTree(root->right, previous));
    }
    return NULL;
}

Я бы с удовольствием, если кто-то может помочь мне найти правильный логику этой проблемы.

Комментарии:

1. Я думаю, что функция нуждается в a maxValue и a minValue для проверки. Каждый раз, когда код соответствует левой ветви, которая maxValue нуждается в обновлении. Следующая за правой ветвью обновляет minValue .

Ответ №1:

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

Вы можете сделать это в порядке обхода и после их последовательного сохранения в структуре данных (возможно, в массиве) проверить , не расположены ли соседние элементы в порядке возрастания. Если вы обнаружите такие элементы , вам необходимо удалить их .

Комментарии:

1. Существует проблема с этим подходом. Рассмотрим дерево из оригинального поста, в результате связный список из симметричного поперечного будут: 7 9 3 10 11 12 14, было бы легко определить 3 как неправильный узел. Но сейчас думаю, что в исходном дереве, но вместо 3 как неправильный элемент, в 7 было бы не так (скажем, 7, будет 16). Приведенный список ссылок будет: 16 9 15 20 22 24 26. Как я могу определить, неправильный элемент 16, а не 9, как в этом случае?

2. Я думаю, что это зависит от вашего определения того, что является неправильным . Вы никогда не определяется в вашем посте как неправильный узел, чтобы быть просто по его родителей : ) можно рассматривать любой из них, чтобы быть неправильным

Метки: