P407: Construct height-balanced binary trees with a given number of nodes

题目

Consider a height-balanced binary tree of height H. What is the maximum number of nodes it can contain? Clearly, MaxN = 2**H - 1. However, what is the minimum number MinN? This question is more difficult. Try to find a recursive statement and turn it into a predicate minNodes/2 defined as follwos:

% minNodes(H,N) :- N is the minimum number of nodes in a height-balanced binary tree of height H. (integer,integer), (+,?)

On the other hand, we might ask: what is the maximum height H a height-balanced binary tree with N nodes can have?

% maxHeight(N,H) :- H is the maximum height of a height-balanced binary tree with N nodes (integer,integer), (+,?)

Now, we can attack the main problem: construct all the height-balanced binary trees with a given nuber of nodes.

% hbal_tree_nodes(N,T) :- T is a height-balanced binary tree with N nodes.

Find out how many height-balanced trees exist for N = 15.

用单元测试描述为：

from python99.btree.p407 import minNodes, minHeight, maxHeight, hbal_tree_nodes def test_minNides(): assert minNodes(2) == 2 assert minNodes(3) == 4 assert minNodes(4) == 7 def test_minHeight(): assert minHeight(4) == 3 assert minHeight(7) == 3 def test_maxHeight(): assert maxHeight(7) == 4 assert maxHeight(12) == 5 def test_hbal_tree_nodes(): assert hbal_tree_nodes(4) == [ ['E', ['E', ['E', None, None], None], ['E', None, None]], ['E', ['E', None, ['E', None, None]], ['E', None, None]], ['E', ['E', None, None], ['E', ['E', None, None], None]], ['E', ['E', None, None], ['E', None, ['E', None, None]]] ]

解题思路

此题有两个问题要解答：

  1. 构成指定高度平衡二叉树所需的最少节点数
  2. 罗列包含指定节点数的平衡二叉树

构成指定高度平衡二叉树所需的最少节点数

这题可用递归法来解。当构造一棵二叉树时，先构造根节点再构造左右子树。而左右子又各是一棵二叉树。现在要加上一些约束：

  • 高度平衡二叉树
  • 最少节点

根据高度平衡二叉树的定义可知，左右子树的高度不可以超过一。而「最少节点」则意味着左右子树高度要䀆量的大。所以，左右子树高度差只能为一。这就有两种组合：左子树高度比右子树高度大一；左子树高度比右子树高度小一。本题只考泸最小节点数，不考泸树的结构。所以上述两种组合是等价的，只需计算其一即可。计算方法用递归方式描述为：

  1. 构造根节点佔用了一个高度
  2. 分别计算高度为N-1和N-2左右子树所需的节点数
  3. 将左右子树所需节点数相加，再加上根节点数1，即为所需节点数縂合

递归截止条件：

  1. 高度为0，所需节点数为0
  2. 高度为1，所需节点数为1

举个例子，求构造高度为3的高度平衡二叉树所需最少节点数。

  • 构造根节点佔用一个高度，剩余2
  • 分别计算高度为2和高度为1的左右子树所需节点数
    • 根节点佔用一个高度，剩余一个高度。分别计算高度为一和零的左右子树所需节点数
      • 高度为1的高度平衡二叉树需节点一个
      • 高度为0的高度平衡二叉树需节点0个
    • 合计高度为2的大子树需节点2个1+1+0
    • 高度为1的高度平衡二叉树需要1个节点
  • 合计需节点4个1+2+1

代码实现：

def minNodes(h): if h == 0: return 0 if h == 1: return 1 return 1 + minNodes(h-1) + minNodes(h-2)

罗列包含指定节点数的平衡二叉树

首先，求出包含指定数量节点高度平衡二叉树的最大和最小高度。然后，罗列出高度在最大最小高度之间的所有高度平衡二叉树。最后，再选出节点数等于指定数的高度平衡二叉树。

minHeight(N)

当二叉树中所有左右子树都包含相同节点时，其高度是最矮的。

举个例子，求包含4个节点的高度最小高度平衡二叉树。

  • 根节点佔用一个节点且佔用一个高度，剩余3个节点，左右子树最平均的分法为：左子树2个节点，右子树1个节点
    • 包含2个节点的左子树至少要2层高度
    • 包含1个节点的右子树至少要1层高度
  • 合计包含4个节点的高度平衡二叉树至少有高度3

代码实现：

def minHeight(n): if n == 0: return 0 return 1 + minHeight(n//2)

maxHeight(N)

当一棵高度平衡二叉树处于高度最高时，其左右子高度相差不超过一，且其中一棵子树只使用了最少的节点以达到其高度。

我们可以使用枚举法找到满足以上特性时，左右子树的高度，再加上一即为树的最大高度。

代码实现：

def maxHeight(n): if n == 1: return 1 if n == 0: return 0 if n == 2: return 2 if n == 3: return 2 for hLeft in range(1, n): nLeft = minNodes(hLeft) hRight = maxHeight(n-1-nLeft) if hLeft == hRight + 1 or hLeft == hRight: return 1 + max(hLeft, hRight)

构造指定高度的高度平衡二叉树

已在P406中实现，可以重用。

统计二叉树中的节点数

直接用递归法统计。

  • 二叉树中节点縂数等于根节点加左右子树节点
  • 左右子树依旧是二叉树

截止条件：

  • 空树，空树节点数为0

代码实现：

def nodes(t): if t is None: return 0 return 1 + nodes(t[1])+nodes(t[2])

罗列高度在minHeight和maxHeight之间的高度平衡二叉树。再过泸掉节点数不符的树。

代码实现：

def hbal_tree_nodes(n): trees = [] for h in range(minHeight(n), maxHeight(n)+1): trees = trees + hbal_tree(h) return [tree for tree in trees if nodes(tree) == n]

results matching ""

    No results matching ""