Bin Tree Post Order Traversal, No recursion, no no

问题:

Is there another way to do this? Just spent 2 hours trying to figure it out. I have a solution (see DumpPostOrder below) however, is there is a better or more efficient method? It feels like there may be. Rules are - no recursion, and the nodes cannot have a visited flag. Ie, you can only use left + right members.

My approach was to destroy the tree in the process. By setting the children of each side to null you can mark the node as traversed once, but I'm also looking at each node with children twice :(. Is there a better faster way? (Comments on my preorder and inorder implementations are appreciated but not necessary (ie, will vote, but not mark answer). Thanks!

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BinaryTreeNoRecursion
{
    public class TreeNode<T>
    {
        public T Value { get; set; }

        public TreeNode<T> Left { get; set; }
        public TreeNode<T> Right { get; set; }

        public TreeNode(T inValue)
        {            
            Value = inValue;
        }

        public TreeNode(TreeNode<T> left, TreeNode<T> right, T inValue)
        {
            Left = left;
            Right = right;
            Value = inValue;
        }
    }

    public class BinaryTree<T>
    {
        private TreeNode<T> root;
        public TreeNode<T> Root
        {
            get { return root; }            
        }

        public BinaryTree(TreeNode<T> inRoot)
        {
            root = inRoot;
        }

        public void DumpPreOrder(T[] testme)
        {
            Stack<TreeNode<T>> stack = new Stack<TreeNode<T>>();
            stack.Push(root);
            int count =0;
            while (true)
            {
                if (stack.Count == 0) break;

                TreeNode<T> temp = stack.Pop();                

                if (!testme[count].Equals(temp.Value)) throw new Exception("fail");

                if (temp.Right != null)
                {
                    stack.Push(temp.Right);
                }

                if (temp.Left != null)
                {
                    stack.Push(temp.Left);
                }

                count++;
            }

        }

        public void DumpPostOrder(T[] testme)
        {

            Stack<TreeNode<T>> stack = new Stack<TreeNode<T>>();
            TreeNode<T> node = root;
            TreeNode<T> temp;
            int count = 0;
            while(node!=null || stack.Count!=0) 
            {   
                if (node!=null)
                {
                    if (node.Left!=null)
                    {                       
                        temp = node;
                        node = node.Left;
                        temp.Left = null;
                        stack.Push(temp);                        

                    }
                    else
                    if (node.Right !=null)
                    {
                        temp = node;
                        node = node.Right;
                        temp.Right= null;
                        stack.Push(temp);
                    }           
                    else //if the children are null
                    {
                        if (!testme[count].Equals(node.Value)) throw new Exception("fail");
                        count++;
                        if (stack.Count != 0)
                        {
                            node = stack.Pop();
                        }
                        else
                        {
                            node = null;
                        }
                    }       
                }
            }

        }

        public void DumpInOrder(T[] testme)
        {

            Stack<TreeNode<T>> stack = new Stack<TreeNode<T>>();            
            TreeNode<T> temp = root;
            int count = 0;
            while (stack.Count!=0 || temp!=null)
            {                
                if (temp != null)
                {                    
                    stack.Push(temp);
                    temp = temp.Left;
                }
                else
                {
                    temp = stack.Pop();
                    if (!testme[count].Equals(temp.Value)) throw new Exception("fail");
                    count++;          
                    temp = temp.Right;
                }

            }
        }

    }


    class Program
    {
        static void Main(string[] args)
        {
            //create a simple tree
            TreeNode<int> node = new TreeNode<int>(100);
            node.Left = new  TreeNode<int>(50);
            node.Right = new  TreeNode<int>(150);
            node.Left.Left = new TreeNode<int>(25);
            node.Left.Right = new TreeNode<int>(75);
            node.Right.Left  = new TreeNode<int>(125);
            node.Right.Right = new TreeNode<int>(175);
            node.Right.Left.Left = new TreeNode<int>(110);

            int[] preOrderResult = { 100, 50, 25, 75, 150, 125, 110, 175};
            int[] inOrderResult = { 25, 50, 75, 100, 110, 125, 150, 175};
            int[] postOrderResult = { 25, 75, 50, 110, 125, 175, 150, 100 };
            BinaryTree<int> binTree = new BinaryTree<int>(node);

            //do the dumps, verify output
            binTree.DumpPreOrder(preOrderResult);
            binTree.DumpInOrder(inOrderResult);
            binTree.DumpPostOrder(postOrderResult);
        }
    }
}

回答1:

Seems to me that destroying the tree while traversing it is pretty brutal.

You are currently building a Collection of nodes visited.

You are marking nodes as visited by setting them to null.

Could you not instead check for visitation by checking for the node in your Collection? For efficiency you may need to not use a Stack, but that's an implementation detail.

回答2:

You could map your binary tree to an array (similar to how you can map a heap to an array, as shown here), and do your post-order traversal there. The action of converting a binary tree to an array is probably going to utilize recursion, but if you're controlling how the tree is initially constructed (or if you're just looking for an intriguing thought), you could just construct it as an array, and trivialize your non-recursive post-order traversal (with no flags) problem.

Edit

I think this would be a viable option:

1) Keep a bi-directional linked list of pointers to nodes in the tree.
2) Start at the root node.
3) Append root pointer to list.
4) Go to right child.
5) Append current node pointer to list.
6) Repeat steps 4 and 5 until there doesn't exist a right child.
7) Write current node to post-order-traversal.
8) Set current node to last node in the list.
9) Go to left child.
10) Append current note pointer to list.
11) Repeat steps 4 through 10 until the list is empty.

Basically, this makes all of the nodes in the tree have a pointer to their parent.

回答3:

Avoiding recursion in this case is probably a bad idea, as previously noted. The system call stack is designed to handle things like this. Destroying your tree is a form of marking nodes.

If you want to use your own stack, then you need to push a bit more more information than just the node. Remember that the system call stack contains the program counter as well as the function parameters (local variables as well bu that is not important here). We could push tuples of the form (PushMyChildren, node), (PrintMe, Node), and when we pop a node of the form (PushMyChildren, node) we push (PrintMe, Node), then (PushMyChildren, right child) and then (PushMyChildren, left child). If the left and right children don't exist don't push them. When we pop a node of the form (PrintMe, Node) we print the node. In pseudo C# (I don't know C# and don't have time to look up the correct types and Syntax).

public void DumpPostOrder(T[] testme)
{
  enum StackState {printNode, pushChildren} 
  Stack< Pair<StackState, TreeNode<T> > > stack = new Stack< Tuple<StackState, TreeNode<T> > >();
  stack.Push(new Pair(pushChildren, root);
  while ( stack.Count != 0 ) {
    Pair<StackState, TreeNode<T> > curr = stack.pop();
    if (curr.First ==  printNode) {
       // process the node in curr.Second
    } else {
       node = curr.Second;
       stack.Push(new Pair(printNode, node));
       if (node.Right != null) {
         stack.Push(new Pair(pushChildren, node.Right))
       }
       if (node.Left != null) {
         stack.Push(new Pair(pushChildren, node.Left))
       }
    }
  }

回答4:

I just made post-order in Java using traversal to width (using queue).

        private void init(){
            if (initialized) return;
            stack = new Stack<>();
            stack.push(root);
            travers(root.right);
            travers(root.left);
            initialized = true;
        }

        private void travers(Node node){
            if (node == null) return;
            Queue<Node> queue = new LinkedList<>();
            queue.add(node);
            while (!queue.isEmpty()){
                Node temp = queue.poll();
                stack.push(temp);
                if (temp.right != null) queue.add(temp.right);
                if (temp.left != null) queue.add(temp.left);
            }
        }

        public T next() {
            return stack.pop().data;
        }