2

我正在为我的作业实现一个 avl 树。

#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

struct TreeNode {
  char *item;
  struct TreeNode *left;
  struct TreeNode *right;
  signed char balance;
};

typedef struct TreeNode Node;

void _print_avl (Node *, int , const char *);

Node * get_new_node (char *);
int avl_insert(Node *, char *);
void print_avl (Node *);
void avl_swr(Node*);

int main (int argc, char *argv[])
{
  Node *root = get_new_node("thura");
  avl_insert(root, "thur2");
  print_avl(root);

  avl_insert(root, "thur1");

  return 0;
}

int avl_insert(Node *root, char *item)
{
  assert(root);

  if( strcmp(item, root->item) < 0) {

        if(!root->left) {
          root->left = get_new_node(item);
          if(--(root->balance)) return 1;
          return 0;
        } else  {
          if(avl_insert(root->left, item)) {
                if( root->balance-- < 0) {
                  avl_swr(root); //Rotate the node right.
                  print_avl(root); //Here, the tree is corrupted.
                  return 0;
                }
                return 1;
          }
        }
  } else {
        if(!root->right) {
          root->right = get_new_node(item);
          if(++(root->balance)) return 1;
          return 0;
        }
        else {
          if(avl_insert(root->right, item)) {
                root->balance++;
                return 1;
          }
        }
  }
  return 0;
}

void avl_swr(Node* root)
{
  Node *node = root;
  root = node->left;

  node->left = NULL;
  node->balance = 0;

  root->right = node;
  root->balance++;

  print_avl(root); // It is working fine here.
}

Node * get_new_node (char *item) {
  Node * node = (Node *)malloc(sizeof(Node));
  node->item  = item;
  node->left  = NULL;
  node->right = NULL;
  node->balance = 0;
  return node;
}

void print_avl (Node *node)
{
  _print_avl(node, 0, "\t\t");
}

void _print_avl (Node *node, int depth, const char *delim)
{
  if(!node)
        return;
  int i = 0;
  while(i++ < depth) printf("%s", delim);
  printf("--> %s:%d\n", node->item, node->balance);

  depth++;

  if(node->left)
        _print_avl (node->left, depth, delim);

  if(node->right)
        _print_avl (node->right, depth, delim);
}

问题是当我旋转树时，使用avl_swr()，按照print_avl()旋转成功，但是当函数返回调用者时，树损坏了。有任何想法吗？

4

4 回答 4

5

avl_swr() 的问题与函数签名有关：void avl_swr(Node* root)和分配： root = node->left;

当函数返回时，根指针没有被更新（只有函数内的本地副本被更新）。签名应该是：void avl_swr(Node** root)为了得到想要的结果。

于 2009-10-13T13:07:11.257 回答
1

指针的副本被更新。您需要在旋转函数中传递一个指向指针的指针。

于 2009-10-13T13:07:32.380 回答
1

这是因为 avl_insert 中的根变量在 avl_swr 中没有改变。当您将它传递给 avl_swr 时，会生成指针的副本。你改变这个指针。

更改调用root = avl_swr(...)并让 avl_swr 返回根。

于 2009-10-13T13:10:28.280 回答
0

不是 100% 肯定，但我确实看到了一个问题。在 avl_swr() 中，您将根更改为左子树。因此，当您在 avl_swr() 中打印出来时，您将拥有 root = "thur2"。但是当你返回 avl_insert() 时，root 没有改变，仍然指向“thura”，它现在没有孩子。因此，当您打印该根目录时，它不会显示任何子项。也许这就是你所说的腐败？解决方案显然是改变avl_insert()中的“根”。您可以通过让 avl_swr 返回新的根值来执行此操作，或者将参数从“Node* root”更改为“Node** root”，以便将 avl_swr 中的更改“传递回”给 avl_insert

于 2009-10-13T13:38:59.270 回答