Существует несколько способов решения этой проблемы:
- вставляет большое количество
printf операторов отладки в ваш код и запускает его, проверяя вывод.
- запускать ваш код в отладчике, пошагово и проверяя переменные после каждого шага.
- задайте открытый, неопределенный вопрос здесь, на SO, и попытайтесь заставить нас сделать все работу за вас.
Только две из этих опций сделают вас лучшим разработчиком и уменьшат вероятность раздражать нас в будущем: -)
Что вы должны сначала попытаться сделать, это сузить проблему. Все сообщения о проблемах (здесь, в SO и в реальном мире) должны содержать:
- что вы делали (очень подробно), что вызвало проблему.
- что вы ожидали.
- что на самом деле произошло.
Все, что меньше, это то, что пользователь не выполняет свою сделку.
AVL *rotacao_direita(AVL *no) {
AVL *temp;
temp = no->esq;
no->esq = temp->dir;
if (temp->dir != NULL)
temp->dir->pai = no;
temp->dir = no;
temp->pai = no->pai;
no->pai->dir = temp;
no->pai = temp;
no->fb = 0;
return temp;
}
Хорошо, это ваша функция, и кажется, что вы хотите повернуть вправо через узел no (A ниже). И, согласно вашему комментарию: pai = отец, dir = справа и esq = слева.
X
\
A
/ \
B C
/ \ / \
так что вы получите что-то вроде:
X
\
B
/ \
A
/ \
C
Я вижу одну непосредственную возможную проблему. Вы пытаетесь изменить родительский указатель этого узла, чтобы он указывал на повернутый узел B.
Но вы меняете no->pai->dir, который является правильным узлом X. Что произойдет, если дерево структурировано следующим образом?
X
/ \
A Y
/ \
B C
/ \ / \
Если вы попытаетесь с помощью кода прокрутить узел A этого дерева, вы серьезно рискуете поддеревом Y.
Начиная с поверхностной проверки, я думаю, вы можете начать с изменения:
no->pai->dir = temp;
до:
if (no->pai->esq == no)
no->pai->esq = temp;
else
no->pai->dir = temp;
, который должен изменить правильный указатель в родительском элементе. Имейте в виду, что я не проверил большое количество возможных деревьев, только это:
_____X_____
/ \
__A__ Y
/ \
B C
/ \ / \
D E F G
с обходом в порядке DBEAFCGXY, который, если вы повернете прямо через A с изменением кода, которое я дал, вы получите:
_____X_____
/ \
__B__ Y
/ \
D A
/ \
E C
/ \
F G
выглядит примерно так (по порядку DBEAFGCXY, как и прежде).
Итак, суть, попробуйте это:
AVL *rotacao_direita(AVL *no) {
AVL *temp;
temp = no->esq;
no->esq = temp->dir;
if (temp->dir != NULL)
temp->dir->pai = no;
temp->dir = no;
temp->pai = no->pai;
if (no->pai->esq == no)
no->pai->esq = temp;
else
no->pai->dir = temp;
no->pai = temp;
no->fb = 0;
return temp;
}
и посмотрите, как это будет.
Диого, я оставлю тебе код для игры, чтобы проиллюстрировать, что я имел в виду. Посмотрите на следующий код. Он в основном создает фиктивную структуру и выводит ее, а затем запускает на ней процедуру поворота. Из вывода видно, что результирующее дерево неверно.
Затем он воссоздает исходное дерево и запускает функцию фиксированного поворота, получая то, что я считаю правильным.
Не стесняйтесь использовать функцию dumpAvl в ваших усилиях по отладке, если у вас возникнут дополнительные проблемы. Он выводит относительно красиво отформатированное дерево с узлом, за которым следуют дочерние узлы с отступом (< для левого и > для правого).
#include <stdio.h>
#include <string.h>
typedef struct AVL {
struct AVL *pai, *esq, *dir;
char chr; int fb;
} AVL;
AVL *rotacao_direita(AVL *no) {
AVL *temp;
temp = no->esq;
no->esq = temp->dir;
if (temp->dir != NULL)
temp->dir->pai = no;
temp->dir = no;
temp->pai = no->pai;
no->pai->dir = temp;
no->pai = temp;
no->fb = 0;
return temp;
}
AVL *rotacao_direita_fixed(AVL *no) {
AVL *temp;
temp = no->esq;
no->esq = temp->dir;
if (temp->dir != NULL)
temp->dir->pai = no;
temp->dir = no;
temp->pai = no->pai;
if (no->pai->esq == no)
no->pai->esq = temp;
else
no->pai->dir = temp;
no->pai = temp;
no->fb = 0;
return temp;
}
static AVL *newNode (AVL *pai, char which, AVL *esq, AVL *dir, char chr) {
AVL *node = malloc (sizeof (AVL));
node->pai = pai;
node->esq = esq;
node->dir = dir;
node->chr = chr;
if (pai != NULL) {
if (which == '<') {
node->pai->esq = node;
} else {
node->pai->dir = node;
}
}
return node;
}
static void dumpAvl (char *desc, AVL *node, int spc, char which) {
int i;
if (desc != NULL) {
printf ("%s:\n", desc);
for (i = 0; i < strlen (desc); i++)
printf ("-");
printf ("-\n");
}
for (i = 0; i < spc; i++) printf (" ");
if (node == NULL) {
printf ("%c#\n", which);
} else {
printf ("%c%c\n", which, node->chr);
if ((node->esq != NULL) || (node->dir != NULL)) {
dumpAvl (NULL, node->esq, spc+2, '<');
dumpAvl (NULL, node->dir, spc+2, '>');
}
}
if (spc == 0)
printf ("==================================================\n");
}
static AVL *setupTree (void) {
AVL *root = newNode (NULL, '-', NULL, NULL, 'X');
AVL *node = newNode (root, '<', NULL, NULL, 'A');
node = newNode (root, '>', NULL, NULL, 'Y');
node = newNode (root->esq, '<', NULL, NULL, 'B');
node = newNode (root->esq, '>', NULL, NULL, 'C');
node = newNode (root->esq->esq, '<', NULL, NULL, 'D');
node = newNode (root->esq->esq, '>', NULL, NULL, 'E');
node = newNode (root->esq->dir, '<', NULL, NULL, 'F');
node = newNode (root->esq->dir, '>', NULL, NULL, 'G');
return root;
}
int main (void) {
AVL *root, *junk;
root = setupTree();
dumpAvl ("Original code", root, 0, '-');
junk = rotacao_direita (root->esq);
dumpAvl (NULL, root, 0, '-');
root = setupTree();
dumpAvl ("Fixed code", root, 0, '-');
junk = rotacao_direita_fixed (root->esq);
dumpAvl (NULL, root, 0, '-');
return 0;
}
Когда вы запускаете это, он производит следующее. Вы можете видеть, что исходный код имеет несколько копий некоторых поддеревьев из-за того, что код предполагал, что точка вращения всегда будет справа от своего родителя. Фиксированный код не делает этого предположения.
Original code:
--------------
-X
<A
<B
<D
>E
>C
<F
>G
>Y
==================================================
-X
<A
<E
>C
<F
>G
>B
<D
>A
<E
>C
<F
>G
==================================================
Fixed code:
-----------
-X
<A
<B
<D
>E
>C
<F
>G
>Y
==================================================
-X
<B
<D
>A
<E
>C
<F
>G
>Y
==================================================