재귀없이 이진 트리의 사후 순회

재귀없이 이진 트리의 사후 순회

---

이진 트리의 게시물 주문 탐색 작업을 수행하는 알고리즘 무엇입니까 없이 재귀를 사용하여이?

---

다음은 방문 플래그를 사용하지 않고 두 가지 다른 솔루션을 제공하는 링크입니다.

https://leetcode.com/problems/binary-tree-postorder-traversal/

이것은 트리에 부모 포인터가 없기 때문에 분명히 스택 기반 솔루션입니다. (부모 포인터가 있으면 스택이 필요하지 않습니다).

루트 노드를 먼저 스택에 푸시합니다. 스택이 비어 있지 않은 동안 스택 맨 위에서 노드의 왼쪽 자식을 계속 밀어냅니다. 왼쪽 자식이 없으면 오른쪽 자식을 밀어냅니다. 리프 노드 인 경우 노드를 처리하고 스택에서 팝합니다.

또한 변수를 사용하여 이전에 통과 한 노드를 추적합니다. 목적은 순회가 트리를 하강 / 상승하는지 확인하는 것이며, 왼쪽 / 오른쪽에서 상승하는지 여부도 알 수 있습니다.

왼쪽에서 나무를 올라 간다면 왼쪽 자식을 다시 스택으로 밀고 싶지 않고 오른쪽 자식이 있으면 계속해서 나무 아래로 올라 가야합니다. 오른쪽에서 트리를 올라가면 처리하여 스택에서 제거해야합니다.

다음 세 가지 경우에 노드를 처리하고 스택에서 제거합니다.

1. 노드가 리프 노드 (자식 없음)
2. 우리는 왼쪽에서 나무 위로 올라가고 오른쪽 자식은 존재하지 않습니다.
3. 우리는 오른쪽에서 나무 위로 이동합니다.

---

다음은 방문 플래그가없는 스택 하나의 버전입니다.

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);
      }
    }
  }
}

---

다음은 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()

---

이것이 제가 반복적 인 주문 후 순회에 사용하는 접근 방식입니다. 다음과 같은 이유로이 접근 방식을 좋아합니다.

1. 루프주기 당 하나의 전환 만 처리하므로 따라 가기가 쉽습니다.
2. 유사한 솔루션이 순회 및 선주문 순회에 적용됩니다.

암호:

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();
    }
  }
}

설명:

다음과 같은 단계를 생각할 수 있습니다.

1. LEFT 시도
   • 왼쪽 노드가있는 경우 : LEFT를 다시 시도하십시오.
   • 왼쪽 노드가없는 경우 : RIGHT 시도
2. 올바른 시도
   • 올바른 노드가있는 경우 : 거기에서 LEFT 시도
   • 권한이 없으면 잎사귀에 있습니다. CURR 시도
3. CURR 시도
   • 현재 노드 인쇄
   • 아래의 모든 노드가 실행되었습니다 (주문 후) : Try UP
4. 시도해 봐
   • 노드가 루트이면 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 ++ 솔루션입니다.
대신 두 개의 스택을 사용합니다. 하나는 우리가 순회하는 데 도움이되고 다른 하나는 노드의 포스트 순회를 할 수 있도록 노드를 저장하는 것입니다.

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";
}

---

// 플래그가있는 자바 버전

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)의 다른 버전을 붙여 오전 : (반복 순회 당신이 참조 할 수 있습니다에 - 주문 : 도움말 날 중위 순회를 이해 재귀를 사용하지 않고 )

1. 위키 ( http://en.wikipedia.org/wiki/Post-order%5Ftraversal#Implementations ) (우아함)
2. 단일 스택의 또 다른 버전 (# 1 및 # 2 : 기본적으로 사후 순회에서 실제 노드를 방문하기 전에 올바른 자식 노드를 방문한다는 사실을 사용합니다. 따라서 스택 상단의 오른쪽 자식이 실제로 있는지 확인하기 만하면됩니다. 방문한 마지막 주문 순회 노드-자세한 내용은 아래 코드 스 니펫에 주석을 추가했습니다)
3. Two stacks 버전 사용하기 (ref : http://www.geeksforgeeks.org/iterative-postorder-traversal/ ) (쉽게 : 기본적으로 post order traversal reverse는 오른쪽 노드가 먼저 방문되는 간단한 조정으로 pre order traversal에 불과합니다. 그런 다음 왼쪽 노드)
4. 방문자 플래그 사용 (쉬움)
5. 단위 테스트

~

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 개이고 플래그가없는 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

---

나는 노드 클래스를 특별히 관련이 없거나 테스트 케이스로 추가하지 않았으며 독자를위한 연습 문제로 남겨 두었습니다.

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 대신 디스크에 저장 공간이 있으므로 공간 낭비에 대한 종교적 관계가 없습니다 (하드 디스크가 저렴합니다).

이런 이유로 내 이진 트리의 노드에는 부모 포인터가 있습니다. 그것이 내가 말하는 여분의 공간입니다. 다양한 목적으로 트리를 따라 오름차순을 반복해야하므로 부모가 필요합니다.

그것을 염두에두고, 나는 그것이 어떻게 수행 될 수 있는지, 즉, 즉석에서 노드를 삭제하는 post-order traversal에 대한 의사 코드의 작은 조각을 빠르게 적었습니다. 구현 및 테스트되었으며 내 솔루션의 일부가되었습니다. 그리고 그것도 꽤 빠릅니다.

문제는 노드에 부모 포인터가있을 때 정말 정말 간단 해집니다. 게다가 "방금 출발 한"노드에 대한 부모의 링크를 무효화 할 수 있기 때문입니다.

다음은 반복적 인 주문 후 삭제를위한 의사 코드입니다.

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.1e/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 단계를 반복합니다.

---

다음은 두 개의 스택이있는 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) 메모리가 필요합니다. tcb의 LeetCode 솔루션 및 솔루션 에는 추가 검사 및 푸시가 있습니다.

다음은 나를 위해 일한 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 의사 코드보다 따르기 쉽습니다. 자세한 내용은 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이 아닌 동안 현재 노드를 푸시하기 전에 스택으로 푸시합니다. 이제 스택에서 노드를 꺼내 해당 노드의 오른쪽 자식이 존재하는지 확인합니다. 존재하는 경우 최상위 요소와 동일한 지 확인하십시오. 동일하다면 아직 오른쪽 부분을 처리하지 않았 음을 나타내므로 현재 노드를 처리하기 전에 오른쪽 부분을 처리하고 그에 대해 최상위 요소 (오른쪽 자식)를 팝하고 현재 노드를 스택으로 다시 푸시해야합니다. . 매번 우리 머리는 튀어 나온 요소입니다. 현재 요소가 top과 같지 않고 head가 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()    

---

재귀없이 Post Order Traversal을 수행하는 두 가지 방법 :

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', [])])]))

dcba

---

가장 간단한 해결책은 최선의 답이 아닌 것처럼 보이지만 이해하기 쉽습니다. 그리고 솔루션을 이해했다면 가능한 최상의 솔루션을 만들기 위해 수정할 수 있다고 믿습니다.

// 두 스택 사용

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;  
}

참고 URL : https://stackoverflow.com/questions/1294701/post-order-traversal-of-binary-tree-without-recursion