Алгоритм построения дерева Фибоначчи с заданным минимумом - PullRequest
Новая
       15

Алгоритм построения дерева Фибоначчи с заданным минимумом

1 голос
/ 01 июня 2019

Я хочу создать дерево Фибоначчи, но с минимальным числом, отличным от 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.И я не вижу, как они вычисляют число корня.Но кроме этого я действительно застрял.

1 Ответ

0 голосов
/ 02 июня 2019

Поскольку дерево Фибоначчи является рекурсивно определенной структурой, проще всего подумать о рекурсивном алгоритме.

Это своего рода псевдокод в стиле 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)

Поскольку это псевдокод, я, очевидно, не проверял его, но вы могли бы понять эту идею.

...