代码在这里: http: //pastebin.com/VAdc67bE
函数 rotacao_esquerda 存在问题。这是 AVL 树的旋转。
如何解决?
有多种方法可以解决此问题:
printf
在整个代码中插入大量调试语句并运行它,检查输出。这些选项中只有两个能让您成为更好的开发人员,并且将来不太可能惹恼我们:-)
你应该首先尝试做的是缩小问题的范围。所有问题报告(此处为 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;
}
看看情况如何。
Diogo,我会给你一些代码来说明我的意思。查看以下代码。它基本上创建了一个虚拟结构并将其转储出来,然后在其上运行您的旋转例程。您可以从输出中看到结果树是错误的。
然后它重新创建原始树并运行固定旋转功能,产生我认为正确的结果。
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
==================================================