Dada uma árvore binária, escreva uma solução iterativa e recursiva para atravessar a árvore usando inorder traversal em C++, Java, e Python.
Listas ligadas sem similar, arrays unidimensionais e outras estruturas de dados lineares, que são atravessadas em ordem linear, árvores podem ser atravessadas de múltiplas maneiras em ordem de profundidade-primeira ordem (pré ordem, ordem e pós ordem) ou ordem de largura-primeira ordem (nível de ordem de travessia). Além dessas travessias básicas, vários esquemas mais complexos ou híbridos são possíveis, tais como buscas de profundidade limitada como a busca iterativa do aprofundamento da profundidade-primeira. Neste post, a travessia de árvore por ordem é discutida em detalhes.
Travessia de árvore envolve iteração sobre todos os nós de alguma forma. Como a árvore não é uma estrutura de dados linear, pode haver mais de um possível próximo nó de um determinado nó, portanto alguns nós devem ser adiados, ou seja, armazenados de alguma forma para uma visita posterior. A travessia pode ser feita iterativamente onde os nós diferidos são armazenados na pilha, ou pode ser feita por recursividade, onde os nós diferidos são armazenados implicitamente na pilha de chamadas.
Para atravessar uma árvore binária (não vazia) de forma ordenada, devemos fazer estas três coisas para cada nó n a partir da raiz da árvore:
(L) Atravessar recursivamente a sua sub-árvore esquerda. Quando este passo estiver terminado, estamos de volta a n novamente.(N) Processo n ele mesmo.(R) Atravessar recursivamente a sua sub-árvore direita. Quando este passo estiver terminado, estamos de volta em n novamente.Na travessia normal da ordem, visitamos a sub-árvore esquerda antes da sub-árvore direita. Se visitarmos a sub-árvore direita antes de visitarmos a sub-árvore esquerda, ela é referida como travessia de ordem inversa.
Como podemos ver, antes de processar qualquer nó, a sub-árvore esquerda é processada primeiro, seguida pelo nó, e a sub-árvore direita é processada finalmente. Estas operações podem ser definidas recursivamente para cada nó. A implementação recursiva é referida como uma busca em profundidade (DFS), pois a árvore de busca é aprofundada o máximo possível em cada filho antes de ir para o próximo irmão.
Following é o programa C++, Java e Python que o demonstra:
Aplicação iterativa –
Para converter o procedimento recursivo acima em iterativo, precisamos de uma pilha explícita. Abaixo está um algoritmo iterativo simples baseado em pilha para realizar a travessia em ordem.
iterativeInorder(node)
O algoritmo pode ser implementado em C++, Java, e Python da seguinte forma:
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
|
// Iterativo função para realizar travessia de ordem na árvore
inorderIterative(Node *root)
{
// criar uma pilha vazia
pilha<Node*> pilha;
// começar a partir do nó raiz (definir nó atual para o nó raiz)
Nó *curr = root;
// se o nó atual for nulo e a pilha também estiver vazia, estamos feitos
enquanto (!stack.empty() ||| curr != nullptr)
{
// se o nó atual existir, empurre-o para a pilha (defera-o)
// e mova-o para o seu filho esquerdo
if (curr != nullptr)
{
stack.push(curr);
curr = curr->left;
}
> outro
{
// caso contrário, se o nó atual for nulo, estale um elemento da pilha,
// imprima-o, e finalmente defina o nó atual para o seu filho direito
corrente = pilha.top();
stack.pop();
cout << curr->data << “;
curr = curr->right;
}
}
}
|
>
Download Run Complete Code
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
|
/ Iterativo função para executar inorder traversal na árvore
public static void inorderIterative(TreeNode root)
{
// criar uma pilha vazia
Stack<TreeNode> stack = pilha nova();
// começar a partir do nó raiz (definir nó atual para o nó raiz)
corrente do TreeNode = root;
// se o nó atual for nulo e a pilha também estiver vazia, estamos feitos
enquanto (!stack.empty() ||| curr != null)
{
// se o nó atual existir, empurre-o para a pilha (defera-o)
// e mova-se para o seu filho esquerdo
if (curr != null)
{
stack.push(curr);
curr = curr.left;
}
> outro
{
// caso contrário, se o nó atual for nulo, estale um elemento da pilha,
// imprima-o, e finalmente defina o nó atual para o seu filho direito
corrente = pilha.pop();
System.out.print(curr.data + ” “);
curr = curr.right;
}
}
>>979797>
|
>>979797>
Download Run Complete Code
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
|
# Função iterativa para realizar a travessia de ordem na árvore
def inorderIterative(root):
# criar uma pilha vazia
pilha = deque()
# começar a partir do nó raiz (definir nó atual para o nó raiz)
corrente = raiz
# se o nó atual for Nenhum e a pilha também estiver vazia, estamos feitos
enquanto pilha ou corrente:
# se o nó actual existir, empurra-o para a pilha (defere-o)
# e move-o para o seu filho esquerdo
se corrente:
stack.append(curr)
curr = curr.left
else:
# caso contrário, se o nó atual for Nenhum, pop um elemento da pilha,
# imprima-o, e finalmente defina o nó atual para o seu filho direito
curr = stack.pop()
print(curr.data, end=’ ‘)
curr = curr.direita
>>979797>
|
Download Run Complete Code
A complexidade temporal das soluções acima é O(n), onde n é o número total de nós na árvore binária. A complexidade de espaço do programa é O(n), pois o espaço necessário é proporcional à altura da árvore, que pode ser igual ao número total de nós na árvore na pior das hipóteses para árvores enviesadas.