Beitrag Order Traversal von binären Baum ohne Rekursion
https://stackoverflow.com/questions/1294701
-
18-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Was ist der Algorithmus einen Beitrag, um Traversal eines binären Baum zu tun OHNE mit Rekursion?
Lösung
Hier ist ein Link, die ohne Verwendung von besuchten Fahnen zwei andere Lösungen.
https://leetcode.com/problems/binary-tree-postorder-traversal /
Das ist natürlich ein Stack-basierten Lösung aufgrund des Fehlens von Abstammungszeiger im Baum. (Wir würden nicht einen Stapel benötigen, wenn es übergeordnete Zeiger).
Wir würden den Stammknoten auf den Stack schieben. Während der Stapel nicht leer ist, halten wir das linke Kind des Knotens von der Oberseite des Stapels schieben. Wenn das linke Kind nicht vorhanden ist, drücken wir ihr Recht Kind. Wenn es ein Blattknoten ist, verarbeiten wir den Knoten und Pop es vom Stapel.
Wir verwenden auch eine variable Spur eines zuvor durchquerten Knoten zu halten. Der Zweck ist, zu bestimmen, ob die Traversal absteigt / den Baum aufsteigend, und wir können auch wissen, ob es von links / rechts aufsteigen.
Wenn wir den Baum von links aufsteigen, würden wir nicht sein linkes Kind wollen wieder auf den Stapel schieben und weiterhin den Baum, wenn sein rechtes Kind existiert steigen nach unten. Wenn wir den Baum von rechts aufsteigen, sollten wir sie verarbeiten und es vom Stapel Pop.
Wir würden die Knoten verarbeiten und aus dem Stapel in diesen drei Fällen Pop:
- Der Knoten ist ein Blattknoten (keine Kinder)
- Wir durchqueren bis nur den Baum von links und rechts kein Kind vorhanden sind.
- Wir durchqueren bis nur den Baum von der rechten Seite.
Andere Tipps
Hier ist die Version mit einem Stapel und ohne Begegnungsflag:
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);
}
}
}
}
Hier ist ein Beispiel von 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()
Dies ist der Ansatz, den ich für iterativ, Post-Order Traversal verwenden. Ich mag diesen Ansatz, weil:
- Sie übernimmt nur einen einzigen Übergang pro Loop-Zyklus, so ist es einfach zu folgen.
- Eine ähnliche Lösung arbeitet für in Ordnung und Vorbestellung Traversierungen
Code:
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();
}
}
}
Erklärung:
Sie können über die Schritte, so denken:
- Versuchen Sie LINKS
- , wenn links Knoten vorhanden ist: Versuchen Sie erneut links
- , wenn links Knoten existiert nicht: Versuchen Sie RECHTS
- Versuchen Sie RECHTS
- Wenn ein rechter Knoten vorhanden ist: Versuchen Sie von dort links
- Wenn kein Recht vorhanden ist, Sie auf einem Blatt: Versuchen CURR
- Versuchen CURR
- Drucke aktuelle Knoten
- Alle unten Knoten ausgeführt wurden (Post-Order): Versuchen Sie UP
- Versuchen Sie UP
- Wenn der Knoten root ist, gibt es keine UP, so EXIT
- Wenn von links kommen, versuchen Sie RECHTS
- Wenn von rechts kommen, versuchen Sie 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);
}
}
Hier ist eine Lösung in C ++, die keinen Speicher für die Buchhaltung im Baum benötigt.
Stattdessen verwendet es zwei Stapel. Eine helfen, uns zu durchqueren und eine andere, die Knoten zu speichern, so dass wir einen Beitrag Traversal von ihnen tun kann.
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";
}
// Die Java-Version mit Fahne
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;
}
}
Bitte beachten Sie diese vollständige Java-Implementierung. Kopieren Sie einfach den Code und fügen Sie ihn in Ihrem Compiler. Es wird funktionieren.
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();
}
}
Hier bin ich Einfügen verschiedene Versionen in C # (.NET) als Referenz: (Für in Ordnung iterative Traversal können Sie beziehen sich auf: Hilf mir zu verstehen Inorder Traversal ohne Rekursion verwenden)
- Wiki ( http://en.wikipedia.org/wiki/Post -dem% 5Ftraversal # Implementations ) (elegant)
- Eine andere Version des Single-Stack (# 1 und # 2: verwendet grundsätzlich die Tatsache, dass in der Post um Traversal das richtige Kind-Knoten vor dem Besuch der eigentlichen Knoten besucht wird - so verlassen wir uns einfach auf dem Scheck, dass, wenn Stapel oben rechte Kind ist in der Tat die letzte Post Order Traversal Knoten das ist besucht - ich habe hinzugefügt Kommentare in folgendem Code-Schnipsel für weitere Details)
- Verwenden von Zwei Stapel Version (ref: http://www.geeksforgeeks.org/iterative -postorder-Traversal / ) (Einfacher: im Grunde um Traversal Reverse Post ist nichts anderes als Vorbestellung Traversal mit einem einfachen zwicken, dass richtiger Knoten zuerst besucht wird, und dann nach links Knoten)
- Verwenden von Besuchern Flagge (leicht)
- Unit Tests
~
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);
}
Hier ist Post Order Traversal mit einem Stapel (meine Version)
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);
}
Mit zwei Stapeln
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);
}
Mit Begegnungsflag 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);
}
Die Definitionen:
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 Tests
[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 mit 1 Stapel und keine Markierung:
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
Und was besser ist, ist mit ähnlichen Aussagen, um zu Traversal funktioniert
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
Ich habe nicht die Knotenklasse als nicht besonders relevant oder irgendwelche Testfälle hinzugefügt, etc. diejenigen als Übung für den Leser zu verlassen.
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;
}
Laufzeit O (n) - alle Knoten besucht werden sollen, müssen Und Raum O (n) - für den Stapel, Worst-Case-Baum ist eine einzige Zeile verknüpfte Liste
Es ist sehr schön, so viele temperament Ansätze für dieses Problem zu sehen. Sehr inspirierend in der Tat!
Ich kam in diesem Thema für eine einfache iterative Lösung der Suche nach allen Knoten in meinem Binärbaum Implementierung zu löschen. Ich habe versucht, einige von ihnen, und ich versuchte, etwas ähnliches an anderer Stelle im Netz gefunden, aber keiner von ihnen waren wirklich nach meinem Geschmack.
Die Sache ist, ich eine Datenbank Indexierungsmodul für einen ganz bestimmten Zweck (Bitcoin Blockchain Indizierung) und meine Daten auf Festplatte gespeichert, nicht im RAM entwickle. Ich tausche in Seiten wie nötig, meine eigene Speicherverwaltung zu tun. Es ist langsamer, aber schnell genug für den Zweck, und mit auf der Festplatte statt RAM-Speicher mit, ich habe keine religiösen Lager gegen Verschwendung Raum (Festplatten sind billig).
Aus diesem Grund meine Knoten in meinem Binärbaum haben Abstammungszeiger. Das ist (alle) die besonders viel Platz ich spreche. Ich brauche die Eltern, weil ich sowohl aufsteigend iterieren müssen und für verschiedene Zwecke durch den Baum absteigt.
Nachdem das in meinem Kopf, ich schrieb schnell ein kleines Stück Pseudo-Code unten, wie es getan werden könnte, das heißt, ein Post-Order-Traversal-Knoten im Fluge zu löschen. Es implementiert und getestet und wurde ein Teil meiner Lösung. Und es ist auch ziemlich schnell.
Die Sache ist. Es wird wirklich, wirklich, einfach, wenn Knoten Abstammungszeiger haben, und darüber hinaus, da ich die Eltern Link auf die Null zu bringen kann „gerade abgereist“ node
Hier ist der Pseudocode für iteratives Post-Order-Löschen:
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;
Wenn Sie Interesse an einem theoretischen Ansatz zur Codierung komplexe Sammlungen (wie mein binären Baum, der wirklich ein selbstausgleich ist rot-schwarz-Baum), dann holt sie sich:
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-Codierung: -)
Søren Nebel http://iprotus.eu/
Tiefe zuerst, Postauftrag, nicht rekursiv, ohne Stapel
Wenn Sie 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 Erstellen Sie einen leeren Stapel
2.1 folgende Maßnahmen während root nicht NULL
a) Push root's right child and then root to stack.
b) Set root as root's left child.
2.2 ein Element aus Stapel Pop und es als root gesetzt.
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 Wiederholen Sie die Schritte 2.1 und 2.2, während Stapel nicht leer ist.
Hier ist die Java-Implementierung mit zwei Stapeln
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;
}
Hier ist die Unit-Tests
@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();
}
}
}
Ich war auf der Suche nach einem Code-Snippet, das gut funktioniert und ist einfach zu gestalten. Gewinde Bäume sind nicht „einfach“. Doppelstapel Lösung erfordert O (n) Speicher. LeetCode Lösung und Lösung von tcb haben zusätzliche Kontrollen und drückt ...
Hier ist ein klassischer Algorithmus in C übersetzt, die für mich gearbeitet:
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 ist dieser Algorithmus einfacher zu folgen, als auch die Durchführung und lesbar wikipedia.org / Tree_traversal Pseudo-Code. Für glorreiche Details siehe Antworten auf Binärbaum Übungen in Knuths Volume 1.
Hier ist eine Python-Version zu ::
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)
Hier ist die Ausgabe ::
So können Sie einen Stapel können einen Beitrag Order Traversal zu tun.
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());
}
Die Logik der Beitrag Order Traversal ohne Rekursion mit
In Postorder traversal ist die Verarbeitungsreihenfolge left-right-current. Also müssen wir den linken Abschnitt besuchen, bevor andere Teile zu besuchen. Wir werden versuchen, den Baum zu durchqueren sich wie für jeden Knoten des Baumes wie möglich nach links. Für jeden aktuellen Knoten, wenn das richtige Kind es in den Stapel vorhanden dann schieben ist, bevor Sie die aktuellen Knoten schieben, während root nicht NULL / None ist. Nun öffnet sich ein Knoten aus dem Stapel und prüfen, ob das richtige Kind dieses Knotens vorhanden ist oder nicht. Wenn es vorhanden ist, dann prüfen, ob es als das oberste Element gleiche ist oder nicht. Wenn sie gleich sind, dann bedeutet dies, dass wir nicht mit rechten Teil noch getan werden, so vor den aktuellen Knoten Verarbeitung haben wir das richtige Teil zu verarbeiten und für das Pop das oberste Element (rechtes Kind) und drücken Sie den aktuellen Knoten zurück in den Stapel . Zu jeder Zeit ist unser Kopf knallt das Element. Wenn das aktuelle Element ist nicht das gleiche wie oben und Kopf nicht NULL ist, dann sind wir sowohl mit der linken und rechten Abschnitt so jetzt geschehen können wir den aktuellen Knoten verarbeiten. Wir haben die vorherigen Schritte zu wiederholen, bis der Stapel leer ist.
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()
Zwei Methoden Beitrag Order Traversal ohne Rekursion ausführen:
1. Verwenden Sie eine HashSet von besuchten Knoten und einen Stapel für Rückzieher:
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;
}
}
}
}
Zeitkomplexität: O (n)
Raum Komplexität: O (2n)
2. Mit Baum Altering-Methode:
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;
}
}
}
}
Zeitkomplexität: O (n)
Raum Komplexität: O (n)
TreeNode Klasse:
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) {
val = x;
}
}
Hier ein kurzes ist (der Wanderer ist 3 Zeilen) Version, die ich in Python für einen allgemeinen Baum zu schreiben benötigt. Natürlich arbeitet für eine begrenztere zu binären Baum. Baum ist ein Tupel des Knotens und die Liste der Kinder. Sie hat nur einen Stapel. Verwendungsbeispiel gezeigt.
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 a
Die einfachste Lösung, kann es nicht wie die beste Antwort aussehen, aber es ist leicht zu verstehen. Und ich glaube, wenn Sie die Lösung verstanden haben, dann können Sie es ändern, die bestmögliche Lösung zu machen
// mit zwei Stapeln
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;
}
