用给定的最小值构造斐波那契树的算法

Question

我想制作一个斐波那契树，但最小数不是 1，而且我似乎找不到任何相关信息。

这是一个“普通”斐波那契树的示例，其最小节点为 1。

        5
      /   \
     3     7
   /   \  /
  2    4 6
 /
1

我想做的是，例如，最少 3 个:

高度为 0:这将是空树。

高度为1:

3

高度为 2:

   4
  /
 3

高度为 3:

     5
   /   \
  4     6
 /
3

高度为 4:

         7
      /    \
     5      9
   /   \   /
  4    6  8 
 /
3  

...等等。

我的问题是，我似乎看不到其中的模式，所以我想不出要编写的算法。

我知道左子树的高度是h-1(其中h是原始给定的高度)，右子树的高度是h-2。而且我看不出他们是如何计算根数的。但除此之外，我真的被困住了。

Answer 1

由于斐波那契树是递归定义的结构，最简单的方法是考虑递归算法。

这是某种 C 风格的伪代码(不涵盖任何边缘情况 - 我把它留给你作为练习的一部分)。

function createTree(height)
{
  // basic cases
  if(height == 0) return NULL;
  if(height == 1)
  {
    node = new Node;
    node.numNodesInTree = 1;
  }
  else
  {
    // according to the definition of the fibonacci tree
    node = new Node;
    node.leftChild  = createTree(height - 1);
    node.rightChild = createTree(height - 2);
    node.numNodesInTree =   node.leftChild.numNodesInTree
                          + node.rightChild.numNodesInTree
                          + 1; // also count the current node
  }
  return node;
}

您最终得到一棵具有斐波那契结构的树，但还不是正确的数字。作为小 helper ，你有每个子树的节点数。

然后你可以这样做:

function fillTree(offset, node, minimum) // offset means "all numbers in this subtree must be bigger than offset"
{
  // According to the binary search tree definition,
  // all numbers in the left sub tree have to be lower than
  // the current node.
  // All nodes in the right sub tree have to be larger.
  node.value =   node.leftChild.numNodesInTree // the number has to be bigger than all numbers in the left sub tree
               + 1                             // (that's the "one bigger")
               + offset                        // offset for right subtrees
               + minimum - 1;                  // Just stupidly add the minimum (as mentioned in the comment to your question)
  fillTree(offset, node.leftChild, minimum);      // propagate offset to left children
  fillTree(node.value, node.rightChild, minimum); // for the right sub tree, the current node's value is the new offset
                                                  // because all nodes in the right sub tree have to be bigger than the current node (binary search criterion)
}

然后你可以这样调用它:

root = createTree(height);
fillTree(0, root, 3); // when initially calling it, the offset is always 0
                      // You can set the minimum arbitrarily (i.e. 3 as in your example)

由于这是伪代码，显然我还没有测试过它，但您可以了解其背后的想法。