根据数组按级别顺序创建二叉树

Question

我正在研究一种按级别顺序构建二叉树的小型算法。给我一个数组，我必须使用其中的值按级别顺序构建二叉树。示例：arr inarr[5]={1,2,3,4,5}；

给定一个这样的数组，我需要填写一个二叉树，如下所示：

        1
      /   \
    2      3
   / \    / \
  4   5  *   * 

（* 为 NULL）节点是基本的二进制节点，具有左指针和右指针以及保存数组中值的 int 空间。

我理解根据树的高度遍历树的概念，并且一次移动一层，但我不确定以这种方式正确构建它的正确逻辑。

Answer 1

按级别遍历树的“自然”方法是使用队列。因此，直观地说，执行相反操作的算法可以使用队列来记忆下一个要处理的节点。

这种算法将遵循以下原则：

1. 一般树的根位于以下位置0
2. 队列q有下一个要处理的节点
3. 每次我们看到一个节点时，通过从队列中提取，它的子节点位于位置i和i+1。请注意，级别遍历保证了这个条件。所以
4. 我们将当前节点的子节点放入队列中

以下伪代码从包含其按级别遍历的数组构建树

Node * build_from_level_order(int a[], int n)
{
  Queue q; // this is a queue of pointers to nodes

  Node * root = (Node*) malloc(sizeof(Node));
  root->key = a[0]; root->left = root->right = NULL;
  q.put(root);

  for (int i = 1; i < n; /* advancing of i is inside */)
    {
      Node * p = q.get();

      Node * l = (Node*) malloc(sizeof(Node));
      l->key = a[i++]; l->left = l->right = NULL;

      p->left = l;
      q.put(l);

      if (i < n) // last level could end in a left node, this test prevents to see an inexistent right node
        {
          Node * r = (Node*) malloc(sizeof(Node));
          r->key = a[i++]; r->left = r->right = NULL;
          p->right = r;
          q.put(r);
        }
    }

  return root;
}