arvore_binaria.cpp

#include <iostream>
#include <cstdlib>
#include <set>

using namespace std;

struct btree {
	struct btree *left;
	struct btree *right;
	int value;
};

// cria um novo nó para a árvore, já configurado...
btree *get_node(int value)
{
	btree *node = new struct btree;
	node->left = NULL;
	node->right = NULL;
	node->value = value;
	return node;
}

// insere um nó em uma árvore binária
void btree_insert(btree **root, int value)
{
	// encontramos o nó
	if (*root == NULL) {
		*root = get_node(value);
		return;
	}
	if ((*root)->value == value)
		return;

	if ((*root)->value > value)
		btree_insert(&((*root)->left), value);
	else btree_insert(&((*root)->right), value);
}

bool btree_find(btree *root, int value)
{
	// verifica se o nó não existe
	if (!root)
		return false;
	
	// verifica se esse é o nó procurado
	if (root->value == value)
		return true;

	// Procura nos filhos
	if (value < root->value)
		return btree_find(root->left, value);
	else return btree_find(root->right, value);
}

// exibe uma árvore binária
void btree_show(btree *root)
{
	if (root) {
		cout << root->value << ", ";
		btree_show(root->left);
		btree_show(root->right);
	}
}

// Retorna o pai de um nó a esquerda sem filho a esquerda.
btree *parent_without_left_child(btree *root, btree *parent)
{
	if (!root)
		return parent;

	if (root->left == NULL)
		return parent;
	return parent_without_left_child(root->left, root);
}


btree *btree_delete(btree *root, int value)
{
	// se a raíz for nula então o elemento não existe
	if (!root)
		return root;

	if (value > root->value)
		root->right = btree_delete(root->right, value);
	else
	if (value < root->value)
		root->left = btree_delete(root->left, value);
	else
	{
		// se este nó for uma folha
		if (root->left == root->right) {
			delete root;
			return NULL;
		}

		// Possui filhos a direita, mas não a esquerda
		if (root->left == NULL) {
			btree *r = root->right;
			delete root;
			return r;
		}

		// Possui filhos a esquerda, mas não a direita
		if (root->right == NULL) {
			btree *r = root->left;
			delete root;
			return r;
		}

		// Possui os dois filhos
		// pegamos a partir do primeiro nó da direita, o pai do primeiro nó sem filhos a esquerda
		btree *parent = parent_without_left_child(root->right, NULL);
		// se existir um pai, quer dizer que existem subarvores no primeiro nó a direita do nó a
		// ser removido
		if (parent) {
			btree *sub = parent->left;
			parent->left = sub->right;
			sub->right = root->right;
			sub->left = root->left;
			delete root;
			return sub;
		}
		delete root;
		return root->right;
	}
}

int main()
{
	btree *root = NULL;
	//for (int i = 0; i < 10; i++) {
	//	btree_insert(&root, rand()%50);
	//}
	btree_insert(&root, 1);

	cout << "Imprimindo a arvore...\n";
	btree_show(root);
	root = btree_delete(root, 1);
	cout << endl;
	btree_show(root);
}