Бинарное дерево поиска - EcsFlash/DataTypes GitHub Wiki

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

Бинарное дерево поиска отличается от обычного бинарного дерева тем, что элементы располагаются в нем по следующему правилу: левый элемент должен быть меньше корня, а правый больше корня.

Создать пустое бинарное дерево поиска.

BSTree() {
	root = nullptr;
}

Уничтожить бинарное дерево поиска.

public:
~BSTree() {
	clear();
}
void clear() {
	clear(root);
}

private:
void clear(Node*& node) {
	if (node) {
		clear(node->right);
		clear(node->left);
		delete node;
		node = nullptr;
	}
}

Определить, пусто ли бинарное дерево.

bool isEmpty() {
	return root == nullptr;
}

Вставить новый элемент в бинарное дерево поиска.

public:
void insert(T element) {
	insert(root, element);
}

private:
void insert(Node*& node, T element) {
	if (!node) {
		node = new Node(element);
	}
	else {
		if (element >= node->data) {
			insert(node->right, element);
		}
		else {
			insert(node->left, element);
		}
	}
}

Удалить элемент из бинарного дерева поиска по заданному ключу.

public:
void remove(T element) {
	remove(root, element);
}

private:
void remove(Node*& node, T element) {
	if (node) {
		if (element < node->data) {
			remove(node->left, element);
		}
		else if (element > node->data) {
			remove(node->right, element);
		}
		else if (element == node->data) {
			if (node->left && node->right) {
				T succ = successor(node->left);
				node->data = succ;
			}
			else if (!node->left && node->right) {
				Node* temp = node;
				node = node->right;
				delete temp;
				temp = nullptr;
			}
			else if (node->left && !node->right) {
				Node* temp = node;
				node = node->left;
				delete temp;
				temp = nullptr;
			}
			else if (!node->left && !node->right) {
				delete node;
				node = nullptr;
			}
		}
	}
	else {
		throw invalid_argument("failed to remove")
	}

}

Обойти узлы бинарного дерева поиска в прямом, симметричном или обратном порядке

public:
void prefixTraverse() {
	prefixTraverse(root);
}

void postfixTraverse() {
	postfixTraverse(root);
}

void infixTraverse() {
	infixTraverse(root);
}

private:
void prefixTraverse(Node* node) {
	if (node) {
		//do smth
		prefixTraverse(node->left);
		prefixTraverse(node->right);
	}
}

void postfixTraverse(Node* node) {
	if (node) {
		postfixTraverse(node->left);
		postfixTraverse(node->right);
		//do smth

	}
}

void infixTraverse(Node* node) {
	if (node) {
		infixTraverse(node->left);
		//do smth
		infixTraverse(node->right);
	}
}

Поиск элемента по ключу. Рекурсивный вариант

public:
Node*& search(T element) {
	return search(root, element);
}

private:
Node*& search(Node*& node, T element) {
	if (node) {
		if (element == node->data) {
			return node;
		}
		else if (element >= node->data)
		{
			return search(node->right, element);
		}
		else {
			return search(node->left, element);
		}
	}
}

можно переделать в bool функцию, но мне так больше нравится + можно использовать для удаления например.

Поиск элемента по ключу. Итеративный вариант

bool iterativeSearch(T element) {
	Node* temp = root;
	while (temp) {
		if (temp->data == element) {
			return true;
		}
		else if (element < temp->data) {
			temp = temp->left;
		}
		else if(element >= temp->data){
			temp = temp->right;
		}
	}
	return false;
}