Bin Tree Post Order Traversal，No recursion，no node flag

还有另一种方法吗？ 花了2个小时试图搞清楚。 我有一个解决方案（参见下面的DumpPostOrder）但是，有更好或更有效的方法吗？ 感觉可能有。 规则是 – 没有递归，节点不能有访问标志。 即，你只能使用左+右成员。

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

using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace BinaryTreeNoRecursion { public class TreeNode { public T Value { get; set; } public TreeNode Left { get; set; } public TreeNode Right { get; set; } public TreeNode(T inValue) { Value = inValue; } public TreeNode(TreeNode left, TreeNode right, T inValue) { Left = left; Right = right; Value = inValue; } } public class BinaryTree { private TreeNode root; public TreeNode Root { get { return root; } } public BinaryTree(TreeNode inRoot) { root = inRoot; } public void DumpPreOrder(T[] testme) { Stack<TreeNode> stack = new Stack<TreeNode>(); stack.Push(root); int count =0; while (true) { if (stack.Count == 0) break; TreeNode 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> stack = new Stack<TreeNode>(); TreeNode node = root; TreeNode 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> stack = new Stack<TreeNode>(); TreeNode 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 node = new TreeNode(100); node.Left = new TreeNode(50); node.Right = new TreeNode(150); node.Left.Left = new TreeNode(25); node.Left.Right = new TreeNode(75); node.Right.Left = new TreeNode(125); node.Right.Right = new TreeNode(175); node.Right.Left.Left = new TreeNode(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 binTree = new BinaryTree(node); //do the dumps, verify output binTree.DumpPreOrder(preOrderResult); binTree.DumpInOrder(inOrderResult); binTree.DumpPostOrder(postOrderResult); } } } 

Answer 1

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

您当前正在构建一个访问过的节点集合。

您通过将节点设置为null将节点标记为已访问。

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

Answer 2

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

编辑

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

1）保持指向树中节点的双向链接列表。
2）从根节点开始。
3）将根指针附加到列表。
4）去找右边的孩子。
5）将当前节点指针附加到列表。
6）重复步骤4和5，直到没有合适的孩子。
7）将当前节点写入后期遍历。
8）将当前节点设置为列表中的最后一个节点。
9）去左边的孩子。
10）将当前音符指针附加到列表。
11）重复步骤4到10，直到列表为空。

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

Answer 3

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

如果您想使用自己的堆栈，那么您需要提供比仅仅节点更多的信息。 请记住，系统调用堆栈包含程序计数器以及函数参数（局部变量以及此处不重要的bu）。 我们可以推送表单的元组(PushMyChildren, node) ， (PrintMe, Node) ，当我们弹出表单的节点(PushMyChildren, node)我们推送(PrintMe, Node) ，然后(PushMyChildren, right child)然后(PushMyChildren, left child) 。 如果左右儿童不存在则不要推他们。 当我们弹出窗体的节点(PrintMe, Node)我们打印节点。 在伪C＃（我不知道C＃，没有时间查找正确的类型和语法）。

 public void DumpPostOrder(T[] testme) { enum StackState {printNode, pushChildren} Stack< Pair > > stack = new Stack< Tuple > >(); stack.Push(new Pair(pushChildren, root); while ( stack.Count != 0 ) { Pair > 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 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; }