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% 確実ではありませんが、問題が 1 つあります。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 に答える