-1

代码在这里: http: //pastebin.com/VAdc67bE

函数 rotacao_esquerda 存在问题。这是 AVL 树的旋转。

如何解决?

4

1 回答 1

2

有多种方法可以解决此问题:

  • 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;
}

看看情况如何。


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
==================================================
于 2010-10-03T04:10:05.620 回答