Esta é uma questão de entrevista comum, como obter a travessia hierárquica da árvore binária através da pré-encomenda e travessia em ordem da árvore binária, etc.
Pré -encomendar + ordem média -> construir
Suponha que agora exista uma árvore binária, como segue:
Neste momento, a ordem de travessia é:
Pré -encomenda: GDAFEMHZ InOrder: ADEFGHMZ PROSTRADE: AEFDHZMG
Agora, faça pré-encomenda e encomenda (inorder), crie uma árvore binária ou dê uma ordem (inordem) e pós-ordem (postordem), crie uma árvore binária, na verdade é a mesma
Definição de nó de árvore:
árvore de classe {char val; árvore à esquerda; árvore à direita; árvore (char val, árvore esquerda, árvore direita) {this.val = val; this.left = esquerda; this.right = direito;} árvore () {} árvore (char val) {this.val = val; this.left = null; this.right = null;}}}Fazer conquistas:
public estática BuildTree (char [] pré -encomenda, char [] inomet) {// A encomenda é a sequência de pré -encomenda // inDorder é a sequência do meio se (pré -encomenda == null || pré -encomenda.length == 0) {return null;} raiz da árvore = new árvore (pré -encomenda [0]); para (char i = 0; i <inorder.length; i ++) {if (inOrder [i] == root.val) {inorderIndex = i;}} // a subárvore esquerda e a parte da subárvore direita da pré -encomenda [] preencherLeft = Arrays.copyofange (pré -encomenda, 1, 1+em encomenda); 1+inOrderIndex, pré -encomenda. BuildTree (pré -encomenda, inDorderLeft); árvore direita = BuildTree (pré -encomenda, inorderright); root.left = leftChild; root.right = rightChild; retorna raiz;}Na verdade, é o mesmo para criar uma ordem média + pós-ordem. Não vou escrever aqui
Vários travessios
Travessal de pós-ordem
public static void posterorderPrint (raiz da árvore) {// subsequente travessal // raízes esquerda e direita esquerda if (root.left! = null) {postorderPrint (root.left); } if (root.right! = null) {postOrderPrint (root.right); } System.out.print (root.val + ""); }Aprenda com um exemplo e a ordem é a mesma que a ordem no meio. Eu não vou escrever aqui
Travessal da sequência de camadas
Você pode usar uma fila na fila para primeiro adicionar o nó raiz à fila. Quando a fila não estiver vazia, pegue o nó do nó da cabeça da fila e imprima o valor do nó do nó. Se as crianças esquerda e direita do nó não estiverem vazias, adicione as crianças esquerda e direita à fila.
public static void layerOrderPrint (raiz da árvore) {if (root == null) {return; } // Sequência de camada Fila de travessia <ree> qe = new LinkedList <ree> (); qe.add (raiz); while (! System.out.print (node.val + ""); if (node.left! = null) {qe.add (node.left); } if (node.right! = null) {qe.add (node.right); }}}Prioridade de profundidade e largura
Na verdade, é apenas um ditado diferente. A prioridade da profundidade é a travessia de pré-encomenda, a amplitude da prioridade é a travessia de ordem de camada.
public static void DeepfirstPrint (raiz da árvore) {// Traversal de prioridade profunda é equivalente a encomendar travessias // para que você possa usar diretamente a travessia de pré -encomenda se (root == null) {return; } System.out.print (root.val + ""); if (root.left! = null) {DeepFirstPrint (root.left); } if (root.right! = null) {DeepFirstPrint (root.right); }} public static void DeepFirstPrintNoneCeC (raiz da árvore) {// A forma não-recursiva de profundidade prioridade travessal if (root == null) {return; } Pilha <ree> st = new Stack <ree> (); St.Add (raiz); enquanto (! System.out.print (node.val + ""); // A pilha está de volta e primeiro fora // Adicione a criança certa primeiro e depois o filho esquerdo se (node.right! = Null) {St.Add (node.right); } if (node.left! = null) {St.Add (node.left); }}}Função principal:
public static void main (string [] args) {char [] preordes = "gdafemhz" .toCharArray (); char [] inOrder = "Adefghmz" .ToCharArray (); Raiz da árvore = main.buildtree (pré -encomenda, inorder); // main.PostOrderPrint (raiz); // Traversal da PostLome // Main.LayerOrderPrint (root); // sequência de camadas travessal // main.deepfirstprint (root); // Prioridade profunda travessal // main.deepfirstprintnoneRec (root); // A versão não recursiva da profundidade de travessia}}Resumir
O exposto acima é sobre o estabelecimento de árvores binárias e vários códigos de instância de traversal em Java. Espero que seja útil para todos. Amigos interessados podem continuar se referindo a este site:
" Introdução a dois métodos de espelhamento em árvores binárias de programação Java "
" A linguagem java descreve a profundidade e a largura da árvore binária "
Caminho da árvore binária Java e exemplo
Se houver alguma falha, deixe uma mensagem para apontá -la. Obrigado amigos pelo seu apoio para este site!