Post ordine di attraversamento di un albero binario senza ricorsione
https://stackoverflow.com/questions/1294701
-
18-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Che cosa è l'algoritmo per fare un post ordine di attraversamento di un albero binario SENZA utilizzando la ricorsione?
Soluzione
Ecco un link che fornisce altre due soluzioni senza l'uso di bandiere visitati.
https://leetcode.com/problems/binary-tree-postorder-traversal /
Questa è ovviamente una soluzione di stack-based a causa della mancanza di puntatore genitore nell'albero. (Non avremmo bisogno di uno stack se c'è puntatore genitore).
Ci spingere il nodo radice alla pila prima. Mentre la pila non è vuota, continuiamo a spingere il figlio sinistro del nodo dalla parte superiore della pila. Se il bambino sinistra non esiste, spingiamo il suo figlio destro. Se si tratta di un nodo foglia, elaboriamo il nodo e pop dallo stack.
Usiamo anche una variabile per tenere traccia di un nodo precedentemente attraversato. Lo scopo è quello di determinare se l'attraversamento sta scendendo / ascendente l'albero, e possiamo anche sapere se salire da sinistra / destra.
Se si sale l'albero da sinistra, non vorremmo spingere nuovamente il suo figlio sinistro allo stack e deve continuare salire verso il basso l'albero se il suo figlio destro esiste. Se si sale l'albero da destra, dovremmo elaborarla e pop dallo stack.
Ci sarebbe elaborare il nodo e pop dallo stack in questi 3 casi:
- Il nodo è un nodo foglia (senza figli)
- Abbiamo appena attraversiamo l'albero da sinistra e nessun figlio destro esistiamo.
- Abbiamo appena attraversiamo l'albero da destra.
Altri suggerimenti
Ecco la versione con una pila e senza bandiera visitato:
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);
}
}
}
}
Ecco un esempio da 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()
Questo è l'approccio che uso per iterativo, post-ordine di attraversamento. Mi piace questo approccio, perché:
- Si gestisce solo una singola transizione per loop-ciclo, quindi è facile da seguire.
- Una soluzione simile funziona per in-ordine e attraversamenti pre-ordine
Codice:
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();
}
}
}
Spiegazione:
È possibile pensare ai passaggi come questo:
- Prova SINISTRA
- se esiste sinistra-nodo: Prova di nuovo a sinistra
- se non-nodo non esiste: Prova DESTRA
- Prova DESTRA
- Se un nodo diritto esiste: Prova sinistra Da lì
- Se non esiste alcun diritto, sei in una foglia: Prova CORR
- Prova CORR
- Stampa nodo corrente
- Tutti i nodi di seguito sono state eseguite (post-ordine): Prova UP
- Prova UP
- Se il nodo è radice, non c'è UP, quindi EXIT
- Se in arrivo da sinistra, Prova DESTRA
- Se in arrivo da destra, Prova CORR
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);
}
}
Ecco una soluzione in C ++ che non richiede alcun deposito per contabilità nell'albero.
Invece, utilizza due pile. Uno per aiutare noi attraversiamo e un altro per memorizzare i nodi in modo che possiamo fare un post attraversamento di loro.
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";
}
// la versione di Java con la bandiera
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;
}
}
Si prega di vedere questa implementazione completa di Java. Basta copiare il codice e incollarlo nel vostro compilatore. E funziona bene.
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();
}
}
Eccomi incollare diverse versioni in c# (.net) per riferimento:(in ordine iterativo di attraversamento si può fare riferimento a: Mi aiuti a capire Inorder Attraversamento senza usare la ricorsione)
- wiki (http://en.wikipedia.org/wiki/Post-order%5Ftraversal#Implementations) (elegante)
- Un'altra versione del singolo stack (#1 e #2:utilizza fondamentalmente il fatto che nel post ordine di attraversamento il bambino vero nodo è visitato prima di visitare il nodo effettivo, abbiamo semplicemente fare affidamento sul controllo che se lo stack superiore destro del bambino è infatti l'ultimo post ordine di attraversamento del nodo è stata visitata - ho aggiunto commenti in seguito frammenti di codice per i dettagli)
- Utilizza Due pile versione (rif: http://www.geeksforgeeks.org/iterative-postorder-traversal/) (più facile:fondamentalmente post ordine di attraversamento inversa è nulla, ma pre ordine di attraversamento con un semplice tweak che diritto nodo visitato per primo, e poi a sinistra del nodo)
- Utilizzando visitatore bandiera (facile)
- Unit Test
~
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);
}
Qui è il post ordine di attraversamento con uno stack (la mia versione)
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);
}
Utilizza due pile
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);
}
Con visitata bandiera in 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);
}
Le definizioni:
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;
}
Unit Test
[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 con 1 stack e nessuna bandiera:
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 cosa c'è di meglio è con dichiarazioni simili, al fine di attraversamento lavora troppo
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
Non ho aggiunto la classe nodo di come la sua non particolarmente eventuali casi di test in questione o, lasciando quelli come esercitazione per il lettore, ecc.
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;
}
in esecuzione tempo O (n) - tutti i nodi devono essere visitato E lo spazio O (n) - per lo stack, peggiore albero caso è una lista collegata sola riga
E 'molto bello vedere così tanti approcci vivaci a questo problema. Molto stimolante anzi!
Mi sono imbattuto in questo tema la ricerca di una soluzione semplice iterativa per l'eliminazione di tutti i nodi nella mia implementazione albero binario. Ho provato alcuni di loro, e ho provato qualcosa di simile si trova altrove in Rete, ma nessuno di loro erano davvero di mio gradimento.
Il fatto è che sto sviluppando un modulo di database di indicizzazione per uno scopo ben preciso (Bitcoin Blockchain indicizzazione), e il mio dati vengono memorizzati su disco, non in RAM. Ho swap in pagine come necessario, fare le mie gestione della memoria. E 'più lento, ma abbastanza veloce per lo scopo, e di avere memorizzazione su disco invece di RAM, non ho cuscinetti religiose contro spazio spreco (dischi rigidi sono a buon mercato).
Per questo motivo i miei nodi nel mio albero binario hanno puntatori genitore. Questo è (tutto) lo spazio extra di cui sto parlando. Ho bisogno dei genitori perché ho bisogno di iterare sia ascendenti e discendenti attraverso l'albero per vari scopi.
Avere che nella mia mente, ho scritto rapidamente un piccolo pezzo di pseudo-codice su come potrebbe essere fatto, vale a dire, un attraversamento post-ordine di eliminare i nodi al volo. E 'implementato e testato, ed è diventato una parte della mia soluzione. Ed è abbastanza veloce anche.
Il fatto è:. Diventa davvero, davvero, semplice quando i nodi hanno puntatori genitore, e, inoltre, dato che posso nullo fuori legame del genitore al nodo "solo andata"
Ecco il pseudo-codice per l'eliminazione iterativo post-ordine:
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 siete interessati a un approccio più teorico alla codifica collezioni complessi (come il mio albero binario, che è davvero un auto-bilanciamento rosso-nero-albero), quindi controllare questi link:
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
codifica Felice: -)
Søren Nebbia http://iprotus.eu/
Profondità prima, vaglia postale, non ricorsiva, senza pila
Quando si dispone di genitore:
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 Creare uno stack vuoto
2.1 Fare seguente mentre root non è NULL
a) Push root's right child and then root to stack.
b) Set root as root's left child.
2.2 Pop un elemento dalla pila e impostarlo come 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 Ripetere i punti 2.1 e 2.2, mentre pila non è vuota.
Qui è l'implementazione Java con due pile
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;
}
Ecco i test di unità
@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();
}
}
}
Ero alla ricerca di un frammento di codice che si comporta bene ed è semplice da personalizzare. alberi filettati non sono “semplici”. soluzione doppio camino richiede O (n) della memoria. soluzione LeetCode e la soluzione da TCB avere controlli extra e spinge ...
Ecco un algoritmo classico tradotto in C che ha funzionato per me:
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 questo algoritmo è più facile da seguire rispetto ben performante e leggibile wikipedia.org / Tree_traversal pseudocodice. Per i dettagli vedere gloriosi risposte a esercizi di alberi binari in di Knuth Volume 1.
Ecco una versione di Python troppo ::
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)
Ecco l'output ::
Quindi, è possibile utilizzare uno stack per fare un attraversamento ordine post.
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());
}
La logica di Post ordine di attraversamento senza l'utilizzo di ricorsione
Nel Postorder traversal, l'ordine di elaborazione è left-right-current. Quindi abbiamo bisogno di visitare la sezione sinistra prima di visitare altre parti. Cercheremo di attraversare verso il basso per l'albero come sinistra possibile per ogni nodo dell'albero. Per ogni nodo corrente, se il bambino destra è presente spingerlo nella pila prima di premere il nodo corrente mentre radice non è NULL / Nessuno. Ora pop un nodo dalla pila e controllare se il figlio destro di quel nodo esiste o no. Se esiste, allora controllare se è uguale dell'elemento superiore o meno. Se essi sono gli stessi allora indica che non abbiamo ancora finito con la parte destra ancora, quindi prima di elaborare il nodo corrente dobbiamo elaborare la parte destra e per questo Estrae l'elemento superiore (figlio destro) e spingere il nodo corrente indietro nella pila . Ad ogni tempo la nostra testa è l'elemento spuntato. Se l'elemento corrente non è la stessa come la parte superiore e la testa non è NULL allora abbiamo finito sia con la sezione destra ora possiamo elaborare il nodo corrente e sinistro. Dobbiamo ripetere le fasi precedenti fino alla pila è vuota.
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()
Due metodi per eseguire Messaggio ordine di attraversamento senza ricorsione:
1. Utilizzo di un HashSet dei nodi visitati e una pila per backtracking:
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 Complessità: O (n)
Spazio Complessità: O (2n)
2. Usando il metodo Albero Altering:
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 Complessità: O (n)
Spazio Complessità: O (n)
TreeNode Classe:
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) {
val = x;
}
}
Ecco un breve (il girello è 3 righe) Versione che avevo bisogno di scrivere in Python per un albero generale. Naturalmente, funziona per un albero binario più limitato troppo. Tree è una tupla del nodo e la lista dei figli. Ha solo una pila. utilizzo di esempio mostrato.
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 un
La soluzione più semplice, può sembrare non è la risposta migliore, ma è facile da capire. E credo che se si è capito la soluzione quindi è possibile modificarlo per rendere la migliore soluzione possibile
// usando due pile
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;
}
