Bin Tree后序遍历，无递归，无节点标志

Question

还有其他方法可以做到这一点吗？刚刚花了2个小时试图弄清楚。我有一个解决方案（请参阅下面的 DumpPostOrder）但是，是否有更好或更有效的方法？感觉可能有。规则是 - 没有递归，并且节点不能有已访问标志。即，您只能使用左+右成员。

我的方法是在此过程中摧毁这棵树。通过将每一侧的子节点设置为 null，您可以将节点标记为遍历一次，但我也会查看每个带有子节点的节点两次:(。有更好更快的方法吗？（对我的预序和中序实现的评论表示赞赏但不是必需的（即，会投票，但不标记答案）谢谢！

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

Answer 1

在我看来，在穿越树时摧毁它是相当残酷的。

您当前正在构建已访问节点的集合。

您可以通过将节点设置为空来将其标记为已访问。

您不能通过检查集合中的节点来检查访问情况吗？为了提高效率，您可能不需要使用堆栈，但这是一个实现细节。

Answer 2

您可以将二叉树映射到数组（类似于将堆映射到数组的方式，如图所示 此处），并在那里进行后序遍历。将二叉树转换为数组的操作可能会利用递归，但是如果您要控制树的初始构造方式（或者如果您只是在寻找一个有趣的想法），您可以将其构造为数组，并简化非递归后序遍历（无标志）问题。

编辑

我认为这将是一个可行的选择：

1）保留指向树中节点的指针的双向链表。
2) 从根节点开始。
3) 将根指针追加到列表中。
4) 转到右孩子。
5) 将当前节点指针追加到链表中。
6) 重复步骤4和5，直到不存在右子节点。
7) 将当前节点写入后序遍历。
8) 将当前节点设置为列表中的最后一个节点。
9) 转到左边的孩子。
10) 将当前注释指针添加到列表中。
11) 重复步骤 4 到 10，直到列表为空。

基本上，这使得树中的所有节点都有一个指向其父节点的指针。

Answer 3

如前所述，在这种情况下避免递归可能是一个坏主意。系统调用堆栈就是为了处理这样的事情而设计的。销毁树是标记节点的一种形式。

如果您想使用自己的堆栈，那么您需要推送比节点更多的信息。请记住，系统调用堆栈包含程序计数器以及函数参数（还有局部变量，但这里并不重要）。我们可以推送 (PushMyChildren, node)、(PrintMe, Node) 形式的元组，当我们弹出 (PushMyChildren, node) 形式的节点时 我们推送(PrintMe, Node)，然后(PushMyChildren，右子节点)，然后(PushMyChildren，左子节点)。如果左孩子和右孩子不存在，就不要推动他们。当我们弹出 (PrintMe, Node) 形式的节点时，我们会打印该节点。在伪 C# 中（我不懂 C#，也没有时间查找正确的类型和语法）。

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

Answer 4

我刚刚在 Java 中使用遍历宽度（使用队列）进行了后序操作。

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