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

Question

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

这是一个 "normal" 斐波那契树的例子，最小节点为 1。

我想做的是例如最少3个：

高度为 0: 它将是空树。

身高1:

身高2：

   4
  /
 3

身高3:

身高4:

...等等

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

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

Answer 1

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

这是某种 C-style 伪代码（不涵盖任何边缘情况 - 我将其留给您作为练习的一部分）。

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 to construct Fibonacci's tree with given minimum

algorithm

recursion

binary-tree

fibonacci