Árvore de pesquisa binária C ++

BST é uma estrutura de dados que mantém os dados em uma lista classificada. É conhecido como uma árvore de busca binária porque, na árvore, cada nó tem um máximo de dois filhos que não pode ser aumentado ainda mais. Isso é conhecido como uma árvore de pesquisa porque é usada para pesquisar ou encontrar qualquer item presente. Implementaremos esse fenômeno na linguagem C ++.

Implementação

Em uma implementação, a primeira etapa é usar uma estrutura para inicializar a chave do tipo inteiro e nós do lado esquerdo e direito. Esses nós são definidos usando um ponteiro variável, pois ambos salvam os endereços dos nós alternativos. Depois disso, fechamos a estrutura.

Vamos criar um novo nó novamente através de uma estrutura. O parâmetro da função conterá os dados que queremos inserir no nó.

Nó da estrutura *NEWNODE (IT ITEM)

Ele criará uma nova temperatura do nó que armazenará dados nele, e o tamanho da memória será alocado através do Malloc (). Adicionaremos o valor do item na parte chave do nó. Enquanto as partes esquerda e direita, que são declaradas anteriormente na estrutura, são declaradas como nulas agora porque é o primeiro nó. A temperatura será devolvida.

É criada uma função com o nome "InOrder" e aceitará o nó raiz no parâmetro. Como sabemos, a árvore contém três partes principais: nó, lados esquerdo e direito da árvore. Usaremos uma estatura IF para verificar se a raiz não é nula. Em seguida, chame a função e envie a parte esquerda da raiz. Isso exibirá a própria raiz com uma seta que denotará a direção do caminho na árvore. Em seguida, para atravessar a direita, chame a função inorder com a direita da raiz como o parâmetro.

InOrder (raiz -> esquerda)

É assim que a travessia inorderada é feita. Para inserir um novo nó na árvore, usaremos uma função que levará um nó e a chave como valores de parâmetros. Se a árvore já estiver vazia, o novo nó será devolvido. No segundo caso, se a árvore não estiver vazia, primeiro vá para o lado direito e insira um novo nó aqui. Para inserção, usaremos uma declaração if-else para verificar o pedido da chave. A nova chave estará indo para o lado esquerdo para a ordem ascendente. Se a parte que verificará a nova chave for menor que o valor presente no nó, digite a chave para a parte esquerda do nó.

Nó -> esquerda = inserir (nó -> esquerda, tecla)

Considerando que, se a chave for maior, será para a parte certa.

Após a inserção do nó, verificaremos o próximo nó ou o nó que é o sucessor. É criada uma função do valor mínimo que criará um novo nó com um nome *atual. Este nó será atribuído por um valor passado como um argumento para a função. Primeiro encontrará o nó da esquina ou a folha do modo esquerdo no lado esquerdo da árvore. Usamos um pouco o loop que itera até que a travessia do nó seja concluída. Em outras palavras, a parte esquerda do nó atual não é nula.

Current = Current -> Esquerda

Continue atribuindo o nó atual o valor da próxima corrente dentro do loop à esquerda.

Nossa árvore é atravessada e organizada adicionando folhas de ambos os lados. Cada valor será inserido através da chamada de função feita do programa principal. Agora, precisamos procurar qualquer elemento e excluí -lo assim que for encontrado.

A árvore em C ++ funciona no mesmo fenômeno que a lista vinculada. Aplicaremos a pesquisa binária na árvore e realizaremos uma operação de exclusão para excluir um nó ou folha da árvore. Uma função do nó de exclusão é criada; Ele conterá a árvore e o valor como parâmetros. Vamos verificar primeiro se as árvores devem ter valores dentro delas. Portanto, a estatura se será usada e, se a raiz for nula, significa retornar apenas a raiz.

Se (chave da chave)

A chave que você deseja excluir é menor que o nó raiz. Em seguida, mova -se para o lado esquerdo e chame a função de exclusão com a parte esquerda da árvore, e a chave a ser excluída.

Raiz -> esquerda = deletenode (raiz -> esquerda, chave);

E o mesmo vale para a parte mais se. Se a chave for maior que a chave do nó, vá para o caminho certo, chame a função de exclusão. Passe a parte certa da árvore e a chave para que se torne fácil encontrar o nó que você deseja excluir.

Agora, chegando em direção à parte, isso é aplicável se o nó estiver sozinho, não tiver folha ainda mais ou apenas um único filho à frente. Dentro da parte mais uma parte novamente, se uma declaração será usada que verificará se não houver nó no lado direito, adicione o valor no lado direito do nó ao novo nó temp, da mesma forma que o lado esquerdo.

Nó da estrutura * temp = root -> esquerda;

Nessa condição, liberte a raiz. Isso removerá o valor da raiz.

Livre (raiz);

Se algum nó contiver duas folhas com ele, para pesquisar o valor, usaremos a função Min Value, e a parte certa será enviada para a função.

Minvaluenode (raiz -> à direita);

Quando o valor a ser excluído for encontrado, o declararemos a última parte da árvore para que ela possa ser excluída facilmente.

Raiz -> key = temp -> key;

Depois de fazer isso, exclua o nó,

Raiz -> direita = excluir nó (nó -> direita, temp -> chave);

Depois de fechar a função, declararemos o programa principal aqui. O nó raiz será definido como nulo inicialmente. Usando a chamada de função insert (), usaremos a raiz e os dados numéricos no nó.

Inserir (raiz, 5);

A função inorderada é chamada para a travessia da árvore.

InOrder (raiz);

Então, para excluir o nó, chamaremos a função de exclusão.

Raiz = deletenode (raiz, 10);

Após a exclusão, os valores são novamente exibidos.

Depois de escrever o código, nós o executaremos no terminal do Ubuntu através do compilador.

$ g ++ -o arquivo de arquivo.c
$ ./arquivo

Como você pode ver, os sete itens são inseridos no nó. Um é excluído e o restante será exibido na mesma ordem que antes.

Conclusão

Uma árvore de pesquisa binária é usada para armazenar os valores na forma classificada. Para pesquisar qualquer número, todos os números devem ser classificados primeiro em ordem. Depois disso, o número especificado é pesquisado dividindo a árvore em duas partes, fazendo subárvores. A implementação BST é feita no sistema Ubuntu, explicando um exemplo de maneira elaborada. Esperamos que você tenha achado este artigo útil. Verifique os outros artigos de dica do Linux para obter mais dicas e tutoriais.