2

Cを使って二分木を配列に変換したいのですが、やってみましたがだめでした。

私の二分木には次の要素が含まれています（予約注文）

4 3 5 10 8 7

しかし、私の配列には（ソート後）が含まれています

4 4 5 7 8 10

どんな助けでも大歓迎です。私の現在のコードは次のようになります。

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

typedef struct tree
{
    int data;
    struct tree *left;
    struct tree *right;
}tree;

int AddToArray(tree *node, int arr[], int i);
tree *CreateNode(int data);
tree *Insert(tree *node, int data);
void PrintPreorder(tree *node);
int count(tree *node);
int compare(const void * a, const void * b);

//---------------------------------------------------------------------------
int main()
{
    int i;
    int size;
    int *arr=NULL;
    tree *root=NULL;

    printf("***TEST PROGRAM***\n");
    root = Insert(root, 4);
    root = Insert(root, 3);
    root = Insert(root, 5);
    root = Insert(root, 10);
    root = Insert (root, 8);
    root = Insert (root, 7);
    size = count(root);

    printf("\n***BINARY TREE (PREORDER)***\n");
    PrintPreorder(root);
    printf("\nThe binary tree countain %d nodes", size);

    printf("\n\n***ARRAY***\n");
    arr = calloc(size, sizeof(int));
    AddToArray(root, arr, 0);
    qsort(arr,size,sizeof(int),compare);

    for (i=0; i<size; i++)
    {
        printf("arr[%d]: %d\n", i, arr[i]);
    }
}
//---------------------------------------------------------------------------

int compare(const void * a, const void * b)
{
   return ( *(int*)a - *(int*)b );
}

int AddToArray(tree *node, int arr[], int i)
{
    if(node == NULL)
        return i;
     arr[i] = node->data;
     i++;
     if(node->left != NULL)
          AddToArray(node->left, arr, i);
     if(node->right != NULL)
          AddToArray(node->right, arr, i);

     arr[i] = node->data;
     i++;
}

tree *CreateNode(int data)
{
    tree *node = (tree *)malloc(sizeof(tree));
    node -> data = data;
    node -> left = node -> right = NULL;
    return node;
}

tree *Insert(tree *node, int data)
{
    if(node==NULL)
    {
        tree *temp;
        temp = CreateNode(data);
        return temp;
    }

    if(data >(node->data))
    {
        node->right = Insert(node->right,data);
    }
    else if(data < (node->data))
    {
        node->left = Insert(node->left,data);
    }

    /* Else there is nothing to do as the data is already in the tree. */
    return node;
}

void PrintPreorder(tree *node)
{
    if(node==NULL)
    {
        return;
    }
    printf("%d ",node->data);
    PrintPreorder(node->left);
    PrintPreorder(node->right);
}

int count(tree *node)
{
    int c = 1;

    if (node == NULL)
        return 0;
    else
    {
        c += count(node->left);
        c += count(node->right);
        return c;
     }
}
4

4 に答える 4

7

AddToArrayメソッドを次のように変更します。

int AddToArray(tree *node, int arr[], int i)
{
     if(node == NULL)
          return i;


     arr[i] = node->data;
     i++;
     if(node->left != NULL)
          i = AddToArray(node->left, arr, i);
     if(node->right != NULL)
          i = AddToArray(node->right, arr, i);

     return i;
}

何が起こっていたかというと、再帰呼び出しがi(次の要素を挿入するはずだったインデックス) の値を変更していましたが、再帰はi実際に再帰を呼び出した反復の値を変更していませんでした。iによって返された値で更新すると、AddToArrayこれが修正されます。

于 2015-04-11T20:17:48.560 に答える
4

i統一的に扱われていない原因。

AddToArrayと置換する

void AddToArray(tree *node, int arr[], int *i){
    if(node == NULL)
        return ;

    arr[*i] = node->data;
    ++*i;
    AddToArray(node->left, arr, i);
    AddToArray(node->right, arr, i);
}

i=0; AddToArray(root, arr, &i);メインで呼び出します。

于 2015-04-11T20:20:42.977 に答える
-1

2 行のコード intAddToArray

 arr[i] = node->data;
 i++;

再帰の各レベルで 2 回表示されます。私の推測では、ツリー内のすべての値が配列に 2 回書き込まれ、互いに重複していると思われます。ただし、ルートは 2 回書き込まれる最終的な値であるため、唯一目立つ値です。

関数の下部にある重複した呼び出しを削除するだけです。

于 2015-04-11T20:14:54.823 に答える