Бинарные деревья - EcsFlash/DataTypes GitHub Wiki

Исходный код - тут

Дерево - это дерево

Структура дерева

struct BinaryTree
{
	int  data;
	BinaryTree* left, * right;

	BinaryTree(int  elem)
	{
		data = elem;
		left = right = nullptr;
	}
};

Создание пустого бинарного дерева

inline void initTree(BinaryTree*& root)
{
	root = nullptr;
}

Создание бинарного дерева, содержащего один узел, по заданному элементу

BinaryTree(int  elem)
	{
		data = elem;
		left = right = nullptr;
	}

Создание бинарного дерева по заданному корню и двум бинарным поддеревьями этого корня

inline void initTree(int elem,BinaryTree*& root,BinaryTree* rootLeft,BinaryTree* rootRight)
{
	root = new BinaryTree(elem);
	root->left = rootLeft;
	root->right = rootRight;
}

Удаление бинарного дерева

inline void clear(BinaryTree*& root)
{
	if (!isEmpty(root))
	{
		clear(root->left);
		clear(root->right);
		delete root;
		root = nullptr;
	}
}

Проверка на путоту

inline bool isEmpty(BinaryTree* root)
{
	return root == nullptr;
}

Определение или изменение данных, записанных в корне бинарного дерева

inline int getRootdata(BinaryTree* root)
{
	if (!isEmpty(root))
		return root->data;
}


inline void setRootdata(BinaryTree* root, int elem)
{
	if (!isEmpty(root))
	{
		root->data = elem;
	}
}

Присоединение к корню бинарного дерева левого или правого дочернего узла

ЛЕВОЕ
inline bool attachLeftSon(BinaryTree* root, int elem) {
	if (!isEmpty(root)) 
	{
		if (isEmpty(root->left)) 
		{
			root->left = new BinaryTree(elem);
			return true;
		}
		else return false;
	}
	return false;
}

ПРАВОЕ
inline bool attachRightSon(BinaryTree* root, int elem)
{
	if (!isEmpty(root))
	{
		if (isEmpty(root->right)) 
		{
			root->right = new BinaryTree(elem);
			return true;
		}
		else return false;
	}
	return false;
}

Присоединение к корню бинарного дерева левого или правого поддерева

ЛЕВОЕ
inline bool attachLeftTree(BinaryTree* root, BinaryTree* leftSubTree) 
{
	if (!isEmpty(root)) 
	{
		if (isEmpty(root->left)) 
		{
			root->left = leftSubTree;
			return true;
		}
		else return false;
	}
	return false;
}

ПРАВОЕ

inline bool attachRightTree(BinaryTree* root, BinaryTree* rightSubTree) 
{
	if (!isEmpty(root)) 
	{
		if (isEmpty(root->right)) 
		{
			root->right = rightSubTree;
			return true;
		}
		else return false;
	}
	return false;
}

Отсоединение от корня бинарного дерева левого или правого поддерева

ЛЕВОЕ
inline BinaryTree*& detachLeftSubTree(BinaryTree* root)
{
	BinaryTree* leftSubTree = root->left;
	root->left = nullptr;
	return leftSubTree;
}

ПРАВОЕ

inline BinaryTree*& detachRightSubTree(BinaryTree* root)
{
	BinaryTree *rightSubTree = root->right;
	root->right = nullptr;
	return rightSubTree;
}

Вернуть копию левого или правого поддерева корня бинарного дерева

Тут мы используем простую функцию копирования и запихиваем ее в другие функции

inline BinaryTree* copyTree(BinaryTree* root) {
	if (!isEmpty(root)) {
		BinaryTree* newRoot = new BinaryTree(root->data);
		newRoot->left = copyTree(root->left);
		newRoot->right = copyTree(root->right);
		return newRoot;
	}
	else {
		return nullptr;
	}
}

ЛЕВОЕ
inline BinaryTree*& copyLeftSubTree(BinaryTree* root) 
{
	if (!isEmpty(root)) 
	{
		BinaryTree* leftSubTree = copyTree(root->left);
		return leftSubTree;
	}
}

ПРАВОЕ

inline BinaryTree*& copyRightSubTree(BinaryTree* root) {
	if (!isEmpty(root))
	{
		BinaryTree *rightSubTree = copyTree(root->right);
		return rightSubTree;
	}
}

Продолжение смотрите тут.По этой ссылке вы обуздаете весь кайф деревьев