Escreva um algoritmo eficiente para encontrar uma árvore binária travessia de pré-encomenda de seu em ordem e pós-encomenda seqüência sem construir a árvore.
Por exemplo, considere a seguinte árvore:
Input:
Inorder traversal is { 4, 2, 1, 7, 5, 8, 3, 6 }
Postorder traversal is { 4, 2, 7, 8, 5, 6, 3, 1 }
Output:
The preorder traversal is { 1, 2, 4, 3, 5, 7, 8, 6 }
Inorder traversal is { 4, 2, 1, 7, 5, 8, 3, 6 }
Postorder traversal is { 4, 2, 7, 8, 5, 6, 3, 1 }
Output:
The preorder traversal is { 1, 2, 4, 3, 5, 7, 8, 6 }
Começamos com o nó raiz, cujo valor seria o último item na sequência de pós-ordem. A idéia é encontrar os limites da subárvore esquerda e direita do nó raiz em uma determinada sequência inorder. Para encontrar as arestas da subárvore esquerda e direita, procure o índice do nó raiz na sequência inorder. Todas as chaves antes do nó raiz na sequência inorder tornam-se parte da subárvore esquerda e todas as chaves após o nó raiz tornam-se parte da subárvore direita. Se repetirmos isso recursivamentemente para todos os nós da árvore, acabaremos fazendo uma travessia de pré-ordem na árvore.
O algoritmo pode ser implementado da seguinte forma em C++, Java e Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 |
#include <iostream> #include <vector> #include <stack> #include <unordered_map> using namespace std; // Função recursivo para encontrar travessia de pré-ordem de uma árvore binária // de sua sequência inorder e postorder. void printPreorder(int start, int end, vector<int> const &postorder, int &pIndex, unordered_map<int, int> &map, stack<int> &stack) { // caso base if (start > end) { return; } // O próximo elemento na sequência pós-ordem a partir do final será o nó raiz // da subárvore formada pela sequência inorder[start, end] int value = postorder[pIndex--]; // obtém o índice do nó atual em sequência inorder para determinar // seu limite de subárvore esquerdo e direito int index = map[value]; //recorre para a subárvore direita printPreorder(index + 1, end, postorder, pIndex, map, stack); //recorre para a subárvore esquerda printPreorder(start, index - 1, postorder, pIndex, map, stack); // coloca o valor do nó atual na Stack stack.push(value); } // Encontra o percurso de pré-ordem de uma árvore binária a partir de seu inorder e // sequência pós-ordem. Esta função assume que a entrada é válida. // isto é, dada sequência inorder e postorder forma uma árvore binária. void findPreorder(vector<int> const &inorder, vector<int> const &postorder) { // map é usado para encontrar eficientemente o índice de qualquer elemento em // uma dada sequência inorder unordered_map<int, int> map; //preenche o mapa for (int i = 0; i < inorder.size(); i++) { map[inorder[i]] = i; } // `lastIndex` armazena o índice do próximo nó não processado a partir do final // da sequência pós-ordem int lastIndex = inorder.size() - 1; // constrói uma Stack para armazenar a sequência de pré-ordem stack<int> stack; //preenche a Stack printPreorder(0, lastIndex, postorder, lastIndex, map, stack); // imprime a Stack cout << "The preorder traversal is "; while (!stack.empty()) { cout << stack.top() << ' '; stack.pop(); } } int main() { /* Construir a seguinte árvore 1 / \ / \ 2 3 / / \ / / \ 4 5 6 / \ / \ 7 8 */ vector<int> inorder = { 4, 2, 1, 7, 5, 8, 3, 6 }; vector<int> postorder = { 4, 2, 7, 8, 5, 6, 3, 1 }; findPreorder(inorder, postorder); return 0; } |
Resultado:
The preorder traversal is 1 2 4 3 5 7 8 6
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
import java.util.ArrayDeque; import java.util.Deque; import java.util.HashMap; import java.util.Map; class Main { // Função recursivo para encontrar travessia de pré-ordem de uma árvore binária // de sua sequência inorder e postorder. public static int printPreorder(int start, int end, int[] postorder, int pIndex, Map<Integer, Integer> map, Deque<Integer> stack) { // caso base if (start > end) { return pIndex; } // O próximo elemento na sequência de pós-ordem a partir do final será o // nó raiz da subárvore formada pela sequência inorder[start, end] int value = postorder[pIndex--]; // obtém o índice do nó atual em sequência inorder para determinar // seu limite de subárvore esquerdo e direito int index = map.get(value); //recorre para a subárvore direita pIndex = printPreorder(index + 1, end, postorder, pIndex, map, stack); //recorre para a subárvore esquerda pIndex = printPreorder(start, index - 1, postorder, pIndex, map, stack); // coloca o valor do nó atual na Stack stack.push(value); return pIndex; } // Encontra o percurso de pré-ordem de uma árvore binária a partir de seu inorder e // sequência pós-ordem. Esta função assume que a entrada é válida. // isto é, dada sequência inorder e postorder forma uma árvore binária. public static void findPreorder(int[] inorder, int[] postorder) { // map é usado para encontrar eficientemente o índice de qualquer elemento em // uma dada sequência inorder Map<Integer, Integer> map = new HashMap<>(); //preenche o mapa for (int i = 0; i < inorder.length; i++) { map.put(inorder[i], i); } // `lastIndex` armazena o índice do próximo nó não processado a partir do final // da sequência pós-ordem int lastIndex = inorder.length - 1; // constrói uma Stack para armazenar a sequência de pré-ordem Deque<Integer> stack = new ArrayDeque<>(); //preenche a Stack printPreorder(0, lastIndex, postorder, lastIndex, map, stack); // imprime a Stack System.out.print("The preorder traversal is "); while (!stack.isEmpty()) { System.out.print(stack.poll() + " "); } } public static void main(String[] args) { /* Construir a seguinte árvore 1 / \ / \ 2 3 / / \ / / \ 4 5 6 / \ / \ 7 8 */ int[] inorder = { 4, 2, 1, 7, 5, 8, 3, 6 }; int[] postorder = { 4, 2, 7, 8, 5, 6, 3, 1 }; findPreorder(inorder, postorder); } } |
Resultado:
The preorder traversal is 1 2 4 3 5 7 8 6
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
from collections import deque # Função recursivo para encontrar a travessia de pré-ordem de uma árvore binária # de sua sequência inorder e pós-ordem. def printPreorder(start, end, postorder, pIndex, d, stack): # caso básico if start > end: return pIndex # O próximo elemento na sequência pós-ordem a partir do final será o nó raiz # da subárvore formada pela sequência inorder[start, end] value = postorder[pIndex] pIndex = pIndex - 1 # obtém o índice de nó atual em sequência inorder para determinar # seu limite de subárvore esquerda e direita index = d[value] # recorrente para a subárvore direita pIndex = printPreorder(index + 1, end, postorder, pIndex, d, stack) # recorrente para a subárvore esquerda pIndex = printPreorder(start, index - 1, postorder, pIndex, d, stack) # empurra o valor do nó atual para a Stack stack.append(value) return pIndex # Encontre o percurso de pré-ordem de uma árvore binária a partir de seu inorder e # Sequência de pós-ordem de #. Esta função assume que a entrada é válida. # ou seja, dada sequência em ordem e pós-ordem forma uma árvore binária. def findPreorder(inorder, postorder): # O mapa # é usado para encontrar eficientemente o índice de qualquer elemento em # uma determinada sequência desordenada d = {} # preencha o dicionário for i, e in enumerate(inorder): d[e] = i # `lastIndex` armazena o índice do próximo nó não processado do final # da sequência pós-ordem lastIndex = len(inorder) - 1 # constrói uma Stack para armazenar a sequência de pré-encomenda stack = deque() # enche a Stack printPreorder(0, lastIndex, postorder, lastIndex, d, stack) # imprimir a Stack print('The preorder traversal is ', end='') while stack: print(stack.pop(), end=' ') if __name__ == '__main__': ''' Construct the following tree 1 / \ / \ 2 3 / / \ / / \ 4 5 6 / \ / \ 7 8 ''' inorder = [4, 2, 1, 7, 5, 8, 3, 6] postorder = [4, 2, 7, 8, 5, 6, 3, 1] findPreorder(inorder, postorder) |
Resultado:
The preorder traversal is 1 2 4 3 5 7 8 6
A complexidade de tempo da solução acima é O(n), Onde n é o número total de nós na árvore binária. O programa exige O(n) espaço extra para hashmap, pilha e ligue para Stack.