Есть ли другой способ сделать это? Просто потратил 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);
}
}
}