Na vida de programação, sempre encontramos estruturas de árvores. Nos últimos dias, precisamos apenas operar a estrutura da árvore, por isso registramos nossos próprios métodos e processos de operação. Agora, suponha que exista uma árvore como essa (não importa se é uma árvore binária ou não, os princípios são os mesmos)
1. Prioridade de profundidade
A abreviação inglesa é DFS, ou seja, a primeira pesquisa em profundidade.
A pesquisa em profundidade é um método mais comumente usado nos estágios iniciais dos rastreadores de desenvolvimento. Seu objetivo é alcançar os nós foliares da estrutura pesquisada (ou seja, os arquivos HTML que não contêm hiperlinks). Em um arquivo HTML, quando um hiperlink é selecionado, o arquivo HTML vinculado executará uma pesquisa de profundidade, ou seja, uma cadeia separada deve ser pesquisada na íntegra antes de procurar os resultados restantes do hiperlink. A pesquisa de prioridade de profundidade segue o hiperlink no arquivo HTML até que não possa ser aprofundado e retorna a um determinado arquivo HTML e continua a selecionar outros hiperlinks no arquivo HTML. Quando nenhum outro hiperlink está disponível, a pesquisa terminou. O processo é simplesmente aprofundar todos os caminhos possíveis de ramificação até que não possa ser mais profundo, e cada nó só pode ser acessado uma vez. Para o exemplo acima, o resultado da primeira traseira é: A, B, D, E, I, C, F, G, H. (assumindo que o lado esquerdo do nó infantil seja deixado primeiro).
A prioridade da profundidade é usada para atravessar cada nó e é necessária uma estrutura de dados como uma pilha. A característica da pilha é ir primeiro e depois sair. Todo o processo de travessia é o seguinte:
Primeiro, pressione o nó A na pilha, pilha (a);
POLE O NODE A e pressione os nós da criança C e B na pilha ao mesmo tempo. Neste momento, B está no topo da pilha, pilha (b, c);
POPELE O Nó B e pressione os nós filhos de B E e D na pilha. Neste momento, D está no topo da pilha, pilha (d, e, c);
POPELIONE O NOD D, NENHUM RODOS CRIANÇAS são pressionados e E está no topo da pilha, pilha (e, c);
POPELE O NODE E E Pressione o nó filho i na pilha (i, c);
... por sua vez, e a travessia final é concluída. O código Java é aproximadamente o seguinte:
public void depthfirst () {Stack <map <string, objeto >> nodEstack = new Stack <map <string, object >> (); map <string, object> node = new hashmap <string, object> (); nodEstack.add (node); while (! nodEstack.isEmpty ()) {node = nodEstack.pop (); system.out.println (node); // Obtenha o nó filho do nó. Para a árvore binária, é obter o nó infantil esquerdo e o nó filho direito da lista de nós <map <string, objeto >> crianças = getchildren (nó); if (crianças!2. A amplitude da prioridade
A abreviação inglesa é o BFS, o que significa amplitude do primeiro pesquisa. De acordo com o teste do processo, cada camada de nós é acessada por sua vez e, depois de acessar uma camada, cada nó pode acessá -lo apenas uma vez. Para o exemplo acima, o resultado da primeira travessia é: A, B, C, D, E, F, G, H, I (supondo que cada camada de nós seja acessada da esquerda para a direita).
A amplitude é usada para atravessar cada nó e é necessária uma estrutura de dados como uma fila. A característica da fila é o primeiro a sair e, de fato, também pode usar uma fila de ponta dupla. A diferença é que os nós podem ser inseridos e aparecidos na primeira posição da fila de ponta dupla. Todo o processo de travessia é o seguinte:
Primeiro insira o nó A na fila, na fila (a);
POLE O NODE A e Insira os nós filhos B e C de A na fila. Neste momento, B está no início da fila e C está no final da fila, fila (B, C);
POPELE O NODE B e insira os nós filhos D e E de B na fila ao mesmo tempo. Neste momento, C está no início da fila e E está no final da fila, fila (C, D, E);
POPELE O Nó C e insira os nós filhos F, G, H de C na fila. Neste momento, D está na frente da fila e H está no final da fila, fila (D, E, F, G, H);
POPLE UP O nó D, D não tem nós filhos, neste momento E está na frente da fila, H está na cauda da fila, fila (E, F, G, H);
... por sua vez, e a travessia final é concluída. O código Java é aproximadamente o seguinte:
public void Breadfirst () {Deque > nodedeque = novo Arraydeque > (); Mapa nó = novo hashmap (); acenado. while (! nodedeque.isempty ()) {node = nodedequ.peekfirst (); System.out.println (nó); // Obtenha o nó filho do nó. Para a árvore binária, o nó da criança esquerda e o nó filho direito do nó devem obter a lista do nó. > crianças = getchildren (nó); if (crianças! }}}} // A fila dupla é usada aqui, o que é o mesmo que usar a fila Resumir
O exposto acima é todo o conteúdo deste artigo sobre os exemplos de código de implementação Java de profundidade e amplitude de Java, e espero que seja útil para todos. Amigos interessados podem continuar se referindo a outros tópicos relacionados neste site. Se houver alguma falha, deixe uma mensagem para apontá -la. Obrigado amigos pelo seu apoio para este site!