travessia fim cargo de árvore binária sem recursão
https://stackoverflow.com/questions/1294701
-
18-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
O que é o algoritmo para fazer um percurso fim cargo de uma árvore binária SEM usando recursão?
Solução
Aqui está um link que fornece duas outras soluções sem o uso de bandeiras visitados.
https://leetcode.com/problems/binary-tree-postorder-traversal /
Esta é, obviamente, uma solução baseada em pilha devido à falta de ponteiro pai na árvore. (Nós não precisamos de uma pilha se há ponteiro pai).
Nós iria empurrar o nó raiz para a pilha pela primeira vez. Enquanto a pilha não está vazio, continuamos empurrando o filho esquerdo do nó da parte superior da pilha. Se a criança esquerda não existe, eu empurro seu filho direito. Se é um nó folha, processamos o nó e pop-lo fora da pilha.
Nós também usamos uma variável para manter o controle de um nó anteriormente percorrido. O objetivo é determinar se o percurso é descendente / ascendente da árvore, e também podemos saber se ele subir a partir da esquerda / direita.
Se nós ascendemos a árvore da esquerda, nós não quer empurrar seu filho esquerdo novamente para a pilha e deve continuar ascender para baixo da árvore, se existe o direito da criança. Se subirmos a árvore da direita, devemos processá-lo e colocá-lo fora da pilha.
Nós iria processar o nó e pop-lo a pilha nestes 3 casos:
- O nó é um nó folha (sem filhos)
- Nós apenas atravessar a árvore a partir do não existir filho direito e esquerdo.
- Nós apenas atravessar a árvore da direita.
Outras dicas
Aqui está a versão com uma pilha e sem uma bandeira visitados:
private void postorder(Node head) {
if (head == null) {
return;
}
LinkedList<Node> stack = new LinkedList<Node>();
stack.push(head);
while (!stack.isEmpty()) {
Node next = stack.peek();
boolean finishedSubtrees = (next.right == head || next.left == head);
boolean isLeaf = (next.left == null && next.right == null);
if (finishedSubtrees || isLeaf) {
stack.pop();
System.out.println(next.value);
head = next;
}
else {
if (next.right != null) {
stack.push(next.right);
}
if (next.left != null) {
stack.push(next.left);
}
}
}
}
Aqui está um exemplo de wikipedia :
nonRecursivePostorder(rootNode)
nodeStack.push(rootNode)
while (! nodeStack.empty())
currNode = nodeStack.peek()
if ((currNode.left != null) and (currNode.left.visited == false))
nodeStack.push(currNode.left)
else
if ((currNode.right != null) and (currNode.right.visited == false))
nodeStack.push(currNode.right)
else
print currNode.value
currNode.visited := true
nodeStack.pop()
Este é o uso I abordagem para iterativo, travessia de pós-ordem. Eu gosto desta abordagem, porque:
- Ele só lida com uma única transição por ciclo loop, por isso é fácil de seguir.
- Uma solução semelhante funciona para travessias em ordem e pré-encomenda
Código:
enum State {LEFT, RIGHT, UP, CURR}
public void iterativePostOrder(Node root) {
Deque<Node> parents = new ArrayDeque<>();
Node curr = root;
State state = State.LEFT;
while(!(curr == root && state == State.UP)) {
switch(state) {
case LEFT:
if(curr.left != null) {
parents.push(curr);
curr = curr.left;
} else {
state = RIGHT;
}
break;
case RIGHT:
if(curr.right != null) {
parents.push(curr);
curr = curr.right;
state = LEFT;
} else {
state = CURR;
}
break;
case CURR:
System.out.println(curr);
state = UP;
break;
case UP:
Node child = curr;
curr = parents.pop();
state = child == curr.left ? RIGHT : CURR;
break;
default:
throw new IllegalStateException();
}
}
}
Explicação:
Você pode pensar sobre os passos como este:
- Tente ESQUERDA
- se existe nó esquerda: Tente novamente à esquerda
- se-node esquerda não existe: tente Direito
- DIREITO Try
- Se um nó direito existe: Tente LEFT de lá
- Se existe o direito, você está em uma folha: Tente CURR
- CURR Try
- Imprimir nó atual
- Todos os nós abaixo foram executados (pós-ordem): Tente UP
- Tente UP
- Se nó é raiz, não há UP, então SAIR
- Se surgindo da esquerda, tente Direito
- Se chegando da direita, Tente CURR
import java.util.Stack;
public class IterativePostOrderTraversal extends BinaryTree {
public static void iterativePostOrderTraversal(Node root){
Node cur = root;
Node pre = root;
Stack<Node> s = new Stack<Node>();
if(root!=null)
s.push(root);
System.out.println("sysout"+s.isEmpty());
while(!s.isEmpty()){
cur = s.peek();
if(cur==pre||cur==pre.left ||cur==pre.right){// we are traversing down the tree
if(cur.left!=null){
s.push(cur.left);
}
else if(cur.right!=null){
s.push(cur.right);
}
if(cur.left==null && cur.right==null){
System.out.println(s.pop().data);
}
}else if(pre==cur.left){// we are traversing up the tree from the left
if(cur.right!=null){
s.push(cur.right);
}else if(cur.right==null){
System.out.println(s.pop().data);
}
}else if(pre==cur.right){// we are traversing up the tree from the right
System.out.println(s.pop().data);
}
pre=cur;
}
}
public static void main(String args[]){
BinaryTree bt = new BinaryTree();
Node root = bt.generateTree();
iterativePostOrderTraversal(root);
}
}
Aqui está uma solução em C ++ que não requer qualquer armazenamento de contabilidade na árvore.
Em vez disso, utiliza duas pilhas. Um para nos ajudar a atravessar e outro para armazenar os nós para que possamos fazer um post travessia deles.
std::stack<Node*> leftStack;
std::stack<Node*> rightStack;
Node* currentNode = m_root;
while( !leftStack.empty() || currentNode != NULL )
{
if( currentNode )
{
leftStack.push( currentNode );
currentNode = currentNode->m_left;
}
else
{
currentNode = leftStack.top();
leftStack.pop();
rightStack.push( currentNode );
currentNode = currentNode->m_right;
}
}
while( !rightStack.empty() )
{
currentNode = rightStack.top();
rightStack.pop();
std::cout << currentNode->m_value;
std::cout << "\n";
}
// a versão java com a bandeira
public static <T> void printWithFlag(TreeNode<T> root){
if(null == root) return;
Stack<TreeNode<T>> stack = new Stack<TreeNode<T>>();
stack.add(root);
while(stack.size() > 0){
if(stack.peek().isVisit()){
System.out.print(stack.pop().getValue() + " ");
}else{
TreeNode<T> tempNode = stack.peek();
if(tempNode.getRight()!=null){
stack.add(tempNode.getRight());
}
if(tempNode.getLeft() != null){
stack.add(tempNode.getLeft());
}
tempNode.setVisit(true);
}
}
}
void postorder_stack(Node * root){
stack ms;
ms.top = -1;
if(root == NULL) return ;
Node * temp ;
push(&ms,root);
Node * prev = NULL;
while(!is_empty(ms)){
temp = peek(ms);
/* case 1. We are nmoving down the tree. */
if(prev == NULL || prev->left == temp || prev->right == temp){
if(temp->left)
push(&ms,temp->left);
else if(temp->right)
push(&ms,temp->right);
else {
/* If node is leaf node */
printf("%d ", temp->value);
pop(&ms);
}
}
/* case 2. We are moving up the tree from left child */
if(temp->left == prev){
if(temp->right)
push(&ms,temp->right);
else
printf("%d ", temp->value);
}
/* case 3. We are moving up the tree from right child */
if(temp->right == prev){
printf("%d ", temp->value);
pop(&ms);
}
prev = temp;
}
}
Por favor, veja esta implementação Java completo. Basta copiar o código e cole em seu compilador. Ele vai funcionar bem.
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
class Node
{
Node left;
String data;
Node right;
Node(Node left, String data, Node right)
{
this.left = left;
this.right = right;
this.data = data;
}
public String getData()
{
return data;
}
}
class Tree
{
Node node;
//insert
public void insert(String data)
{
if(node == null)
node = new Node(null,data,null);
else
{
Queue<Node> q = new LinkedList<Node>();
q.add(node);
while(q.peek() != null)
{
Node temp = q.remove();
if(temp.left == null)
{
temp.left = new Node(null,data,null);
break;
}
else
{
q.add(temp.left);
}
if(temp.right == null)
{
temp.right = new Node(null,data,null);
break;
}
else
{
q.add(temp.right);
}
}
}
}
public void postorder(Node node)
{
if(node == null)
return;
postorder(node.left);
postorder(node.right);
System.out.print(node.getData()+" --> ");
}
public void iterative(Node node)
{
Stack<Node> s = new Stack<Node>();
while(true)
{
while(node != null)
{
s.push(node);
node = node.left;
}
if(s.peek().right == null)
{
node = s.pop();
System.out.print(node.getData()+" --> ");
if(node == s.peek().right)
{
System.out.print(s.peek().getData()+" --> ");
s.pop();
}
}
if(s.isEmpty())
break;
if(s.peek() != null)
{
node = s.peek().right;
}
else
{
node = null;
}
}
}
}
class Main
{
public static void main(String[] args)
{
Tree t = new Tree();
t.insert("A");
t.insert("B");
t.insert("C");
t.insert("D");
t.insert("E");
t.postorder(t.node);
System.out.println();
t.iterative(t.node);
System.out.println();
}
}
Aqui estou colando versões diferentes em c # (.NET) para referência: (Na ordem iterativo TRAVERSAL você pode se referir a: Ajuda-me a entender Inorder Traversal sem usar recursão )
- wiki ( http://en.wikipedia.org/wiki/Post -order% 5Ftraversal # Implementações ) (elegante)
- Outra versão única pilha (# 1 e # 2: usa basicamente o fato de que na travessia pós fim do nó filho direito é visitado antes de visitar o nó actual - assim, nós simplesmente contar com a verificação de que se a criança direita de topo da pilha é de fato o nó último post fim travessia isso é visto - eu adicionei comentários em abaixo trechos de código para detalhes)
- Usando a versão duas pilhas (ref: http://www.geeksforgeeks.org/iterative -postorder-atravessamento / ) (Mais fácil: travessia, basicamente, pós ordem é inversa nada além de travessia ordem pré com um ajuste simples que nó direito é visitado em primeiro lugar, e depois nó esquerdo)
- Usando a bandeira visitante (fácil)
- Unidade de Testes
~
public string PostOrderIterative_WikiVersion()
{
List<int> nodes = new List<int>();
if (null != this._root)
{
BinaryTreeNode lastPostOrderTraversalNode = null;
BinaryTreeNode iterativeNode = this._root;
Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
while ((stack.Count > 0)//stack is not empty
|| (iterativeNode != null))
{
if (iterativeNode != null)
{
stack.Push(iterativeNode);
iterativeNode = iterativeNode.Left;
}
else
{
var stackTop = stack.Peek();
if((stackTop.Right != null)
&& (stackTop.Right != lastPostOrderTraversalNode))
{
//i.e. last traversal node is not right element, so right sub tree is not
//yet, traversed. so we need to start iterating over right tree
//(note left tree is by default traversed by above case)
iterativeNode = stackTop.Right;
}
else
{
//if either the iterative node is child node (right and left are null)
//or, stackTop's right element is nothing but the last traversal node
//(i.e; the element can be popped as the right sub tree have been traversed)
var top = stack.Pop();
Debug.Assert(top == stackTop);
nodes.Add(top.Element);
lastPostOrderTraversalNode = top;
}
}
}
}
return this.ListToString(nodes);
}
Aqui está travessia pós ordem com uma pilha (minha versão)
public string PostOrderIterative()
{
List<int> nodes = new List<int>();
if (null != this._root)
{
BinaryTreeNode lastPostOrderTraversalNode = null;
BinaryTreeNode iterativeNode = null;
Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
stack.Push(this._root);
while(stack.Count > 0)
{
iterativeNode = stack.Pop();
if ((iterativeNode.Left == null)
&& (iterativeNode.Right == null))
{
nodes.Add(iterativeNode.Element);
lastPostOrderTraversalNode = iterativeNode;
//make sure the stack is not empty as we need to peek at the top
//for ex, a tree with just root node doesn't have to enter loop
//and also node Peek() will throw invalidoperationexception
//if it is performed if the stack is empty
//so, it handles both of them.
while(stack.Count > 0)
{
var stackTop = stack.Peek();
bool removeTop = false;
if ((stackTop.Right != null) &&
//i.e. last post order traversal node is nothing but right node of
//stacktop. so, all the elements in the right subtree have been visted
//So, we can pop the top element
(stackTop.Right == lastPostOrderTraversalNode))
{
//in other words, we can pop the top if whole right subtree is
//traversed. i.e. last traversal node should be the right node
//as the right node will be traverse once all the subtrees of
//right node has been traversed
removeTop = true;
}
else if(
//right subtree is null
(stackTop.Right == null)
&& (stackTop.Left != null)
//last traversal node is nothing but the root of left sub tree node
&& (stackTop.Left == lastPostOrderTraversalNode))
{
//in other words, we can pop the top of stack if right subtree is null,
//and whole left subtree has been traversed
removeTop = true;
}
else
{
break;
}
if(removeTop)
{
var top = stack.Pop();
Debug.Assert(stackTop == top);
lastPostOrderTraversalNode = top;
nodes.Add(top.Element);
}
}
}
else
{
stack.Push(iterativeNode);
if(iterativeNode.Right != null)
{
stack.Push(iterativeNode.Right);
}
if(iterativeNode.Left != null)
{
stack.Push(iterativeNode.Left);
}
}
}
}
return this.ListToString(nodes);
}
Usando duas pilhas
public string PostOrderIterative_TwoStacksVersion()
{
List<int> nodes = new List<int>();
if (null != this._root)
{
Stack<BinaryTreeNode> postOrderStack = new Stack<BinaryTreeNode>();
Stack<BinaryTreeNode> rightLeftPreOrderStack = new Stack<BinaryTreeNode>();
rightLeftPreOrderStack.Push(this._root);
while(rightLeftPreOrderStack.Count > 0)
{
var top = rightLeftPreOrderStack.Pop();
postOrderStack.Push(top);
if(top.Left != null)
{
rightLeftPreOrderStack.Push(top.Left);
}
if(top.Right != null)
{
rightLeftPreOrderStack.Push(top.Right);
}
}
while(postOrderStack.Count > 0)
{
var top = postOrderStack.Pop();
nodes.Add(top.Element);
}
}
return this.ListToString(nodes);
}
Com o sinalizador visitado em C # (.net):
public string PostOrderIterative()
{
List<int> nodes = new List<int>();
if (null != this._root)
{
BinaryTreeNode iterativeNode = null;
Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
stack.Push(this._root);
while(stack.Count > 0)
{
iterativeNode = stack.Pop();
if(iterativeNode.visted)
{
//reset the flag, for further traversals
iterativeNode.visted = false;
nodes.Add(iterativeNode.Element);
}
else
{
iterativeNode.visted = true;
stack.Push(iterativeNode);
if(iterativeNode.Right != null)
{
stack.Push(iterativeNode.Right);
}
if(iterativeNode.Left != null)
{
stack.Push(iterativeNode.Left);
}
}
}
}
return this.ListToString(nodes);
}
As definições:
class BinaryTreeNode
{
public int Element;
public BinaryTreeNode Left;
public BinaryTreeNode Right;
public bool visted;
}
string ListToString(List<int> list)
{
string s = string.Join(", ", list);
return s;
}
Unidade de Testes
[TestMethod]
public void PostOrderTests()
{
int[] a = { 13, 2, 18, 1, 5, 17, 20, 3, 6, 16, 21, 4, 14, 15, 25, 22, 24 };
BinarySearchTree bst = new BinarySearchTree();
foreach (int e in a)
{
string s1 = bst.PostOrderRecursive();
string s2 = bst.PostOrderIterativeWithVistedFlag();
string s3 = bst.PostOrderIterative();
string s4 = bst.PostOrderIterative_WikiVersion();
string s5 = bst.PostOrderIterative_TwoStacksVersion();
Assert.AreEqual(s1, s2);
Assert.AreEqual(s2, s3);
Assert.AreEqual(s3, s4);
Assert.AreEqual(s4, s5);
bst.Add(e);
bst.Delete(e);
bst.Add(e);
s1 = bst.PostOrderRecursive();
s2 = bst.PostOrderIterativeWithVistedFlag();
s3 = bst.PostOrderIterative();
s4 = bst.PostOrderIterative_WikiVersion();
s5 = bst.PostOrderIterative_TwoStacksVersion();
Assert.AreEqual(s1, s2);
Assert.AreEqual(s2, s3);
Assert.AreEqual(s3, s4);
Assert.AreEqual(s4, s5);
}
Debug.WriteLine(string.Format("PostOrderIterative: {0}", bst.PostOrderIterative()));
Debug.WriteLine(string.Format("PostOrderIterative_WikiVersion: {0}", bst.PostOrderIterative_WikiVersion()));
Debug.WriteLine(string.Format("PostOrderIterative_TwoStacksVersion: {0}", bst.PostOrderIterative_TwoStacksVersion()));
Debug.WriteLine(string.Format("PostOrderIterativeWithVistedFlag: {0}", bst.PostOrderIterativeWithVistedFlag()));
Debug.WriteLine(string.Format("PostOrderRecursive: {0}", bst.PostOrderRecursive()));
}
Python com 1 pilha e nenhuma bandeira:
def postorderTraversal(self, root):
ret = []
if not root:
return ret
stack = [root]
current = None
while stack:
previous = current
current = stack.pop()
if previous and ((previous is current) or (previous is current.left) or (previous is current.right)):
ret.append(current.val)
else:
stack.append(current)
if current.right:
stack.append(current.right)
if current.left:
stack.append(current.left)
return ret
E o que é melhor é com declarações semelhantes, a fim travessia funciona também
def inorderTraversal(self, root):
ret = []
if not root:
return ret
stack = [root]
current = None
while stack:
previous = current
current = stack.pop()
if None == previous or previous.left is current or previous.right is current:
if current.right:
stack.append(current.right)
stack.append(current)
if current.left:
stack.append(current.left)
else:
ret.append(current.val)
return ret
Eu não adicionou a classe nó como não é particularmente relevante ou quaisquer casos de teste, deixando os como um exercício para o leitor etc.
void postOrderTraversal(node* root)
{
if(root == NULL)
return;
stack<node*> st;
st.push(root);
//store most recent 'visited' node
node* prev=root;
while(st.size() > 0)
{
node* top = st.top();
if((top->left == NULL && top->right == NULL))
{
prev = top;
cerr<<top->val<<" ";
st.pop();
continue;
}
else
{
//we can check if we are going back up the tree if the current
//node has a left or right child that was previously outputted
if((top->left == prev) || (top->right== prev))
{
prev = top;
cerr<<top->val<<" ";
st.pop();
continue;
}
if(top->right != NULL)
st.push(top->right);
if(top->left != NULL)
st.push(top->left);
}
}
cerr<<endl;
}
tempo de execução O (n) - todos os nós precisam ser visitada E espaço O (n) - para a pilha, pior árvore caso é uma lista ligada única linha
É muito bom ver tantas abordagens animadas para este problema. Muito inspirador de fato!
Me deparei com este tópico de procura de uma solução iterativa simples para apagar todos os nós no meu implementação de árvore binária. Eu tentei alguns deles, e eu tentei algo que se encontra semelhante em outros lugares na Net, mas nenhum deles era realmente para o meu gosto.
A coisa é, eu estou desenvolvendo um módulo de indexação banco de dados para um propósito muito específico (Bitcoin Blockchain indexação), e meu dados são armazenados no disco, não em RAM. Eu troco em páginas conforme necessário, fazendo o meu próprio gerenciamento de memória. É mais lento, mas rápido o suficiente para o efeito, e com ter de armazenamento em disco em vez de RAM, não tenho rolamentos religiosas contra o desperdício de espaço (discos rígidos são baratos).
Por essa razão meus nós em minha árvore binária tem ponteiros do pai. Isso é (todos) o espaço extra que estou falando. Eu preciso os pais porque eu preciso iterate tanto ascendente e descendente através da árvore para diversos fins.
Tendo isso em minha mente, eu rapidamente escreveu um pequeno pedaço de pseudo-código sobre como isso poderia ser feito, ou seja, um pós-ordem travessia eliminar nós na mosca. É implementado e testado, e tornou-se uma parte da minha solução. E é muito rápido também.
A coisa é:. Fica muito, muito, simples quando nós têm ponteiros pai, e, além disso desde que eu posso nulo a ligação do pai para o "justo partiu" nó
Aqui está o pseudo-código para exclusão pós-ordem iterativo:
Node current = root;
while (current)
{
if (current.left) current = current.left; // Dive down left
else if (current.right) current = current.right; // Dive down right
else
{
// Node "current" is a leaf, i.e. no left or right child
Node parent = current.parent; // assuming root.parent == null
if (parent)
{
// Null out the parent's link to the just departing node
if (parent.left == current) parent.left = null;
else parent.right = null;
}
delete current;
current = parent;
}
}
root = null;
Se você está interessado em uma abordagem mais teórica para codificação coleções complexas (como o meu árvore binária, que é realmente um auto-equilíbrio vermelho-preto-árvore), então confira estes links:
http://opendatastructures.org/versions/edition-0.1 e / ODS-java / 6_2_BinarySearchTree_Unbala.html http://opendatastructures.org/versions/edition-0.1e/ods -java / 9_2_RedBlackTree_Simulated_.html https://www.cs.auckland.ac.nz/software/AlgAnim /red_black.html
Happy codificação: -)
Søren Fog http://iprotus.eu/
Profundidade primeira, ordem post, não recursiva, sem pilha
Quando você tem parent:
node_t
{
left,
right
parent
}
traverse(node_t rootNode)
{
bool backthreading = false
node_t node = rootNode
while(node <> 0)
if (node->left <> 0) and backthreading = false then
node = node->left
continue
endif
>>> process node here <<<
if node->right <> 0 then
lNode = node->right
backthreading = false
else
node = node->parent
backthreading = true
endif
endwhile
1.1 Criar uma pilha vazia
2.1 Do seguinte, enquanto raiz não é NULL
a) Push root's right child and then root to stack.
b) Set root as root's left child.
2.2 Pop um item da pilha e defini-lo como root.
a) If the popped item has a right child and the right child
is at top of stack, then remove the right child from stack,
push the root back and set root as root's right child.
b) Else print root's data and set root as NULL.
2.3 Repita os passos 2.1 e 2.2, enquanto a pilha não está vazia.
Aqui está a implementação Java com duas pilhas
public static <T> List<T> iPostOrder(BinaryTreeNode<T> root) {
if (root == null) {
return Collections.emptyList();
}
List<T> result = new ArrayList<T>();
Deque<BinaryTreeNode<T>> firstLevel = new LinkedList<BinaryTreeNode<T>>();
Deque<BinaryTreeNode<T>> secondLevel = new LinkedList<BinaryTreeNode<T>>();
firstLevel.push(root);
while (!firstLevel.isEmpty()) {
BinaryTreeNode<T> node = firstLevel.pop();
secondLevel.push(node);
if (node.hasLeftChild()) {
firstLevel.push(node.getLeft());
}
if (node.hasRightChild()) {
firstLevel.push(node.getRight());
}
}
while (!secondLevel.isEmpty()) {
result.add(secondLevel.pop().getData());
}
return result;
}
Aqui está os testes de unidade
@Test
public void iterativePostOrderTest() {
BinaryTreeNode<Integer> bst = BinaryTreeUtil.<Integer>fromInAndPostOrder(new Integer[]{4,2,5,1,6,3,7}, new Integer[]{4,5,2,6,7,3,1});
assertThat(BinaryTreeUtil.iPostOrder(bst).toArray(new Integer[0]), equalTo(new Integer[]{4,5,2,6,7,3,1}));
}
/**
* This code will ensure holding of chain(links) of nodes from the root to till the level of the tree.
* The number of extra nodes in the memory (other than tree) is height of the tree.
* I haven't used java stack instead used this ParentChain.
* This parent chain is the link for any node from the top(root node) to till its immediate parent.
* This code will not require any altering of existing BinaryTree (NO flag/parent on all the nodes).
*
* while visiting the Node 11; ParentChain will be holding the nodes 9 -> 8 -> 7 -> 1 where (-> is parent)
*
* 1
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
2 7
/ \ /
/ \ /
/ \ /
/ \ /
3 6 8
/ \ /
/ \ /
4 5 9
/ \
10 11
*
* @author ksugumar
*
*/
public class InOrderTraversalIterative {
public static void main(String[] args) {
BTNode<String> rt;
String[] dataArray = {"1","2","3","4",null,null,"5",null,null,"6",null,null,"7","8","9","10",null,null,"11",null,null,null,null};
rt = BTNode.buildBTWithPreOrder(dataArray, new Counter(0));
BTDisplay.printTreeNode(rt);
inOrderTravesal(rt);
}
public static void postOrderTravesal(BTNode<String> root) {
ParentChain rootChain = new ParentChain(root);
rootChain.Parent = new ParentChain(null);
while (root != null) {
//Going back to parent
if(rootChain.leftVisited && rootChain.rightVisited) {
System.out.println(root.data); //Visit the node.
ParentChain parentChain = rootChain.Parent;
rootChain.Parent = null; //Avoid the leak
rootChain = parentChain;
root = rootChain.root;
continue;
}
//Traverse Left
if(!rootChain.leftVisited) {
rootChain.leftVisited = true;
if (root.left != null) {
ParentChain local = new ParentChain(root.left); //It is better to use pool to reuse the instances.
local.Parent = rootChain;
rootChain = local;
root = root.left;
continue;
}
}
//Traverse RIGHT
if(!rootChain.rightVisited) {
rootChain.rightVisited = true;
if (root.right != null) {
ParentChain local = new ParentChain(root.right); //It is better to use pool to reuse the instances.
local.Parent = rootChain;
rootChain = local;
root = root.right;
continue;
}
}
}
}
class ParentChain {
BTNode<String> root;
ParentChain Parent;
boolean leftVisited = false;
boolean rightVisited = false;
public ParentChain(BTNode<String> node) {
this.root = node;
}
@Override
public String toString() {
return root.toString();
}
}
void display_without_recursion(struct btree **b)
{
deque< struct btree* > dtree;
if(*b)
dtree.push_back(*b);
while(!dtree.empty() )
{
struct btree* t = dtree.front();
cout << t->nodedata << " " ;
dtree.pop_front();
if(t->right)
dtree.push_front(t->right);
if(t->left)
dtree.push_front(t->left);
}
cout << endl;
}
import java.util.Stack;
class Practice
{
public static void main(String arr[])
{
Practice prc = new Practice();
TreeNode node1 = (prc).new TreeNode(1);
TreeNode node2 = (prc).new TreeNode(2);
TreeNode node3 = (prc).new TreeNode(3);
TreeNode node4 = (prc).new TreeNode(4);
TreeNode node5 = (prc).new TreeNode(5);
TreeNode node6 = (prc).new TreeNode(6);
TreeNode node7 = (prc).new TreeNode(7);
node1.left = node2;
node1.right = node3;
node2.left = node4;
node2.right = node5;
node3.left = node6;
node3.right = node7;
postOrderIteratively(node1);
}
public static void postOrderIteratively(TreeNode root)
{
Stack<Entry> stack = new Stack<Entry>();
Practice prc = new Practice();
stack.push((prc).new Entry(root, false));
while (!stack.isEmpty())
{
Entry entry = stack.pop();
TreeNode node = entry.node;
if (entry.flag == false)
{
if (node.right == null && node.left == null)
{
System.out.println(node.data);
} else
{
stack.push((prc).new Entry(node, true));
if (node.right != null)
{
stack.push((prc).new Entry(node.right, false));
}
if (node.left != null)
{
stack.push((prc).new Entry(node.left, false));
}
}
} else
{
System.out.println(node.data);
}
}
}
class TreeNode
{
int data;
int leafCount;
TreeNode left;
TreeNode right;
public TreeNode(int data)
{
this.data = data;
}
public int getLeafCount()
{
return leafCount;
}
public void setLeafCount(int leafCount)
{
this.leafCount = leafCount;
}
public TreeNode getLeft()
{
return left;
}
public void setLeft(TreeNode left)
{
this.left = left;
}
public TreeNode getRight()
{
return right;
}
public void setRight(TreeNode right)
{
this.right = right;
}
@Override
public String toString()
{
return "" + this.data;
}
}
class Entry
{
Entry(TreeNode node, boolean flag)
{
this.node = node;
this.flag = flag;
}
TreeNode node;
boolean flag;
@Override
public String toString()
{
return node.toString();
}
}
}
Eu estava procurando por um trecho de código que executa bem e é simples de personalizar. árvores de rosca não são “simples”. solução de pilha dupla requer memória O (n). solução LeetCode e solução de TCB tem verificações extras e empurra ...
Aqui está um algoritmo clássico traduzido em C que funcionou para mim:
void postorder_traversal(TreeNode *p, void (*visit)(TreeNode *))
{
TreeNode *stack[40]; // simple C stack, no overflow check
TreeNode **sp = stack;
TreeNode *last_visited = NULL;
for (; p != NULL; p = p->left)
*sp++ = p;
while (sp != stack) {
p = sp[-1];
if (p->right == NULL || p->right == last_visited) {
visit(p);
last_visited = p;
sp--;
} else {
for (p = p->right; p != NULL; p = p->left)
*sp++ = p;
}
}
}
IMHO este algoritmo é mais fácil de seguir do que com bom desempenho e legível wikipedia.org / Tree_traversal pseudocódigo. Para mais detalhes gloriosos ver respostas para exercícios árvore binária em Knuth Volume 1.
Aqui está uma versão Python também ::
class Node:
def __init__(self,data):
self.data = data
self.left = None
self.right = None
def postOrderIterative(root):
if root is None :
return
s1 = []
s2 = []
s1.append(root)
while(len(s1)>0):
node = s1.pop()
s2.append(node)
if(node.left!=None):
s1.append(node.left)
if(node.right!=None):
s1.append(node.right)
while(len(s2)>0):
node = s2.pop()
print(node.data)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
postOrderIterative(root)
Aqui está a saída ::
Assim você pode usar uma pilha para fazer um percurso ordem pós.
private void PostOrderTraversal(Node pos) {
Stack<Node> stack = new Stack<Node>();
do {
if (pos==null && (pos=stack.peek().right)==null) {
for (visit(stack.peek()); stack.pop()==(stack.isEmpty()?null:stack.peek().right); visit(stack.peek())) {}
} else if(pos!=null) {
stack.push(pos);
pos=pos.left;
}
} while (!stack.isEmpty());
}
A lógica de Pós travessia fim sem usar recursão
Em Postorder traversal, a ordem de processamento é left-right-current. Então, precisamos visitar a seção esquerda antes de visitar outras partes. Vamos tentar atravessar até a árvore como esquerda quanto possível para cada nó da árvore. Para cada nó atual, se a criança direita está presente, em seguida, empurre-o para a pilha antes de empurrar o nó atual, enquanto raiz não é NULL / Nenhum. Agora pop um nó da pilha e verificar se a criança direita desse nó existe ou não. Se existir, em seguida, verificar se é mesmo que o elemento do topo ou não. Se eles são os mesmos, então isso indica que não é feito com parte direita ainda, então antes de processar o nó atual que temos para processar a parte direita e para isso colocar o elemento superior (criança direita) e empurre a parte de trás nó atual na pilha . Em cada tempo nossa cabeça é o elemento estourado. Se o elemento atual não é o mesmo que a parte superior e cabeça não é NULL, em seguida, estamos a fazer com tanto da esquerda e parte direita então agora podemos processar o nó atual. Temos de repetir os passos anteriores até que a pilha está vazia.
def Postorder_iterative(head):
if head is None:
return None
sta=stack()
while True:
while head is not None:
if head.r:
sta.push(head.r)
sta.push(head)
head=head.l
if sta.top is -1:
break
head = sta.pop()
if head.r is not None and sta.top is not -1 and head.r is sta.A[sta.top]:
x=sta.pop()
sta.push(head)
head=x
else:
print(head.val,end = ' ')
head=None
print()
Dois métodos para executar Post Ordenar Traversal sem recursão:
1. Usando Um HashSet de Visitou Nodes e Uma pilha de retrocesso:
private void postOrderWithoutRecursion(TreeNode root) {
if (root == null || root.left == null && root.right == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
Set<TreeNode> visited = new HashSet<>();
while (!stack.empty() || root != null) {
if (root != null) {
stack.push(root);
visited.add(root);
root = root.left;
} else {
root = stack.peek();
if (root.right == null || visited.contains(root.right)) {
System.out.print(root.val+" ");
stack.pop();
root = null;
} else {
root = root.right;
}
}
}
}
Tempo Complexidade: O (n)
Espaço Complexidade: O (2n)
2. Usando o método de árvore Alterando:
private void postOrderWithoutRecursionAlteringTree(TreeNode root) {
if (root == null || root.left == null && root.right == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
while (!stack.empty() || root != null) {
if (root != null) {
stack.push(root);
root = root.left;
} else {
root = stack.peek();
if (root.right == null) {
System.out.print(root.val+" ");
stack.pop();
root = null;
} else {
TreeNode temp = root.right;
root.right = null;
root = temp;
}
}
}
}
Tempo Complexidade: O (n)
Espaço Complexidade: O (n)
TreeNode Classe:
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) {
val = x;
}
}
Aqui está uma pequena (o caminhante é de 3 linhas) versão que eu precisava para escrever em Python para uma árvore geral. Claro, trabalha para uma árvore binária mais limitado também. Árvore é uma tupla do nó e lista de crianças. Ele só tem uma pilha. Exemplo de uso mostrada.
def postorder(tree):
def do_something(x): # Your function here
print(x),
def walk_helper(root_node, calls_to_perform):
calls_to_perform.append(partial(do_something, root_node[0]))
for child in root_node[1]:
calls_to_perform.append(partial(walk_helper, child, calls_to_perform))
calls_to_perform = []
calls_to_perform.append(partial(walk_helper, tree, calls_to_perform))
while calls_to_perform:
calls_to_perform.pop()()
postorder(('a', [('b', [('c', []), ('d', [])])]))
d c b um
A solução mais simples, pode parecer que não é a melhor resposta, mas é fácil de entender. E eu acredito que se você compreendeu a solução, então você pode modificá-lo para fazer a melhor solução possível
// usando duas pilhas
public List<Integer> postorderTraversal(TreeNode root){
Stack<TreeNode> st=new Stack<>();
Stack<TreeNode> st2=new Stack<>();
ArrayList<Integer> al = new ArrayList<Integer>();
if(root==null)
return al;
st.push(root); //push the root to 1st stack
while(!st.isEmpty())
{
TreeNode curr=st.pop();
st2.push(curr);
if(curr.left!=null)
st.push(curr.left);
if(curr.right!=null)
st.push(curr.right);
}
while(!st2.isEmpty())
al.add(st2.pop().val);
//this ArrayList contains the postorder traversal
return al;
}
