Binario
319
Árvore Binária de Busca
construída de tal forma que, para cada nó:
nós com chaves menores estão na sub-árvore esquerda nós com chaves maiores (ou iguais) estão na sub-árvore direita
a inserção dos nós da árvore deve satisfazer a essa propriedade
320
Árvore Binária de Busca
para a busca de uma chave v na árvore binária de busca: primeiro compare com a raiz
se menor, vá para a sub- árvore esquerda se maior, para a sub-árvore direita
aplique o método recursivamente
321
Árvore Binária de Busca
6 4 3 5 9
8
10
2
322
Árvore Binária de Busca
a cada passo, garante-se que nenhuma outra parte da árvore contém a chave sendo buscada o procedimento pára quando
o nó com v é encontrado senão, chega-se a NULL
323
Árvore Binária de Busca busca_arvore_nao_recursivo (v, pt) { do { if (v < pt->info) pt = pt-> esq; else pt = pt-> dir; }while (pt != NULL) && (v != pt->info); return(pt); }
324
Inserindo em Árvore Binária de Busca
Para inserir um nó na árvore:
fazer uma busca com insucesso alocar um novo nó é necessário saber por qual nó se chegou a NULL será o pai do novo nó
325
Inserindo em Árvore Binária de Busca
6 4 3 5 9
8
10
2
Inserindo o 9
326
Inserindo em Árvore Binária de Busca
6 4 3 5 7 2 9
8
10
Inserindo o 7
327
Inserção Árvore Binária de Busca insere_árvore (int valor, tipo_nó * pt) { tipo_nó * pai; do{ pai = pt ; if (valor < pt->chave) pt = pt ->esq ; else if ( valor > pt-> chave) pt = pt->dir; } while(pt != NULL) && (pt->chave != valor); if (pt == NULL){ pt = aloca(); pt ->chave = valor; pt->esq = NULL; pt->dir = NULL; if (v < pai->chave) pai ->esq = pt ; else pai ->dir = pt ; return(pt); } }
328
Inserção Árvore Binária de Busca
a árvore está classificada se percorrida da forma correta (pre, pos ou em-ordem?)
as chaves aparecem em