C语言 在c中将二叉树转换为数组
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/29582431/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Convert binary tree to array in c
提问by Isak
I want to convert a binary tree to an array using C. I tried but was unsuccessful.
我想使用 C 将二叉树转换为数组。我尝试过但没有成功。
My binary tree contains the following elements (preorder)
我的二叉树包含以下元素（预购）
4 3 5 10 8 7
but my array contains (after sorting)
但我的数组包含（排序后）
4 4 5 7 8 10
Any help would be greatly appreciated. My current code look like this:
任何帮助将不胜感激。我当前的代码如下所示：
#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;
}
}
回答by Daniel Kleinstein
Change your AddToArraymethod to this:
将您的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;
}
What was happening was that your recursive calls were changing the value of i(the index where you were supposed to insert the following element), but your recursion wasn't changing the value of iin the iteration that actually invoked the recursion. Updating iwith the value returned by AddToArrayfixes this.
发生的事情是您的递归调用正在更改i（您应该插入以下元素的索引）的值，但您的递归并没有更改i实际调用递归的迭代中的值。i用返回的值更新AddToArray修复了这个问题。
回答by BLUEPIXY
Cause that iis not treated in a unified manner.
i未统一处理的原因。
AddToArrayreplace with
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);
}
and call i=0; AddToArray(root, arr, &i);at main.
并i=0; AddToArray(root, arr, &i);在 main 处调用。
回答by Stewart Grant
The two lines of code int AddToArray
两行代码int AddToArray
arr[i] = node->data;
i++;
Are appearing twice at each level of recursion. My guess is that every value in the tree is being written to the array twice and they over lap each other. but the root is the final value to be written twice so it is the only noticeable one.
在每个递归级别出现两次。我的猜测是树中的每个值都被写入数组两次，并且它们彼此重叠。但是根是要写入两次的最终值，因此它是唯一值得注意的值。
Just remove the duplicate call at the bottom of the function.
只需删除函数底部的重复调用即可。
回答by josef
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;
}
