宾树后序遍历，没有递归，没有节点标志 [英] Bin Tree Post Order Traversal, No recursion, no node flag
问题描述
有另一种方式做到这一点？仅仅花了2小时试图弄明白。我有一个解决方案（见下文DumpPostOrder）然而，有一个更好或更有效的方法？这感觉就像有可能。规则 - 没有递归，和节点不能有一个被访问的标志。也就是说，你只能用左+右成员。
我的方法是摧毁树的过程。通过设定每边的孩子们NULL作为遍历一旦你可以标记一个节点，但我也期待在每个节点有孩子的两倍:(。是否有更好更快的方法？（我的preorder和评论序实现被pciated AP $ P $，但没有必要（也就是会投，但没有标注的答案）。谢谢！
使用系统;
使用System.Collections.Generic;
使用System.Linq的;
使用System.Text;
命名空间BinaryTreeNoRecursion
{
公共类树节点＆LT; T＆GT;
{
公众的T值{获得;组; }
公共树节点＆LT; T＆GT;左{获得;组; }
公共树节点＆LT; T＆GT;右{获得;组; }
公共树节点（T inValue）
{
值= inValue;
}
公共树节点（树节点＆LT; T＆GT;左树节点＆LT; T＆GT;右，T inValue）
{
左=左;
右=权利;
值= inValue;
}
}
公共类二叉树＆LT; T＆GT;
{
私人树节点＆LT; T＆GT;根;
公共树节点＆LT; T＆GT;根
{
{返回根; }
}
公共二叉树（树节点＆LT; T＆GT;器InRoot）
{
根=器InRoot;
}
公共无效转储preOrder（T [] TESTME）
{
堆叠＆LT;树节点＆LT; T＆GT;＆GT;堆栈=新的堆栈＆LT;树节点＆LT; T＆GT;＆GT;（）;
stack.Push（根）;
诠释计数= 0;
而（真）
{
如果（stack.Count == 0）打破;
树节点＆LT; T＆GT;临时= stack.Pop（）;
如果（！TESTME [统计] .Equals（temp.Value））抛出新的异常（失败）;
如果（temp.Right！= NULL）
{
stack.Push（temp.Right）;
}
如果（temp.Left！= NULL）
{
stack.Push（temp.Left）;
}
算上++;
}
}
公共无效DumpPostOrder（T [] TESTME）
{
堆叠＆LT;树节点＆LT; T＆GT;＆GT;堆栈=新的堆栈＆LT;树节点＆LT; T＆GT;＆GT;（）;
树节点＆LT; T＆GT;节点=根;
树节点＆LT; T＆GT;温度;
诠释计数= 0;
而（节点！= NULL || stack.Count！= 0）
{
如果（节点！= NULL）
{
如果（node.Left！= NULL）
{
TEMP =节点;
节点= node.Left;
temp.Left = NULL;
stack.Push（临时）;
}
其他
如果（node.Right！= NULL）
{
TEMP =节点;
节点= node.Right;
temp.Right = NULL;
stack.Push（临时）;
}
否则//如果孩子为空
{
如果（！TESTME [统计] .Equals（node.Value））抛出新的异常（失败）;
算上++;
如果（stack.Count！= 0）
{
节点= stack.Pop（）;
}
其他
{
节点= NULL;
}
}
}
}
}
公共无效DumpInOrder（T [] TESTME）
{
堆叠＆LT;树节点＆LT; T＆GT;＆GT;堆栈=新的堆栈＆LT;树节点＆LT; T＆GT;＆GT;（）;
树节点＆LT; T＆GT; TEMP =根;
诠释计数= 0;
而（stack.Count！= 0 ||温度！= NULL）
{
如果（临时！= NULL）
{
stack.Push（临时）;
TEMP = temp.Left;
}
其他
{
临时= stack.Pop（）;
如果（！TESTME [统计] .Equals（temp.Value））抛出新的异常（失败）;
算上++;
TEMP = temp.Right;
}
}
}
}
类节目
{
静态无效的主要（字串[] args）
{
//创建一个简单的树
树节点＆LT; INT＆GT;节点=新树节点＆其中; int的＆GT;（100）;
node.Left =新树节点＆LT;诠释＆GT;（50）;
node.Right =新树节点＆LT; INT＆GT;（150）;
node.Left.Left =新树节点＆LT;诠释＆GT;（25）;
node.Left.Right =新树节点＆LT; INT＆GT;（75）;
node.Right.Left =新树节点＆LT;诠释＆GT;（125）;
node.Right.Right =新树节点＆LT; INT＆GT;（175）;
node.Right.Left.Left =新树节点＆LT;诠释＆GT;（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};
二叉树＆LT; INT＆GT;二叉树=新二叉树＆LT; INT＆GT;（节点）;
//做垃圾场，验证输出
binTree.Dump preOrder（preOrderResult）;
binTree.DumpInOrder（inOrderResult）;
binTree.DumpPostOrder（postOrderResult）;
}
}
}
在我看来，破坏树遍历时它是pretty的残酷。
您目前正在建设的节点集合访问。
正在打标节点所访问设置为null。
你能不能，而不是通过检查您的收藏节点检查探视？为了提高效率，您可能需要为不使用堆栈，但是这是一个实现细节。
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);
}
}
}
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.
这篇关于宾树后序遍历，没有递归，没有节点标志的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
