使用C语言将数组转换为二叉树？

Question

我将尝试使用C语言将整数数组转换为二叉树。

例如，对于一个数组a[10]={5,2,1,6,7,3,4}，它的二叉树应该像这样：

    5    
   / \  
  2   1    
 /\   /\  
6  7  3  4    

我尝试使用以下代码进行转换

typedef struct btree    
{        
    int value;    
    struct btree *left;    
    struct btree *right;    
}Btree;    
void insert(Btree *t,int *a,int index,int n)    
{    
    t=(Btree *)malloc(sizeof(Btree));    
    if(index<n)    
    {    
        t->value=a[index];    
        insert(t->left,a,2*index,n);    
        insert(t->right,a,2*index+1,n);    
    }    
}    
int main(void) {    
    int a[100],i;    
    Btree *t;    
    for(i=0;i<10;i++)    
        scanf("%d",&a[i]);    
    insert(t,a,0,i+1);    
    return 0;    
}  

有人能帮我解决这个问题吗？

这个问题是关于IT技术的。

- vineeth suhas

Answer 1

这里有几个问题：

- 在 `insert` 的条件块中应该放置节点分配，否则会为 null 节点分配内存。 - 应该在节点为叶子节点且没有子节点时将 `left` 和 `right` 指针初始化为 `NULL`。 - 最重要的是，您对树所做的更改将会丢失。指针变量仅限于当前实例的 `insert`（您递归调用它），不会传输到较早的实例或到 `main`。传递一个指向节点指针的指针。 - 考虑在整个过程中使用基于零的索引；它们在 C 中是标准的。

因此，下面是它的工作方式：

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

typedef struct btree {
    int value;
    struct btree *left;
    struct btree *right;
} Btree;

void insert(Btree **t, int *a, int index, int n)
{
    if (index < n) {
        *t = malloc(sizeof(**t));
        
        (*t)->value = a[index];
        (*t)->left = NULL;
        (*t)->right = NULL;
        
        insert(&(*t)->left, a, 2 * index + 1, n);
        insert(&(*t)->right, a, 2 * index + 2, n);
    }
}

void print(Btree *t, int level)
{
    if (t) {
        print(t->left, level + 1);
        printf("%*s->%d\n", 4*level, "", t->value);
        print(t->right, level + 1);
    }
}

int main(void)
{
    int a[] = {5, 2, 1, 6, 7, 3, 4};
    Btree *t;

    insert(&t, a, 0, 7);
    print(t, 0);

    // TODO: Clean up memory used by nodes

    return 0;
}

我已经用一个硬编码的数组替换了scanf的内容。代码没有清理分配的内存，这是真的应该做的。

- M Oehm

Answer 2

也许你只需要输出数组以匹配树形视图。在这种情况下，您不需要使用节点创建二叉树，而是使用适当索引的数组即可。

如果当前索引为 X，则子节点变为 2X+1 和 2X+2。也许这正是您想要的。

看一个例子：

#include <stdio.h>

int main()
{

    int a[7]={5,2,1,6,7,3,4}; // <= A hard coded array

    int n=0;

    // Getting the unsorted Tree output. 
    //  sizeof(a)/sizeof(int) - used to get the array length

    while(n < (sizeof(a)/sizeof(int))/2){
        printf("Parent: %d\n",a[n]);  // <= parent node
        printf("Left Child: %d\n",a[2*n +1]); // <= left Child
        printf("Right Child: %d\n",a[2*n +2]); // <= right Child

        printf("\n");
        n++;
    }

    return 0;
}

输出：

Parent: 5                                                                                                                                                            
Left Child: 2                                                                                                                                                        
Right Child: 1                                                                                                                                                       

Parent: 2                                                                                                                                                            
Left Child: 6                                                                                                                                                        
Right Child: 7                                                                                                                                                       

Parent: 1                                                                                                                                                            
Left Child: 3                                                                                                                                                        
Right Child: 4  

- Kavindu Dodanduwa

---

如果我想打印由数组形成的树的中序遍历，没有使用二叉树是否可能打印它？ - vineeth suhas

是的，如果树已经排序，那么什么也不需要做，只需打印数组即可 :) 就这么简单。但是我提供了解决方案，只是为了说明用数组表示二叉树是可能的，但是学习使用节点对于知识来说是很好的 :) （请参见此处，存储二叉树的方法部分：http://en.wikipedia.org/wiki/Binary_tree） - Kavindu Dodanduwa

实际上这棵树不是排序的，它是由问题中给定的数组形成的。我需要以中序方式打印数组，即给定数组的中序是{6, 2, 7, 5, 3, 1, 4}。我试过在不形成树的情况下打印它，但是我无法理解如何做到这一点。你能否提供一下代码给我？ - vineeth suhas