1. Conceito
A árvore de busca binária também se torna uma árvore de classificação binária. Tem a característica de que, se um nó tiver dois nós filhos, deve ser satisfeito. O valor do nó da criança esquerda deve ser menor que o valor do nó, e o valor do nó da criança certo deve ser maior que o valor do nó. Para comparações de tipos não básicos, a interface do comparador pode ser implementada. Neste artigo, os dados do tipo int são usados para operação.
Para implementar uma árvore binária, você deve começar com seu aumento. Somente construindo a árvore, você pode usar outras operações.
2. Construção da árvore de busca binária
Ao falar sobre o aumento de árvores binárias, devemos primeiro construir uma classe representando um nó. A classe do nó possui vários atributos, o valor do nó, o nó pai, o nó esquerdo e o nó direito do nó. O código é o seguinte
classe estática nó {nó pai; Nó esquerda da esquerda; Nó direito da direita; int val; Public Node (nó pai, nó leftChild, node direita, int val) {super (); this.parent = pai; this.leftchild = leftChild; this.rightChild = RightChild; this.val = val; } nó público (int val) {this (nulo, nulo, nulo, val); } nó público (nó nó, int val) {this (nó, nulo, nulo, val); }}Aqui usamos o método de escrita de classe interna. Depois de construir o valor do nó, construiremos a árvore inteira. Uma árvore deve primeiro ter um nó raiz e depois se estender aos nós filhos restantes. Nesta árvore, também existem alguns atributos, como a raiz da raiz básica e o tamanho do elemento na árvore. Se esses dois atributos forem usados, o atributo do comparador poderá ser adicionado ou uma implementação padrão poderá ser fornecida. O código específico é o seguinte
classe pública SearchBinaryTree {private node root; Tamanho privado int; public SearchBinaryTree () {super (); }}3. Adicione
Ao adicionar elementos, você deve considerar a inicialização do nó raiz. Geralmente, existem dois tipos: quando o construtor desta classe é inicializado, a raiz do nó raiz será inicializada. O segundo é adicionar o nó raiz quando o primeiro elemento for adicionado. Ambos trabalham em teoria, mas geralmente usam a segunda forma de carregamento preguiçoso.
Ao adicionar elementos, existem várias situações que precisam ser consideradas
1. Ao adicionar, determine se a raiz é inicializada. Se não for inicializado, será inicializado. Atribua o valor ao nó raiz e adicione um tamanho.
2. Como a árvore de pesquisa de árvores binárias satisfaz que o valor do nó raiz é maior que o nó esquerdo e menor que o nó direito, o valor inserido precisa ser comparado com o nó raiz primeiro. Se for grande, pesquise na subárvore direita. Se for pequeno, pesquise na subárvore esquerda. Até um nó infantil.
A implementação da inserção aqui pode adotar dois tipos: um, recursão, dois, iterativa (ou seja, através do modo de loop).
3.1. Inserção de versão recursiva
public boolean add (int val) {if (root == null) {root = new Node (val); tamanho ++; retornar true; } Nó nó = getAdApternode (root, val); Nó newNode = new Node (Val); if (node.val> val) {node.leftchild = newNode; newNode.parent = node; } else if (node.val <val) {node.rightChild = newNode; newNode.parent = node; } else {// nenhum processamento por enquanto} size ++; 19 retorna true; } /*** Obtenha o nó pai do nó a ser inserido. O nó pai atende a um dos seguintes estados* 1. O nó pai é um nó filho* 2. O valor do nó de inserção é menor que o nó pai, mas o nó pai não possui um nó filho esquerdo* 3. O valor do nó de inserção é maior que o nó pai, mas o nó pai não tem um nó de inserção. * 5. O nó pai está vazio* Se um dos 5 casos acima for satisfeito, ele interromperá recursivamente. * @param node * @param val * @return */ node privado getAdapTernode (nó, int val) {if (node == null) {retornar nó; } // Insira na subárvore esquerda, mas não há subárvore esquerda, if (node.val> val && node.leftChild == null) {return node; } // Insira na subárvore direita, mas não há subárvore correta, também retorne se (node.val <val && node.rightChild == null) {retornar node; } // Insira na subárvore direita, mas não há subárvore correta, também retorne se (node.val <val && node.rightChild == null) {retornar node; } // Insira na subárvore direita, mas não há subárvore correta, também retorne se (node.val <val && node.rightChild == null) {retornar node; } // Insira na subárvore direita, mas não há subárvore correta, retorne também se (node.leftchild == null && node.rightChild == null) {return node; } if (node.val> val && node.leftchild! = null) {return getadaptarnode (node.leftchild, val); } else if (node.val <val && node.rightChild! = null) {return getadaptarnode (node.rightChild, val); } else {return node; }}Use a recursão, primeiro encontre o ponto final da recursão e depois transforme todo o problema em um subproblema. No código acima, a lógica é aproximadamente assim: primeiro determine se o nó raiz é inicializado e, se não é inicializado, é inicializado e, após a conclusão, ele retorna e, em seguida, use uma função para obter o nó adaptado. Em seguida, insira o valor.
3.2. Versão iterativa
public boolean put (int val) {return putval (root, val); } private boolean putval (nó nó, int val) {if (node == null) {// Inicialize o nó da raiz = new Node (val); root = nó; tamanho ++; retornar true; } Nó temp = nó; Nó p; int t; / ** * Obtenha o melhor nó através da iteração do loop, */ do {p = temp; t = temp.val-val; if (t> 0) {temp = temp.leftchild; } else if (t <0) {temp = temp.rightChild; } else {temp.val = val; retornar falso; }} while (temp! = null); Nó newNode = new Node (P, Val); if (t> 0) {P.LeftChild = newNode; } else if (t <0) {P.RightChild = newNode; } tamanho ++; retornar true; }O princípio é realmente o mesmo que a recursão, que é obter o melhor nó e operar nesse nó.
Em termos de desempenho, é definitivamente a melhor versão iterativa; portanto, em geral, é a versão iterativa operar nos dados.
4. Exclua
Pode -se dizer que, na operação da árvore de busca binária, a exclusão é a mais complicada e há relativamente muitas situações a serem consideradas. Da maneira convencional, se você excluir um nó na árvore de busca binária, definitivamente pensará nas quatro situações a seguir.
1. O nó a ser excluído não tem nós da criança esquerda e direita, como mostrado nos nós D, E e G na figura acima
2. O nó a ser excluído é apenas o nó da criança esquerda, como o nó B
3. O nó a ser excluído é apenas o nó infantil certo, como o nó F
4. O nó a ser excluído deixou nós filhos e nós filhos da direita, como nós A e C
Nas três primeiras situações, pode -se dizer que é relativamente simples, enquanto o quarto é complicado. Vamos analisar o primeiro
Se for esse o caso, por exemplo, se o nó D for excluído, o nó infantil esquerdo do nó B poderá ser definido como nulo e se o nó g for excluído, o nó infantil certo do nó f pode ser definido como nulo. Qual lado deve ser definido e veja de que lado o nó excluído está localizado.
A segunda maneira de excluir o nó B, você só precisa definir o nó esquerdo do nó A para o nó D e o nó pai do nó D como A. Qual lado está definido depende de qual lado do nó excluído está localizado no nó pai.
O terceiro tipo é o mesmo que o segundo tipo.
O quarto tipo, que é um pouco complicado, como mencionado anteriormente, é, por exemplo, para excluir o nó C, defina o nó pai do nó F como o nó A, defina o nó esquerdo do nó f no nó e, na Substitua do Nó de A no Nó. Então, qual deve ser usado? Se o nó excluir é o nó raiz, como devo excluí -lo?
Para o quarto caso, você pode pensar assim: encontre o nó sucessor de c ou um nó, exclua o nó sucessor e defina o valor do nó sucessor com o valor de c ou um nó. Vamos primeiro suplementar o conceito de nós sucessores.
O nó sucessor de um nó em toda a árvore deve ser satisfeito. O nó com o menor valor no conjunto de nós que vale o nó é o nó sucessor. Obviamente, pode não haver nós sucessores.
No entanto, para o quarto caso, o nó sucessor deve existir e deve estar em sua subárvore direita, e também atende a um dos casos em que há apenas um nó filho ou nenhum nó filho. O motivo específico pode ser pensado sobre isso, porque o nó sucessor é maior que o nó C e, como as subseções esquerda e direita do nó C devem existir, ele deve existir na subseção esquerda na sub-árvore direita. Por exemplo, o nó sucessor de C é F, e o nó sucessor de A é E.
Com a análise acima, a implementação é relativamente simples, o código é o seguinte
public boolean excluir (int val) {nó nó = getNode (val); if (node == null) {return false; } Nó pai = node.parent; Nó leftChild = node.leftchild; Nó diretochild = node.rightChild; // Todos os seguintes nós dos pais estão vazios, significa que o nó excluído é o nó raiz se (leftChild == null && rightChild == null) {// sem nós filhos if (parent! } else if (parent.rightChild == node) {parent.rightChild = null; }} else {// O nó pai não existe, o que significa que o nó excluído é o nó raiz raiz = null; } node = null; retornar true; } else if (leftChild == null && rightChild! = null) {// apenas o nó direito if (pai! = null && parent.val> val) {// existe um nó pai e a posição do nó é o lado esquerdo do nó pai parent.leftchild = direto; } else if (pai! = null && parent.val <val) {// existe um nó pai, e a posição do nó é o lado direito do nó pai parent.rightChild = rightChild; } else {root = rightChild; } node = null; retornar true; } else if (leftChild! = null && rightchild == null) {// apenas o nó esquerdo se (pai! = null && parent.val> val) {// existe um nó pai, e a posição do nó é o lado esquerdo do nó pai parent.leftchild = leftChild; } else if (pai! = null && parent.val <val) {// existe um nó pai, e a posição do nó é o lado direito do nó pai parent.rightChild = leftChild; } else {root = leftChild; } retornar true; } else if (leftChild! = null && rightChild! = null) {// Ambos os nós da criança têm sucessor do nó = getSuccessor (nó); // Nesse caso, deve haver um nó sucessor int temp = sucessor.val; excluir boolean = delete (temp); if (delete) {node.val = temp; } sucessor = null; retornar true; } retornar false; } /*** Encontre o nó sucessor do nó do nó* 1. Primeiro, determine se o nó tem uma subárvore direita. Nesse caso, procure o nó sucessor na subárvore esquerda do nó direito. Caso contrário, prossiga para a próxima etapa* 2. Encontre o nó pai do nó. Se o nó direito do nó pai for igual ao nó, continue procurando o nó pai * até que o nó pai seja nulo ou encontre o nó certo que não é igual ao nó. * Motivo, o nó sucessor deve ser maior que o nó. Se houver uma subárvore correta, o nó sucessor deve existir na subárvore direita. Esta é a razão da primeira etapa* Se não houver subárvore correta, também pode haver um nó do avô do nó (ou seja, o nó pai do nó ou o nó pai acima do nó pai). * Procure iterativamente por ele, se houver, ele retorna o nó e, se não houver, retorna nulo * @param node * @return */ node privado getsuccessor (nó nó) {if (node.rightChild! = Null) {node sight = node.rightChild; while (rightChild.leftchild! = null) {rightchild = rightchild.leftchild; } retornar correto; } Nó pai = node.parent; while (pai! = null && (node == parent.rightChild)) {node = pai; pai = pai.parent; } retornar pai; }Para uma lógica específica, consulte a análise acima. Não vou descrever o texto aqui.
Além desta implementação, outra implementação é fornecida na introdução ao algoritmo.
public boolean Remow (int val) {nó nó = getNode (val); if (node == null) {return false; } if (node.leftchild == null) {// 1. O nó esquerdo não existe, o nó direito pode existir, incluindo duas situações. Ambos os nós não existem e apenas o nó certo existe transplante (nó, node.rightChild); } else if (node.rightChild == null) {// 2. O filho esquerdo existe e o nó direito não existe transplante (nó, node.leftchild); } else {// 3. Ambos os nós têm sucessor do nó = getSuccessor (nó); // Obtenha o nó do nó ode if (sucessor.parent! = node) {// O nó sucessor existe na subárvore direita do nó. transplante (sucessor, sucessor.rightChild); // substitua o sucessor pelo nó infantil certo do sucessor.rightChild = node.rightChild; // atribui a criança à direita do nó do nó à direita do nó de referência do sucessor. transplante (nó, sucessor); sucessor.leftchild = node.leftchild; sucessor.leftchild.parent = sucessor; } retornar true; } /*** Substitua o nó infantil por nó do nó* @param nó raiz raiz* @param nó nó para excluir* @param nó filho nó filho nó filho nó filho nó filho nó criança nó de criança Void transplante (nó nó Nó, nó não existe, então não é o nó. Etapa* 2. Determine que o nó é o filho do nó pai (ou seja, determine se o nó é um nó direito ou um nó esquerdo),* Após obter o resultado, substituir o nó filho pelo nó do nó, ou seja, o nó do nó. nó*/ if (node.parent == null) {this.root = filho; } else if (node.parent.leftchild == node) {node.parent.leftchild = filho; } else if (node.parent.rightChild == node) {node.parent.rightChild = filho; } if (filho! = null) {Child.parent = node.parent; }}5. Pesquise
A pesquisa também é relativamente simples, mas, na verdade, foi implementada quando é adicionada. Em situações reais, essa parte pode ser extraída de um método separado. O código é o seguinte
public node getNode (int val) {nó temp = root; int t; do {t = temp.val-val; if (t> 0) {temp = temp.leftchild; } else if (t <0) {temp = temp.rightChild; } else {return temp; }} while (temp! = null); retornar nulo; }6. Travessal de árvore de pesquisa binária
Depois de entender as propriedades da árvore de busca binária, fica claro que sua travessia de ordem intermediária é organizada em sequência de pequeno a grande. Aqui está o código de travessia da ordem intermediária fornecida aqui
public void print () {print (root); } private void print (nó root) {if (root! = null) {print (root.leftchild); System.out.println (root.val); // Se a posição estiver no meio, o pedido estará no meio. Se estiver na frente, está no precedente, caso contrário, é uma impressão subsequente (root.rightChild); }} Resumir
O exposto acima é a implementação Java da função de árvore de pesquisa binária introduzida pelo editor. Espero que seja útil para todos. Se você tiver alguma dúvida, deixe -me uma mensagem. O editor responderá a todos a tempo!