二叉树的后序遍历（不使用递归）

我正在寻找一个执行良好且易于自定义的代码片段。 线程树不是“简单”的解决方案。 双栈解决方案需要 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;
        }
    }
}

在我看来，这个算法比维基百科/树遍历伪代码更易于理解，而且性能也更好。如果想了解更多细节，请参考Knuth的第一卷中有关二叉树练习的答案。

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.1和2.2。

看到这么多富有激情的解决方法真是太好了。确实很鼓舞人心！

我在搜索二叉树实现中删除所有节点的简单迭代解决方案时遇到了这个主题。我尝试了其中一些，也尝试了在其他地方找到的类似的方法，但没有一个真正符合我的口味。

事实上，我正在为一个非常特定的目的（比特币区块链索引）开发一个数据库索引模块，我的数据存储在磁盘上，而不是内存中。我按需交换页面，进行自己的内存管理。它比较慢，但对于该目的来说足够快，并且由于数据存储在磁盘而不是内存中，我没有浪费空间的宗教信仰（硬盘很便宜）。

出于这个原因，我在我的二叉树中的节点具有父指针。这是我所说的（全部）额外空间。我需要这些父节点，因为我需要迭代树中升序和降序的各种目的。

有了这个想法，我很快就草拟了一小段伪代码，说明如何完成它，也就是在

问题是：当节点有父指针时，它变得非常简单，而且由于我可以将父链接置空到“刚离开”的节点，因此更加简单。

这是迭代后序删除的伪代码：

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

编程愉快 :-)

Søren Fog http://iprotus.eu/

使用 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

我没有添加节点类，因为它并不特别相关，也没有任何测试用例，把这些留给读者练习等。

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) - 对于栈来说，最坏情况下的树是一条单链表

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

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


}

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

这是使用两个栈的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}));

}

对于编写这些递归方法的迭代等效方法，我们可以首先了解递归方法本身如何在程序堆栈上执行。假设节点没有其父指针，我们需要为迭代变体管理自己的“堆栈”。

一种开始的方法是查看递归方法并标记调用将“恢复”的位置（初始调用或递归调用返回后）。下面这些被标记为“RP 0”，“RP 1”等（“Resume Point”）。对于后序遍历的情况：

void post(node *x)  
{  
  /* RP 0 */  
  if(x->lc) post(x->lc);  
  /* RP 1 */  
  if(x->rc) post(x->rc);  
  /* RP 2 */  
  process(x);  
}

它的迭代变体：

void post_i(node *root)  
{  
  node *stack[1000];  
  int top;  
  node *popped;  
 
  stack[0] = root;  
  top = 0;  
  popped = NULL;  
 
#define POPPED_A_CHILD() \  
  (popped && (popped == curr->lc || popped == curr->rc))  
 
  while(top >= 0)  
  {  
    node *curr = stack[top];  
 
    if(!POPPED_A_CHILD())  
    {  
      /* type (x: 0) */  
      if(curr->rc || curr->lc)  
      {  
        if(curr->rc) stack[++top] = curr->rc;  
 
        if(curr->lc) stack[++top] = curr->lc;  
 
        popped = NULL;  
        continue;  
      }  
    }  
 
    /* type (x: 2) */  
    process(curr);  
    top--;  
    popped = curr;  
  }  
}

代码中带有(x: 0)和(x: 2)的注释对应于递归方法中的“RP 0”和“RP 2”恢复点。

通过将lc和rc指针一起推动，我们已经消除了在post(x->lc)完成执行时保持post(x)调用在恢复点1处的需要。也就是说，我们可以直接将节点移动到“RP 2”，绕过“RP 1”。因此，在“RP 1”阶段没有节点保留在堆栈上。

POPPED_A_CHILD宏帮助我们推断出两个恢复点之一（“RP 0”或“RP 2”）。