再帰を伴わないバイナリ ツリーのポストオーダー トラバース
https://stackoverflow.com/questions/1294701
-
18-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
バイナリツリーのポストオーダートラバーサルを行うためのアルゴリズムは何ですか それなし 再帰を使用しますか?
解決
ここに、訪問済みフラグを使用せずに他の 2 つのソリューションを提供するリンクがあります。
https://leetcode.com/problems/binary-tree-postorder-traversal/
ツリーには親ポインタがないため、これは明らかにスタックベースのソリューションです。(親ポインターがある場合はスタックは必要ありません)。
最初にルート ノードをスタックにプッシュします。スタックが空ではない間、スタックの一番上からノードの左側の子をプッシュし続けます。左の子が存在しない場合は、右の子をプッシュします。それがリーフ ノードの場合は、ノードを処理してスタックからポップします。
また、変数を使用して、以前に通過したノードを追跡します。目的は、トラバースがツリーを下降しているか上昇しているかを判断することであり、また、トラバースが左から上昇しているか右から上昇しているかを知ることもできます。
ツリーを左から登る場合、その左の子をスタックに再度プッシュすることは望ましくなく、右の子が存在する場合はツリーを下降し続ける必要があります。ツリーを右から登る場合は、それを処理してスタックからポップする必要があります。
次の 3 つのケースでは、ノードを処理してスタックからポップします。
- ノードはリーフ ノードです (子はありません)
- ツリーを左側から上にトラバースしているだけで、右側の子は存在しません。
- 右側から木をトラバースして登っていきます。
他のヒント
ここに1つのスタックを持つと訪れたフラグのないバージョンがあります
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);
}
}
}
}
ここでウィキペディアするからのサンプルです
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()
これは、私が反復的な順序後の走査に使用するアプローチです。私がこのアプローチを気に入っている理由は次のとおりです。
- ループサイクルごとに 1 つの遷移のみを処理するため、従うのは簡単です。
- 同様のソリューションは、順序どおりのトラバーサルと事前順序のトラバーサルにも機能します。
コード：
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();
}
}
}
説明：
次のような手順を考えることができます。
- 左に試してください
- 左ノードが存在する場合:もう一度左に試してください
- 左ノードが存在しない場合:右に試してください
- 右に試してください
- 正しいノードが存在する場合:そこから左に進んでみてください
- 権利が存在しない場合は、途方に暮れます。CURR を試してみる
- CURR を試してみる
- 現在のノードを出力する
- 以下のすべてのノードが実行されました (ポストオーダー)。やってみて
- やってみて
- ノードがルートの場合は UP がないので EXIT
- 左から来る場合は右を試してください
- 右から来る場合は、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);
}
}
ここでは、ツリー内の簿記のための任意のストレージを必要としないC ++でのソリューションです。
その代わりに、2つのスタックを使用しています。私たちはそれらのポストトラバーサルを行うことができますので、ノードを格納するために横断し、別のを助けるための一つ。
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";
}
//フラグを持つJavaのバージョン
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;
}
}
この完全なJava実装を参照してください。ただ、コードをコピーして、コンパイラに貼り付けます。これは、正常に動作します。
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();
}
}
ここでは、参考のために C# (.net) のさまざまなバージョンを貼り付けています。(順序どおりの反復走査については、以下を参照してください: 再帰を使用しない順序トラバーサルを理解するのに役立ちます)
- ウィキ (http://en.wikipedia.org/wiki/Post-order%5Ftraversal#Implementations) (エレガント)
- シングルスタックの別のバージョン（＃1および＃2：基本的に、ポストオーダートラバーサルでは、実際のノードを訪問する前に右側の子ノードが訪問されるという事実を使用します。したがって、スタックトップの右側の子が実際に訪問された最後のポストオーダートラバーサルノードであるかどうかのチェックに単純に依存します。詳細については、以下のコード スニペットのコメントを参照してください)
- 2 つのスタック バージョンを使用する (参照: http://www.geeksforgeeks.org/iterative-postorder-traversal/） （より簡単に：基本的に、ポストオーダートラバーサルリバースは、最初に右ノードにアクセスし、次に左ノードにアクセスするという簡単な調整を加えたプレオーダートラバーサルに他なりません）
- 訪問者フラグの使用 (簡単)
- 単体テスト
~
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);
}
これは1つのスタックを使用したポストオーダートラバーサルです（私のバージョン）
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);
}
2 つのスタックを使用する
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);
}
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);
}
定義:
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;
}
単体テスト
[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()));
}
1つのスタックなしフラグをPythonの
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
そして、何より良いのは、トラバーサルがあまりにも働くためには、同様のステートメントを使用することです。
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
Iは、リーダ等のためのエクササイズとしてそれらを残して、その特に関連または任意のテストケースはないとノードクラスを追加していない。
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;
}
時間O（n）を実行している - すべてのノードが訪問する必要があります そして、スペースO（N） - スタックのために、最悪の木は1行にリンクされたリストです。
これは、この問題に非常に多くの威勢のアプローチを見ることは非常にうれしいです。確かにかなり感激！
私は、バイナリツリーの実装では、すべてのノードを削除するための単純な反復解法を探して、このトピックに出くわしました。私はそれらのいくつかを試してみました、と私はネット上で他の場所に似た何かを試してみましたが、それらのどれも私の好みに合わせて、本当になかった。
の事は、私は非常に特定の目的（ビットコインBlockchainのインデックス作成）のために、データベースの索引付けモジュールを開発していますされ、そして私のデータがディスク上ではなく、RAMに格納されます。私は私自身のメモリ管理を行って、必要に応じてページ単位で交換します。それは遅くなりますが、目的のために十分に速く、そして代わりにRAMのディスク上のストレージを持って、私は（ハードディスクが安い）消耗スペースに対しては宗教的なベアリングを持っていません。
そのために私のバイナリツリーの私のノードは、親のポインタを持っています。それは私が話している（すべての）余分なスペースです。私は両方の上昇を反復処理する必要があり、様々な目的のためにツリーを下降するので、私は両親が必要になります。
私の心の中で、私はすぐにそれを行うことができるどのように擬似コードの小さな作品を書いたこと、それは、その場でノードを削除帰りがけ順です。これは、実装、テスト、および私の解決策の一部となっています。そしてそれはあまりにもかなり高速です。
のものがある：ノードが、私は「ちょうど出発した」ノードに親のリンクをゼロすることができるので、さらに親のポインタを持っている、とするとき、それは本当に、本当に、簡単な取得します。
ここでは、反復後のオーダーの削除のための擬似コードは次のとおりです。
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;
、その後、これらのリンクをチェックアウトします：
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する
ハッピーコーディング： - ）
セーレン霧 http://iprotus.eu/する
深まず、ポスト順序、非再帰、スタックなし
あなたが親を持っている場合：
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
空のスタックを作成します。2.1ルートがNULLではないながら、次の操作を行います。
a) Push root's right child and then root to stack.
b) Set root as root's left child.
2.2スタックから項目をポップし、ルートとして設定します。
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を繰り返し2.1手順2.2。
ここで2つのスタックとJava実装
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;
}
ここで、ユニットテストである
@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();
}
}
}
私はよく実行し、カスタマイズが簡単なコードスニペットを探していました。スレッドの木は、「シンプル」ではありません。ダブルスタック溶液は、O（n）のメモリを必要とします。よるLeetCodeソリューションとソリューションのTCB の余分なチェックとプッシュを持っている...
ここでは私のために働いCに翻訳1つの古典的なアルゴリズムがあります：
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、このアルゴリズムは好調で読みやすいwikipedia.org / Tree_traversal擬似コードよりも従うことは簡単です。栄光の詳細についてはKnuthの第1巻では、バイナリツリー演習への回答を参照してください。
ここでは、Pythonのバージョンがあまりにもです::
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)
ここで出力::ある
" ここに画像の説明を入力するですから、ポストオーダートラバースを行うために1つのスタックを使用することができます。
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());
}
再帰を使用せずにポスト順トラバーサルのロジック
Postorder traversalにおいて、処理順序がleft-right-currentあります。だから我々は、他の部分を訪問する前に、まず左側のセクションを訪問する必要があります。私たちは、ツリーの各ノードのための可能性として残さとしてツリーにダウントラバースしようとします。右の子が存在する場合、現在の各ノードについて、そのルートはNULL / Noneでないながら、現在のノードをプッシュする前にスタックに押し込みます。今、スタックからノードをポップし、そのノードの右の子が存在するかどうかを確認してください。それが存在する場合、それは先頭の要素かと同じだかどうかを確認してください。それらが同じであれば、それは我々がまだ右の部分で行われていないことを示しているので、現在のノードを処理する前に、我々は右の部分を処理する必要があり、それはトップの要素（右の子）をポップし、スタックに戻し、現在のノードをプッシュするために。各時点で私たちの頭にはポップな要素です。トップとヘッドがNULLではないとして、現在の要素が同じでない場合、我々は左と右の部分の両方で行われますので、今、私たちは、現在のノードを処理することができます。私たちは、スタックが空になるまで、前の手順を繰り返す必要があります。
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()
再帰なしでポスト注文トラバーサルを実行するには、
二つの方法：
1.バックトラックのために訪れたノードの一つHashSetのとつのスタックを使用します：
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;
}
}
}
}
時間計算：O（n）の
スペース複雑さ：O（2N）
2.使用してツリーの変更方法：
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;
}
}
}
}
時間計算：O（n）の
スペース複雑さ：O（n）の
のTreeNodeクラスます：
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) {
val = x;
}
}
ここでは短いです、私は一般的な木のためにPythonで書くために必要なバージョン（ウォーカーは3行です）。もちろん、あまりにもより限定されたバイナリツリーのために動作します。ツリーは、ノードと子のリストのタプルです。これは、一つだけのスタックを持っています。使用例は示されています。
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
最も簡単な解決策は、それが最善の答えではないように見えるかもしれないが、理解しやすいです。そして、私はあなたが解決策を理解しているならば、あなたが最良の解決策を作ってそれを修正することができると信じています。
// 2つのスタックを使用して
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;
}
所属していません StackOverflow
