Traversée post-ordre d'un arbre binaire sans récursion

Question

Quel est l'algorithme pour faire une traversée post ordre d'un arbre binaire ? SANS en utilisant la récursion ?

Answer 1

Voici la version avec une seule pile et sans drapeau visité :

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

Answer 2

Voici un lien qui fournit deux autres solutions sans utiliser de drapeaux visités.

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

Il s'agit évidemment d'une solution basée sur la pile en raison de l'absence de pointeur de parent dans l'arbre. (Nous n'aurions pas besoin d'une pile s'il y a un pointeur de parent).

Nous pousserions d'abord le nœud racine dans la pile. Tant que la pile n'est pas vide, nous continuons à pousser l'enfant gauche du noeud du haut de la pile. Si l'enfant de gauche n'existe pas, nous poussons son enfant de droite. Si c'est un noeud feuille, nous traitons le noeud et le sortons de la pile.

Nous utilisons également une variable pour garder la trace d'un nœud précédemment parcouru. Le but est de déterminer si la traversée est descendante/ascendante de l'arbre, et nous pouvons aussi savoir si elle est ascendante de la gauche/droite.

Si nous montons l'arbre depuis la gauche, nous ne voudrions pas pousser son enfant gauche à nouveau dans la pile et devrions continuer à monter dans l'arbre si son enfant droit existe. Si nous remontons l'arbre par la droite, nous devrions le traiter et le pousser hors de la pile.

Nous traiterions le nœud et le retirerions de la pile dans ces 3 cas :

1. Le noeud est un noeud feuille (pas d'enfants)
2. On traverse l'arbre en partant de la gauche et il n'y a pas d'enfant de droite.
3. On traverse juste l'arbre à partir de la droite.

Answer 3

Voici un extrait de 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()

Answer 4

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

}

Answer 5

// la version de java avec le drapeau

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

        }
    }
}