Árvore binária
Tese: Árvore binária. Pesquise 860.000+ trabalhos acadêmicosPor: gabrielFigueiro • 11/11/2014 • Tese • 1.998 Palavras (8 Páginas) • 340 Visualizações
Árvore binária
Origem: Wikipédia, a enciclopédia livre.
Uma simples árvore binária de tamanho 9 e altura 3, com um nó raiz de valor 2. A árvore acima não está balanceada e nem ordenada.
Uma árvore binária é uma estrutura de dados caracterizada por:
Ou não tem elemento algum (árvore vazia).
Ou tem um elemento distinto, denominado raiz, com dois ponteiros para duas estruturas diferentes, denominadas sub-árvore esquerda e sub-árvore direita.
Perceba que a definição é recursiva e, devido a isso, muitas operações sobre árvores binárias utilizam recursão. É o tipo de árvore mais utilizado na computação. A principal utilização de árvores binárias são as árvores de busca binária.
Índice [esconder]
1 Definições para árvores binárias
2 Definições em teoria dos grafos
3 Inserção
4 Percursos em árvore
4.1 Ordem Simétrica
4.2 Pré-Ordem
4.3 Pós-Ordem
5 Soma Elementos
6 Maior Elemento
7 Menor Elemento
8 Transformação de uma árvore n-ária
9 Métodos para representação de árvores binárias
10 Ver também
Definições para árvores binárias[editar | editar código-fonte]
Os nós de uma árvore binária possuem graus zero, um ou dois. Um nó de grau zero é denominado folha.
Em uma árvore binária, por definição, cada nó poderá ter até duas folhas, sendo que ela se compara com a abb (árvore binária de busca), apesar de não ter a propriedade da mesma ("na abb, existe uma regra na inserção").
A profundidade de um nó é a distância deste nó até a raiz. Um conjunto de nós com a mesma profundidade é denominado nível da árvore. A maior profundidade de um nó, é a altura da árvore.
Uma árvore "estritamente binária" é uma árvore na qual todo nó tem zero ou duas folhas. [1]
Existem autores, porém, que adotam essa definição para o termo quase completa, e utilizam o termo completa apenas para árvores em que todos os níveis têm o máximo número de elementos.
Definições em teoria dos grafos[editar | editar código-fonte]
Em teoria dos grafos, uma árvore binária é definida como um grafo acíclico, conexo, dirigido e que cada nó não tem grau maior que 2. Assim sendo, só existe um caminho entre dois nós distintos.
E cada ramo da árvore é um vértice dirigido, sem peso, que parte do pai e vai o filho.
Inserção[editar | editar código-fonte]
O algoritmo da inserção em árvores binárias são facilmente implementadas através de função recursiva.
Algoritmo da inserção em C:
void inserir(struct No **pRaiz, int numero){
if(*pRaiz == NULL){
* pRaiz = (struct No *) malloc(sizeof(struct No));
(*pRaiz)→pEsquerda = NULL;
(*pRaiz)→pDireita = NULL;
(*pRaiz)→numero = numero;
}else{
if(numero <(*pRaiz)→numero)
inserir(&(*pRaiz)→pEsquerda, numero));
else
inserir(&(*pRaiz)→pDireita, numero));
}
}
Algoritmo da inserção em Java:
public No Inserir(No novo, No anterior){
if (anterior != null){
if (novo.ObtemValor() < anterior.ObtemValor())
//Como o novo nó tem valor menor do que o do nó anterior, desce para a esquerda do nó anterior.
anterior.filho_Esq = this.Inserir(novo, anterior.filho_Esq);
else {
if(novo.ObtemValor() > anterior.ObtemValor())
//Como o novo nó tem valor maior do que o do nó anterior, desce para a direita do nó anterior.
anterior.filho_Dir = this.Inserir(filho, anterior.filho_Dir);
else
//Caso seja um nó já existente, sai do método.
return null;
}
} else {
//Insere o novo nó como folha.
anterior = novo;
}
return anterior;
}
Algoritmo da inserção em C#:
public class Node
{
public Node(int value)
{
Value = value;
}
public decimal Value { get; set; }
public Node Esq { get; set; }
public Node Dir { get; set; }
}
class Tree : BinarySearch
{
...