从数组中按层次顺序创建二叉树

Question

我正在研究一个小算法，它按层级顺序构建二叉树。给定一个数组，我必须使用其中的值来按层次顺序构建二叉树。例如： arr inarr[5]={1,2,3,4,5};

给定这样一个数组，我需要填充一个二叉树，使其看起来像这样:

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

(*为NULL) 这些节点是基本的二叉节点，具有左指针、右指针和一个int空间，其中保存了数组中的值。

我理解根据树的高度遍历树的概念，并且一次只能移动到下一层，但我不确定正确构建它的逻辑是什么。

- JustaRedShirt

---

http://stackoverflow.com/q/23668389/971127 - BLUEPIXY

在O(n)时间内构建一棵空树，如果你的数组已经排序，则可以按顺序遍历它并相应地填充节点。构建的树是一个完全二叉树，从右侧删除叶子节点以匹配你的数组大小。 - ThunderWiring

可能是Javascript TCP连接到服务器的重复问题。 - starkshang

@FireSun，我已经检查了您报告的可能重复帖子，但实际上我没有发现任何关联。您能否再次确认一下？ - lrleon

如果使用arr inarr[5]={3,1,2,4,5};，是否会构建相同的树？ - chux - Reinstate Monica

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;
}

- lrleon