Деревья фибоначи - EcsFlash/DataTypes GitHub Wiki

Hаиболее асимметpичное АВЛ-деpево Th высоты h имеет наиболее асимметpичное АВЛ-деpево Th-1 высоты h-1 в качестве одного из своих поддеpевьев и наиболее асимметpичное АВЛ-деpево высоты h-2 в качестве дpугого. Подобные деpевья называются деpевьями Фибоначчи.

Дерево Фибоначчи несколько больше напоминает реальный куст, чем рассматривавшиеся ранее деревья, возможно, потому, что многие природные процессы удовлетворяют закону Фибоначчи.

Приведем формальное определение дерева Фибоначчи.

Дерево Фибоначчи порядка k определяется следующим образом.

если k=0, то дерево Фибоначчи пусто; если k=1, то дерево Фибоначчи состоит из единственного узла, ключ которого содержит 1; если k >=2, то корень дерева Фибоначчи содержит ключ Fk, левое поддерево есть дерево Фибоначчи порядка k-1, правое поддерево есть дерево Фибоначчи порядка k-2 с ключами в узлах, увеличенными на Fk.

image

Наглядное построение дерева Фибоначчи

image

class FibTree{
private:
	struct Node
	{
		int   data;
		Node* left;
		Node* right;
		Node() {
			data = 0;
			left = right = nullptr;
		}
	};
	Node* root; //Указатель на корень дерева.
	void PrintTree(Node* W, int l) {
		int i;

		if (W != nullptr)
		{
			PrintTree(W->right, l + 1);
			for (i = 1; i <= l; i++) cout << "   ";
			cout << W->data << endl;
			PrintTree(W->left, l + 1);
		}
	}

	void FibonTree1(int k, Node*& node) {
		if (k == 0)  node = nullptr;
		else
			if (k == 1)
			{
				node = new Node();
			}
			else
			{
				node = new Node();
				FibonTree1(k - 1, node->left);
				FibonTree1(k - 2, node->right);
			}
	}

	void FibonTree2(Node*& node, int& i) {
		if (node)
		{
			FibonTree2(node->left, i);
			node->data = i;
			i++;
			FibonTree2(node->right, i);
		}
	}
public:
	FibTree() {
		root = nullptr; 
	};

	FibTree(int i, int k) {
		root = nullptr;
		FibonTree1(k, root);
		FibonTree2(root, i);
	}

	Node* GetTree() { 
		return root; 
	};

	Node* GetTree1() { 
		return root; 
	};

	void PrintTree() {
		PrintTree(root, 0);
	}
};
void main()
{
  
  int k;
  cout << "Вводите k...";
  cin >> k;
  //Построение дерева Фибоначчи.
  int i = 1; // Инициализация самого левого ключа дерева.
  Tree A(i, k);
  //Вывод дерева Фибоначчи
  A.PrintTree();
}

обля

⚠️ **GitHub.com Fallback** ⚠️