Преобразование двоичного дерева в массив в c

Question

Я хочу преобразовать двоичное дерево в массив с помощью C. Я пробовал, но не увенчался успехом.

Моя бинарное дерево содержит следующие элементы (PREORDER)

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

Answer 1

Изменить метод 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 (индекс, в котором вы должны были вставить следующий элемент), но ваш рекурсии WASN 't изменяя значение i в итерации, которая фактически вызывала рекурсию. Обновление i со значением, возвращаемым AddToArray, исправляет это.

Answer 2

две строки кода междунар AddToArray

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

появляются дважды на каждом уровне рекурсии. Я предполагаю, что каждое значение в дереве записывается в массив дважды, и они пересекают друг друга. но корень - это окончательное значение, которое должно быть записано дважды, поэтому оно является единственным заметным.

Просто удалите дубликат вызова в нижней части функции.

Answer 3

Причина, по которой 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); на главном.

Answer 4

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