Обход бинарного дерева стеком - C#
Формулировка задачи:
Задание такое: реализовать обход бинарного дерева в глубину (сверху вниз) с помощью стека. НЕ очереди, а именно стека. В общем-то как это осуществить?
Решение задачи: «Обход бинарного дерева стеком»
textual
Листинг программы
using System;
using System.Collections.Generic;
namespace ConsoleApplication188
{
class Program
{
static void Main(string[] args)
{
var n3 = new Node {Name = "n3"};
var n1 = new Node {Left = n3, Name = "n1"};
var n2 = new Node { Name = "n2" };
var root = new Node {Left = n2, Right = n1, Name = "root"};
foreach (var n in EnumerateTree(root))
Console.WriteLine(n.Name);
Console.ReadLine();
}
private static IEnumerable<Node> EnumerateTree(Node root)
{
var stack = new Stack<Node>();
stack.Push(root);
while(stack.Count > 0)
{
var n = stack.Pop();
yield return n;
if (n.Left != null) stack.Push(n.Left);
if (n.Right != null) stack.Push(n.Right);
}
}
}
class Node
{
public string Name;
public Node Left;
public Node Right;
}
}