Подтвердить что ты не робот

Обход по порядку двоичного дерева без рекурсии

Что такое алгоритм для выполнения обхода порядка двоичного дерева БЕЗ с помощью рекурсии?

4b9b3361

Ответ 1

Здесь ссылка, которая предоставляет два других решения без использования посещенных флагов.

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

Это, очевидно, решение на основе стека из-за отсутствия родительского указателя в дереве. (Нам не нужен стек, если есть родительский указатель).

Сначала мы поместим корневой узел в стек. Пока стек не пуст, мы продолжаем выталкивать левого потомка узла из вершины стека. Если левого ребенка не существует, мы подталкиваем его правого ребенка. Если это листовой узел, мы обрабатываем узел и извлекаем его из стека.

Мы также используем переменную для отслеживания ранее пройденного узла. Цель состоит в том, чтобы определить, является ли обход нисходящим/восходящим по дереву, и мы также можем знать, поднимается ли он слева/справа.

Если мы поднимаемся по дереву слева, мы не хотим снова помещать его левого потомка в стек и должны продолжать подниматься по дереву, если существует его правый потомок. Если мы поднимаемся по дереву справа, мы должны обработать его и выбросить из стека.

Мы обработаем узел и вытолкнем его из стека в следующих 3 случаях:

  1. Узел является листовым (без дочерних узлов)
  2. Мы просто перебираем дерево слева, и правого потомка не существует.
  3. Мы просто проходим вверх по дереву справа.

Ответ 2

Здесь версия с одним стеком и без посещенного флага:

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

Ответ 3

Здесь образец из 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()

Ответ 4

Это подход, который я использую для итеративного обхода после заказа. Мне нравится этот подход, потому что:

  • Он обрабатывает только один переход на цикл цикла, поэтому легко следовать.
  • Аналогичное решение работает для сквозных и предварительных обходов

код:

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

Объяснение:

Вы можете подумать о таких шагах:

  • Попробуйте LEFT
    • если left- node существует: попробуйте снова LEFT
    • если left- node не существует: Try RIGHT
  • Попробуйте ПРАВО
    • Если существует право node: попробуйте LEFT оттуда
    • Если права не существуют, вы находитесь на листе: Try CURR
  • Попробуйте CURR
    • Ток печати node
    • Все узлы ниже выполнены (после заказа): Попробуйте UP
  • Попробуйте UP
    • Если node является root, UP не существует, поэтому EXIT
    • Если вы встаете слева, попробуйте RIGHT
    • Если вы вернетесь направо, попробуйте CURR

Ответ 5

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


}

Ответ 6

Вот решение на С++, которое не требует хранения для хранения книг в дереве.
Вместо этого он использует два стека. Один, чтобы помочь нам пройти, а другой - хранить узлы, чтобы мы могли выполнить их обход.

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

Ответ 7

//версия 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);


        }
    }
}

Ответ 8

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

}

Ответ 9

Пожалуйста, ознакомьтесь с полной реализацией 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();
    }
}

Ответ 10

Здесь я вставляю разные версии в С# (.net) для справки: (для итеративного обхода в порядке, на который вы можете обратиться: Помогите мне разобраться в обходном пути без использования рекурсии)

  • wiki (http://en.wikipedia.org/wiki/Post-order%5Ftraversal#Implementations) (элегантный)
  • Другая версия одного стека (# 1 и # 2: в основном используется тот факт, что в обходном порядке после посещения фактического node посещает правильный дочерний node), поэтому мы просто полагаемся на проверку того, что если верхний верхний дочерний элемент стека является последним post traversal после node, которые были посещены - я добавил комментарии ниже в фрагментах кода для деталей)
  • Использование двух стеков (ссылка: http://www.geeksforgeeks.org/iterative-postorder-traversal/) (проще: в основном обратный ход обхода после заказа - это не что иное, как предварительный обход с простой настройкой, которую сначала посещает правая node, а затем слева node)
  • Использование флага посетителя (легко)
  • Тестирование устройств

~

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

С посещенным флагом в С# (.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()));
        }

Ответ 11

Python с 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

Ответ 12

Я не добавил класс node в качестве его не особо актуальных или случайных случаев, оставив их как упражнение для читателя и т.д.

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) - для стека, дерево наихудшего случая - это список, связанный с одной строкой

Ответ 13

Очень приятно видеть так много энергичных подходов к этой проблеме. Действительно вдохновляет!

Я столкнулся с этой темой, ища простое итеративное решение для удаления всех узлов в моей реализации двоичного дерева. Я попробовал некоторые из них, и я попробовал нечто подобное, найденное в другом месте в Сети, но ни один из них мне не понравился.

Дело в том, что я разрабатываю модуль индексирования базы данных для определенной цели (индексация биткойнов Blockchain), а мои данные хранятся на диске, а не в ОЗУ. Я поменяю местами по мере необходимости, делая свое собственное управление памятью. Это медленнее, но достаточно быстро для этой цели и с хранением на диске вместо ОЗУ, я не имею никакого религиозного отношения к тратам пространства (жесткие диски дешевы).

По этой причине мои узлы в моем двоичном дереве имеют родительские указатели. Это (все) дополнительное пространство, о котором я говорю. Мне нужны родители, потому что мне нужно повторять и восхождение и спуск по дереву для различных целей.

Имея это в виду, я быстро записал небольшой фрагмент псевдокода о том, как это можно сделать, т.е. постобработка, удаляющая узлы "на лету". Он реализован и протестирован и стал частью моего решения. И это довольно быстро тоже.

Дело в том, что оно действительно, ДЕЙСТВИТЕЛЬНО, просто, когда узлы имеют родительские указатели, и, кроме того, поскольку я могу исключить родительскую ссылку на "только что отпустил" node.

Здесь псевдокод для итеративного удаления после заказа:

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 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/

Ответ 14

Глубина сначала, пост-порядок, нерекурсивный, без стека

Когда у вас есть родитель:

   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

Ответ 15

1.1 Создайте пустой стек

2.1 Выполняйте следующие действия, если root не равен NULL

a) Push root right child and then root to stack.

b) Set root as root left child.

2.2 Поп-элемент из стека и установите его как root.

a) If the popped item has a right child and the right child 
   is at top of stack, then remove the right child from stack,
   push the root back and set root as root right child.

b) Else print root data and set root as NULL.

2.3 Повторите шаги 2.1 и 2.2, когда стек не пуст.

Ответ 16

Вот реализация 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}));

}

Ответ 17

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

Ответ 18

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

Ответ 19

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


}

Ответ 20

Я искал фрагмент кода, который хорошо работает и прост в настройке. Резьбовые деревья не являются "простыми". Для решения двойного стека требуется 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;
        }
    }
}

ИМХО этот алгоритм легче отслеживать, чем хорошо выполняемый и читаемый псевдокод wikipedia.org/Tree_traversal. Для славных деталей см. Ответы на бинарные древовидные упражнения в книге Knuths Volume 1.

Ответ 21

Вот и версия 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)

Вот результат:

enter image description here

Ответ 22

Таким образом, вы можете использовать один стек для прохождения пост-заказа.

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

Ответ 23

Логика обхода почтового заказа без использования рекурсии

В Postorder traversal порядок обработки является left-right-current. Поэтому нам нужно посетить левый раздел, прежде чем посещать другие части. Мы попытаемся пройти вниз к дереву как можно левее для каждого узла дерева. Для каждого текущего узла, если присутствует правый дочерний элемент, поместите его в стек, прежде чем помещать текущий узел, пока root не равен 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()    

Ответ 24

Два способа выполнения обхода заказа без рекурсии:

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

Ответ 26

Вот короткая (ходок 3 строки) версия, которую мне нужно было написать на Python для общего дерева. Конечно, работает и для более ограниченного двоичного дерева. Дерево - это кортеж из узла и списка детей. У него только один стек. Пример использования показан.

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

д б б

Ответ 27

Самое простое решение, может показаться не лучшим ответом, но его легко понять. И я верю, что если вы поняли решение, вы можете изменить его, чтобы сделать наилучшее решение

//используя два стека

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