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

我想做一棵斐波那契树，但它的最小值不是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。我看不出他们是怎么计算根数的但除此之外，我真的被困住了。

最佳答案

由于fibonacci树是递归定义的结构，最简单的方法是考虑递归算法。
这是某种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;
}

你最终得到了一棵具有斐波那契结构的树，但还没有找到正确的数字。作为一个小助手，您拥有每个子树的节点数。
然后你可以做如下事情：

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)

既然这是伪代码，我显然还没有测试过，但你可以从中得到一些想法。

关于algorithm - 给定最小值构造斐波那契树的算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/56410140/