재귀 없이 이진 트리의 후순 순회
https://stackoverflow.com/questions/1294701
-
18-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
이진 트리의 사후 순서 순회를 수행하는 알고리즘은 무엇입니까 없이 재귀를 사용합니까?
해결책
다음은 방문한 플래그를 사용하지 않고 다른 두 가지 솔루션을 제공하는 링크입니다.
https://leetcode.com/problems/binary-tree-postorder-traversal/
이것은 트리의 부모 포인터가 없기 때문에 스택 기반 솔루션입니다. (부모의 포인터가 있으면 스택이 필요하지 않습니다).
루트 노드를 먼저 스택으로 밀어냅니다. 스택이 비어 있지는 않지만 노드의 왼쪽 자식을 스택 상단에서 계속 밀어 넣습니다. 좌파 자녀가 존재하지 않으면 우리는 오른쪽 아이를 밀어냅니다. 리프 노드 인 경우 노드를 처리하고 스택에서 팝업합니다.
또한 변수를 사용하여 이전에 트레이닝 된 노드를 추적합니다. 목적은 트래버스가 트리를 내림차순으로 올라가고 있는지 판단하는 것이며, 왼쪽/오른쪽에서 올라가는 지 알 수 있습니다.
우리가 왼쪽에서 나무를 올라가면, 우리는 왼쪽 아이를 다시 스택으로 밀고 싶지 않으며 오른쪽 아이가 존재한다면 나무를 계속 올라 가야합니다. 우리가 오른쪽에서 나무를 올라가면, 우리는 그것을 처리하고 스택에서 튀어 나와야합니다.
우리는이 세 가지 경우에 노드를 처리하고 스택에서 팝업 할 것입니다.
- 노드는 잎 노드입니다 (어린이 없음)
- 우리는 단지 왼쪽에서 나무를 가로 질러 오른쪽 아이가 존재하지 않습니다.
- 우리는 그냥 오른쪽에서 나무를 가로 질러 가야합니다.
다른 팁
다음은 하나의 스택이 있고 방문한 깃발이없는 버전은 다음과 같습니다.
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()
이것은 내가 반복적 인 사후 순서 트래버스에 사용하는 접근법입니다. 나는이 접근법이 마음에 들기 때문에 :
- 루프 사이클 당 단일 전환 만 처리하므로 따라 가기 쉽습니다.
- 유사한 솔루션은 순차 및 선주문 트래버스에 작용합니다
암호:
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을 사용해보십시오.
- Curr을 시도하십시오
- 현재 노드를 인쇄하십시오
- 아래의 모든 노드가 실행되었습니다 (사후 주문) : 시도해보십시오.
- 시도해 봐
- 노드가 루트 인 경우 위로가 없으므로 종료
- 왼쪽에서 올라 오면 오른쪽으로 시도하십시오
- 오른쪽에서 올라 오면 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 ++의 솔루션이 나무에 책을 보관할 수있는 스토리지가 필요하지 않습니다.
대신 두 개의 스택을 사용합니다. 하나는 우리가 횡단하고 다른 하나는 노드를 저장하여 포스트 트래버스를 수행 할 수 있도록 도와줍니다.
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)로 다른 버전을 붙여 넣고 있습니다. 재귀를 사용하지 않고 순서를 이해하도록 도와줍니다)
- 위키 (Wiki)http://en.wikipedia.org/wiki/post-order%5ftraversal#implementations) (우아한)
- 단일 스택의 또 다른 버전 ( #1 및 #2 : 기본적으로 오른쪽 순서에서 오른쪽 하위 노드가 실제 노드를 방문하기 전에 방문한다는 사실을 사용합니다. 따라서 Stack Top의 오른쪽 자식이 실제로 있는지 확인하는 데 의존합니다. 방문 된 마지막 포스트 순서 트래버스 노드 - 자세한 내용은 코드 스 니펫 아래에 주석을 추가했습니다)
- 두 개의 스택 버전 사용 (참조 : 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);
}
다음은 하나의 스택 (내 버전)이있는 사후 주문 횡단입니다.
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);
}
두 개의 스택 사용
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 스택과 깃발이없는 파이썬 :
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
노드 클래스를 특히 관련성이 없거나 테스트 사례로 추가하지 않았으며 독자 등의 운동으로 남겨 두었습니다.
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) - 스택의 경우 최악의 경우 최악의 트리는 단일 줄 링크 목록입니다.
이 문제에 대한 많은 활발한 접근 방식을 보는 것은 매우 좋습니다. 참으로 영감을주는!
이 주제를 발견하여 바이너리 트리 구현에서 모든 노드를 삭제하기위한 간단한 반복 솔루션을 검색했습니다. 나는 그들 중 일부를 시도했고, 그물에서 다른 곳에서 발견 된 비슷한 것을 시도했지만 그들 중 어느 것도 실제로 내 취향에 맞지 않았습니다.
문제는 매우 구체적인 목적 (비트 코인 블록 체인 인덱싱)을 위해 데이터베이스 인덱싱 모듈을 개발하고 있으며 내 데이터는 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://opendatrastructures.org/versions/edition-0.1e/ods-java/6_2_binarysearchtree_unbala.html http://opendatrastructures.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 루트가 널이 아닌 동안 다음을 수행하십시오
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 단계를 반복하십시오.
다음은 두 개의 스택이있는 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로 번역 된 클래식 알고리즘 중 하나입니다.
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 pseudocode보다 따라 가기가 더 쉽습니다. 영광스러운 세부 사항은 Knuth의 Volume 1의 이진 트리 운동에 대한 답변을 참조하십시오.
여기 파이썬 버전도 있습니다.
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)
출력은 다음과 같습니다.
따라서 하나의 스택을 사용하여 포스트 순서 트래버스를 수행 할 수 있습니다.
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. 방문 된 노드의 해시 해시를 사용하고 역 추적을 위해 하나의 스택 사용 :
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;
}
}
다음은 짧은 (워커는 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 a
가장 간단한 솔루션은 최상의 대답이 아닌 것처럼 보일 수 있지만 이해하기 쉽습니다. 그리고 솔루션을 이해했다면 최상의 솔루션을 만들기 위해 수정할 수 있다고 생각합니다.
// 두 스택 사용
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
