c - 将级别顺序插入到二叉树中？

Question

假设我们给定一个水平顺序遍历输出。如何根据正确位置的数据构建二叉树？

请注意，我并不是要从给定的遍历输出中绘制树，而是从数组中读取遍历数据，然后通过实际的 C 语言编码将其填充到二叉树中。

例如:

让 a[] = {A, B, C, D, E, F, G};//数组中的遍历输出

所以层次顺序树看起来像这样:

            A
           / \ 
          B   C
        / \  / \
       D   E F  G

假设有一个这样的树节点结构:

typedef struct node
{
    char data;
    struct node* left;
    struct node* right;
}tree;

现在我正在尝试读取 a[] 值并对这棵树进行编码，使其看起来像图表。有很多层序遍历的例子，但找不到任何与二叉树构造的实际编码相关的东西。这有点像“遍历的逆向”。

另请注意，这不是家庭作业，但如果更多人注意到它，我在标记它时没有问题。 :)

Answer 1

一种可能的解决方案:

char a[SIZE] = {A,B,C,D,E,F,G}; 
    node* func(int index){
        if(index < SIZE){
            node *tmp = new node();
            tmp->data = a[index];
            tmp->left = func(2*index + 1);
            tmp->right = func(2*index + 2);
        }
        return tmp;
    }

树的堆栈跟踪:

                                     A->a[0]
          B->func(2*0 + 1)=[1]                              C->func(2*0 + 2)=[2]
D->func(2*1 + 1)=[3]    E->func(2*1 + 2)=[4]        F->func(2*2 + 1)=[5]     G->func(2*2 + 2)=[6]