arvore_binaria

arvore.cpp

#include "arvore.h"

Arvore::Arvore()
{
	raiz = 0;
}

void Arvore::inserirNo(no** arvore, int valor)
{
	if((*arvore) != NULL)
	{
		pilha.push_back(*arvore);
	}
	if(*arvore == NULL)
	{
		*arvore = (no*) malloc(sizeof(no));
		(*arvore)->esq = NULL;
		(*arvore)->dir = NULL;
		(*arvore)->valor = valor;
		(*arvore)->fb = 0;
		while(pilha.size() != 0)
		{
			no* aux = pilha.back();
			pilha.pop_back();
			fb(&aux);
			if(aux->fb > 1 || aux->fb < -1)
			{
				if(aux->esq->fb > 0)
				{
					rsd(&aux);
				}
				if(aux->dir->fb > 0)
				{
					rse(&aux);
				}
				if(aux->esq->fb < 0)
				{
					rse(&(aux->esq->dir));
					rsd(&aux);	
				}
				if(aux->dir->fb < 0)
				{
					rsd(&(aux->dir->esq));
					rse(&aux);	
				}
			}
		}
		return;
	}
	
	if(valor <= (*arvore)->valor)
	{
		inserirNo(&(*arvore)->esq, valor);
	}
	else
	{
		inserirNo(&(*arvore)->dir, valor);
	}
}

void Arvore::imprimir(no** arvore)
{
	no* aux = *arvore;
	if(aux->esq != NULL)
	{
		imprimir(&aux->esq);
	}
	
	if(aux->dir != NULL)
	{
		imprimir(&aux->dir);
	}
	
	printf("\n%d\n", aux->valor);
	aux = NULL;
	return;
		
}

void Arvore::imprimirEmOrdem(no** arvore)
{
	no* aux = *arvore;
	if(aux != NULL)
	{
		imprimirEmOrdem(&aux->esq);
		printf("\n%d\n", aux->valor);
		imprimirEmOrdem(&aux->dir);
	}
}

int Arvore::altura(no** arvore)
{
	if((*arvore)== NULL)
	{
		return -1;
	}
	int he = altura(&(*arvore)->esq);
	int hd = altura(&(*arvore)->dir);
	
	return 1+(he>hd?he:hd);
}

void Arvore::fb(no** arvore)
{
	if((*arvore) != NULL)
	{
		int he = altura(&(*arvore)->esq);
		int hd = altura(&(*arvore)->dir);
		(*arvore)->fb = he-hd;
	}
}

void Arvore::rsd(no** arvore)
{
	no* aux = (*arvore)->esq;
	(*arvore)->esq = aux->dir;
	aux->dir = (*arvore);
	(*arvore) = aux;
}

void Arvore::rse(no** arvore)
{
	no* aux = (*arvore)->dir;
	(*arvore)->dir = (aux)->esq;
	(aux)->esq = (*arvore);
	(*arvore) = aux;
}

no* Arvore::busca(int valor, no** arvore)
{
	no* aux = raiz;
	return aux;
}

void Arvore::remove(int valor)
{
	no* arvore = busca(valor);
}

arvore.h

#include <iostream>
#include <stdlib.h>
#include <list>
using namespace std;

typedef struct no{
	int valor;
	struct no* esq;
	struct no* dir;
	int fb;
}NO;
class Arvore {
	public:
		Arvore();

		void inserir(int valor)
		{
			inserirNo(&raiz, valor);
		};
		void imprimir()
		{
			imprimir(&raiz);
		};
		void imprimirEmOrdem()
		{
			imprimirEmOrdem(&raiz);
		};
		int altura()
		{
			return altura(&raiz);
		};
		no* busca(int valor)
		{
			busca(valor, &raiz);
		}
		void remove(int valor);
		
	
	private:
		no* raiz;
		list<no*> pilha;
		void inserirNo(no**, int);
		void imprimir(no**);
		void imprimirEmOrdem(no**);
		int altura(no**);
		void fb(no**);
		void rsd(no**);
		void rse(no**);
		no* busca(int valor, no** arvore);
};

main.cpp

#include <iostream>
#include "arvore.h"
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main(int argc, char** argv) {
	Arvore arvore;
	arvore.inserir(10);
	arvore.inserir(5);
	arvore.inserir(15);
	arvore.inserir(7);
	arvore.inserir(6);
	arvore.inserir(4);
	arvore.inserir(3);
	arvore.inserir(2);
	arvore.inserir(20);
	arvore.inserir(21);
	arvore.inserir(22);
	arvore.inserir(12);
	arvore.inserir(13);
	arvore.imprimir();
	//arvore.imprimirEmOrdem();
	
	printf("\n\nAltura: %d\n\n", arvore.altura());
	system("pause");
	return 0;
}