二叉树的层序插入？

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[]的值并编写此树，使其看起来像图表。有许多层序遍历的示例，但找不到任何与二叉树构造实际编码相关的内容。这有点像“遍历”的反向操作。

另外请注意，这不是作业，尽管如果更多人以这种方式注意到它，我不介意标记它。 :)

- AruniRC

---

对我来说，最简单的机制似乎是将传入的数据存储到堆中。传入的数据是否适用于堆属性？还是树是二叉搜索树？ - sarnold

奇怪...通常二叉树是根据某种比较进行填充的。但显然这里不是这种情况。 - Codie CodeMonkey

从层序遍历中几乎总会构建出多棵树。不能保证再次生成与遍历创建的确切树相同。 - Bart Kiers

@DeepYellow，不，一个二叉树每个节点最多只有两个子节点。而一棵二叉搜索树则对节点进行排序。 - Bart Kiers

@Bart，我知道这棵树是二叉树，并且不需要排序就可以满足定义。我的观点是，在没有一些排序要求的情况下使用二叉结构是不寻常的。我从未遇到过实际应用，你呢？ - Codie CodeMonkey

一个二叉搜索树没有被指定；数据可能是有序的，但从树图中并不明显。 - AruniRC

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]

- Benny Tjia

Answer 2

这类似于BFS，因此您可以使用队列。

请注意，您总是先分配左子节点，然后立即分配右子节点。因此，从包含根的队列开始。在每次迭代中，从队列中弹出节点，然后从数组（或流）中读取下两个值。将第一个值设置为弹出节点的左子节点，并将其推入队列。然后将第二个值设置为右子节点并将其推入队列。依此类推，直到数组（或流）中没有元素为止。

- Petar Ivanov

Answer 3

对于一个完全（或充满）的二叉树，将层遍历转换为任何遍历都很容易，因为在数组从1开始编号时，位置为n的节点的子节点位于2n和2n+1，而在数组从0开始编号时，它们位于2n+1和2n+2。因此，您可以轻松使用该公式将其转换为插入节点到树中所需的喜爱遍历顺序（如前序遍历）。例如，递归伪代码：

void fill( TreeNode* node, char a[], int arrayLength, int n ){
    // n is the position of the current "node" in the array
    if( n < arrayLength ){
        node->data = a[n];
        fill( node->left, a, arrayLength, 2n+1 );
        fill( node->right, a, arrayLength, 2n+2 );
    }
}

- trutheality

Answer 4

如果您使用一些额外的存储空间，可以相对容易地采用迭代方式完成此操作，从而避免递归解决方案的调用开销。以下是我的建议：

node* theTree (char[] a, int arraylength) {
   if (arraylength == 0) return NULL;

   node** nodes = new node*[arraylength];
   nodes[0] = new node();
   nodes[0]->data = a[0];

   for (int i = 0, j = 0; TRUE ; j++) {
      if (++i >= arraylength) return nodes[0];

      nodes[i] = new node();
      nodes[i]->data = a[i];
      nodes[j]->left = nodes[i];

      if (++i >= arraylength) return nodes[0];

      nodes[i] = new node();
      nodes[i]->data = a[i];
      nodes[j]->right = nodes[i];
   }
}

可能的改进包括通过在 i > arraylength/2 时覆盖指针数组的一部分来将所需内存减少一半，并且可能通过将所有节点预先分配到一个数组中来进行预分配（但是需要小心处理释放）。请注意保留HTML标签。

- Erik P.

---

谢谢。递归删除确实是一件好事，但现在对我来说并不是必要的——代码紧凑性暂时够用。 - AruniRC