Construct a complete binary tree

题目

A complete binary tree with height H is defined as follows: The levels 1,2,3,...,H-1 contain the maximum number of nodes (i.e 2**(i-1) at the level i, note that we start counting the levels from 1 at the root). In level H, which may contain less than the maximum possible number of nodes, all the nodes are "left-adjusted". This means that in a levelorder tree traversal all internal nodes come first, the leaves come second, and empty successors (the nil's which are not really nodes!) come last.

Particularly, complete binary trees are used as data structures (or addressing schemes) for heaps.

We can assign an address number to each node in a complete binary tree by enumerating the nodes in levelorder, starting at the root with number 1. In doing so, we realize that for every node X with address A the following property holds: The address of X's left and right successors are 2A and 2A+1, respectively, supposed the successors do exist. This fact can be used to elegantly construct a complete binary tree structure. Write a predicate complete_binary_tree/2 with the following specification:

% complete_binary_tree(N,T) :- T is a complete binary tree with N nodes. (+,?)

Test your predicate in an appropriate way.

单元测试描述为：

解题思路

从完全二叉树的定义可得出：

• 从根节点开始层级优先，依次给节点从-开始标号。任意序号为N的节点，其左右子节点序号必为2*N和2*N+1。

现在，假设存在一个无限的二叉树，树中每个节点都有左右子节点。从根节点开始，按上述方式给每个节点标号。当遇到序号超过指定值的节点即停止。所有被标号的节点组成的二叉树即包含指定节点数的完全二叉树。

举个例子，指定节点个数4。

• 从根节点开始标号，根节点为1
  • 左子节点为2*1=2未超过指定值4，继续构造子树
    • 左子节点为2*2=4未超过指定值4，继续构造子树
      • 左子节点为2*4=8超过指定值4
      • 右子节点为2*4+1=9超过指定值4
    • 右子节点为2*2+1=5超过指定值
  • 右子节点为2*1+1=3未超过指定值4，继续构造子树
    • 左子节点为2*3=6超过指定值4
    • 右子节点为2*3+1=7超过指定值4

代码实现：