Konvertieren von binary tree, array in c

Möchte ich zum konvertieren eines binären Baums in ein array mit C. ich habe versucht, aber war erfolglos.

Mein binäre Baum enthält die folgenden Elemente (Vorbestellen)

4 3 5 10 8 7

aber mein array enthält (nach der Sortierung)

4 4 5 7 8 10

Jegliche Hilfe würde sehr geschätzt werden. Mein Aktueller code so Aussehen:

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

InformationsquelleAutor Isak | 2015-04-11

  1. 4

    Ändern Sie Ihre AddToArray Methode:

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

    Was passierte war, dass Ihre rekursive Aufrufe wurden, ändern Sie den Wert von i (der index, wo Sie sollen, fügen Sie das folgende element), aber die Rekursion nicht ändern Sie den Wert von i in der iteration, die tatsächlich aufgerufen wird, wird die Rekursion. Aktualisierung i durch den Rückgabewert AddToArray dies behebt.

    vielen Dank für eine schnelle Antwort! Sie ersparte mir eine Menge Kopfschmerzen

    InformationsquelleAutor Daniel Kleinstein

  2. 2

    Ursache, dass i ist nicht behandelt in einer einheitlichen Art und Weise.

    AddToArray ersetzen mit 

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

    - und call - i=0; AddToArray(root, arr, &i); am main.

    danke für die Hilfe mich aus!

    InformationsquelleAutor BLUEPIXY

  3. -1

    Die zwei Zeilen code, int AddToArray

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

    Erscheinen zweimal auf jeder Ebene der Rekursion. Meine Vermutung ist, dass jeder Wert in den Baum geschrieben wird das array zweimal und Sie überschneiden sich gegenseitig. aber die Wurzel ist der Letzte Wert geschrieben zu werden, zweimal so es ist nur Auffällig.

    Entfernen Sie einfach die doppelte Aufruf am unteren Rand der Funktion.

    InformationsquelleAutor Stewart Grant

  4. -1
    int TreeToArray (struct node *tree, int *arr, int i)

{
    if (tree == NULL) return i;

    if (tree->left != NULL) i = TreeToArray(tree->left, arr, i);
    arr[i] = tree->Value;
    i++;
    if (tree->right != NULL) i = TreeToArray(tree->right, arr, i);

    return i;
}

    InformationsquelleAutor josef

Schreibe einen Kommentar