Anúncios

Árvore representa os nós conectados por arestas. Vamos discutir árvore binária ou árvore binária de busca especificamente.

árvore binária é uma estrutura de dados especial usada para fins de armazenamento de dados. Uma árvore binária tem uma condição especial que cada nó pode ter um máximo de duas crianças., Uma árvore binária tem os benefícios tanto de um array ordenado e uma lista vinculada como a busca é tão rápida como em uma array ordenada e operação de inserção ou exclusão são tão rápidos quanto na lista vinculada.

termos importantes

a seguir são os termos importantes em relação à árvore.

  • Caminho-Caminho refere-se à sequência de nós ao longo das bordas de uma árvore.

  • Root − o nó no topo da árvore é chamado de root. Há apenas uma raiz por árvore e um caminho do nó raiz para qualquer nó.,

  • Pai-qualquer nó excepto o nó raiz tem uma aresta para cima para um nó chamado pai.

  • Child − O nó abaixo de um determinado nó conectado pela sua aresta para baixo é chamado de nó-filho.

  • Leaf-o nó que não tem nenhum nó-filho é chamado de nó-folha.

  • Subtree-Subtree representa os descendentes de um nó.

  • Visiting-Visiting refere-se a verificar o valor de um nó quando o controlo está no nó.

  • atravessar − atravessar significa passar através dos nós numa ordem específica.,

  • níveis-Nível de um nó representa a geração de um nó. Se o nó raiz está no nível 0, então seu próximo nó-filho está no nível 1, seu neto está no nível 2, e assim por diante.

  • chave-chave representa um valor de um nó baseado no qual uma operação de busca deve ser realizada para um nó.

representação em árvore de pesquisa binária

árvore de pesquisa binária exibe um comportamento especial. O filho esquerdo de um nó deve ter um valor inferior ao valor do seu pai e o filho direito do nó deve ter um valor maior do que o seu valor pai.,

vamos implementar árvore usando objeto de nó e conectá-los através de referências.

nó de árvore

o código para escrever um nó de árvore seria semelhante ao que é dado abaixo. Ele tem uma parte de dados e referências aos seus nós-filhos esquerda e direita.

struct node { int data; struct node *leftChild; struct node *rightChild;};

numa árvore, todos os nós partilham uma construção comum.

BST Operações Básicas

As operações básicas que podem ser executadas em uma árvore de busca binária estrutura de dados, são as seguintes: −

  • Inserir − Insere um elemento em uma árvore/criar uma árvore.,

  • procura um elemento numa árvore.

  • pré-ordem atravessa uma árvore de uma forma pré-ordem.

  • na ordem atravessa uma árvore de uma forma ordenada.

  • Postorder atravessa uma árvore de uma forma pós − ordem.

aprenderemos a criar (inserir) uma estrutura de árvore e a procurar um item de dados numa árvore neste capítulo. Vamos aprender sobre os métodos de travessia de árvores no próximo capítulo.

inserir operação

a primeira inserção cria a árvore., Depois, sempre que um elemento deve ser inserido, primeiro localize a sua localização adequada. Inicie a pesquisa a partir do nó raiz, então se os dados são menores que o valor chave, procure a localização vazia na sub-árvore esquerda e insira os dados. Caso contrário, procure a localização vazia na sub-árvore direita e insira os dados.,

Algoritmo

If root is NULL then create root nodereturnIf root exists then compare the data with node.data while until insertion position is located If data is greater than node.data goto right subtree else goto left subtree endwhile insert dataend If

Implantação

A implementação de inserir função deve olhar como este

Operação de Busca

Sempre que um elemento está a ser procurado, iniciar a pesquisa a partir do nó raiz e, em seguida, se os dados é menor do que o valor da chave, procure o elemento na subárvore esquerda. Caso contrário, procure o elemento na subárvore direita. Siga o mesmo algoritmo para cada nó.

algoritmo

If root.data is equal to search.data return rootelse while data not found If data is greater than node.data goto right subtree else goto left subtree If data found return node endwhile return data not found end if

a implementação deste algoritmo deve ser assim.,

para saber sobre a implementação da estrutura de dados da árvore de pesquisa binária, por favor Clique aqui.

Anúncios