Created
January 3, 2016 05:27
-
-
Save AlphaDelta/660d359a38bcd16977f7 to your computer and use it in GitHub Desktop.
Binary tree level order traversal
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
class Program | |
{ | |
class BinaryNode | |
{ | |
public char Letter; | |
public BinaryNode First = null, Second = null; | |
} | |
static BinaryNode BinaryTree = | |
// A | |
// / \ | |
// B C | |
// / \ \ | |
// D E F | |
new BinaryNode() | |
{ | |
Letter = 'A', | |
First = new BinaryNode() | |
{ | |
Letter = 'B', | |
First = new BinaryNode() { Letter = 'D' }, | |
Second = new BinaryNode() { Letter = 'E' } | |
}, | |
Second = new BinaryNode() | |
{ | |
Letter = 'C', | |
First = new BinaryNode() { Letter = 'F' } | |
} | |
}; | |
static void Main(string[] args) | |
{ | |
Write("[ ", ConsoleColor.White); | |
Write("Typical loop"); | |
Write(" ]\n", ConsoleColor.White); | |
//Handle our own stack to prevent a StackOverflowException | |
//With a typical loop it would call a method such as ProcessNode(BinaryNode), which would call itself with the nodes contained within the parent node, meaning to emulate such a process we need to use a first-in last-out collection such as Stack<T> | |
Stack<BinaryNode> stack = new Stack<BinaryNode>(); | |
stack.Push(BinaryTree); | |
BinaryNode current; | |
do | |
{ | |
current = stack.Pop(); | |
Write(current.Letter + " "); | |
if (current.Second != null) stack.Push(current.Second); | |
if (current.First != null) stack.Push(current.First); //First comes last because we're using a first-in last-out collection | |
} while (stack.Count > 0); | |
Write(".\n\n[ ", ConsoleColor.White); | |
Write("Binary tree level order traversal"); | |
Write(" ]\n", ConsoleColor.White); | |
//Use a queue instead of a stack for traversal, because it is first-in first-out | |
Queue<BinaryNode> queue = new Queue<BinaryNode>(); | |
queue.Enqueue(BinaryTree); | |
do | |
{ | |
current = queue.Dequeue(); | |
Write(current.Letter + " "); | |
if (current.First != null) queue.Enqueue(current.First); //First comes first | |
if (current.Second != null) queue.Enqueue(current.Second); | |
} while (queue.Count > 0); | |
Write(".", ConsoleColor.White); | |
Console.ReadKey(); | |
} | |
static void Write(string str, ConsoleColor c = ConsoleColor.Gray) { Console.ForegroundColor = c; Console.Write(str); } | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment