A binary tree is defined as a tree where each node can have no more than two children.
Building a Binary Search Tree:
首先创建一个节点Class
public class BtNode
{
public int Data { get; set; } public BtNode Left { get; set; } public BtNode Right { get; set; } public void DisplayNode()
{
Console.Write("Data: {0}, ", this.Data);
}
}
然后创建BST Class 提供Insert 方法：
public class BinarySearchTree
{
private BtNode root = null; public BtNode Root
{
get
{
return this.root;
}
set
{
this.root = value;
}
} public void Insert(int data)
{
BtNode newNode = new BtNode();
newNode.Data = data;
if (this.root == null)
{
this.root = newNode;
}
else
{
// Add to children nodes.
BtNode current = this.root;
BtNode parent = new BtNode(); while(true)
{
parent = current;
if (data < current.Data)
{
current = current.Left;
if (current == null )
{
parent.Left = newNode;
break;
} }
else
{
current = current.Right;
if (current == null)
{
parent.Right = newNode;
break;
}
}
}
}
}
}
Level traverse the binary tree.
思路就是用 Queue （FIFO），从左到右扫描节点，一个节点出队列，就将其节点的左右孩子入队。
public static void PrintLevelTracversal(BtNode root)
{
if (root == null)
{
throw new Exception("Binary true is null!");
} Queue<BtNode> queueBtNode = new Queue<BtNode>();
queueBtNode.Enqueue(root);
BtNode currentNode = root; // Dequeue the node from left to right and put its left/right children into queue.
while(currentNode != null)
{
currentNode = queueBtNode.Dequeue();
currentNode.DisplayNode(); if (currentNode.Left != null)
{
queueBtNode.Enqueue(currentNode.Left);
} if (currentNode.Right != null)
{
queueBtNode.Enqueue(currentNode.Right);
}
}
}
Level traverse and print nodes as Zigzag.
思路： 用2个Stuck， 一个保存Current Level， 另一个保存Next Level.
当一层 扫完后，将下一层copy到当前层。
// Non-Recursive method. Use two stacks.
public static void PrintZigzagLevelTraversal(BtNode root)
{
if (root == null)
{
throw new Exception("Binary tree is null!");
} Stack<BtNode> currentLevelStack = new Stack<BtNode>();
Stack<BtNode> nextLevelStack = new Stack<BtNode>();
BtNode currentBtNode = new BtNode(); int level = ;
currentLevelStack.Push(root); while(currentLevelStack.Count > )
{
// Display current node data.
currentBtNode = currentLevelStack.Pop();
currentBtNode.DisplayNode(); if (level % == ) // even level
{
if (currentBtNode.Left != null)
{
nextLevelStack.Push(currentBtNode.Left);
}
if (currentBtNode.Right != null)
{
nextLevelStack.Push(currentBtNode.Right);
}
}
else
{
if (currentBtNode.Right != null)
{
nextLevelStack.Push(currentBtNode.Right);
}
if (currentBtNode.Left != null)
{
nextLevelStack.Push(currentBtNode.Left);
}
} // Move data from next level to current level stack.
if (nextLevelStack.Count > && currentLevelStack.Count == )
{
BtNode[] nodes = new BtNode[nextLevelStack.Count];
nextLevelStack.CopyTo(nodes, );
for (int i = nodes.Length - ; i >= ; i--)
{
currentLevelStack.Push(nodes[i]);
}
nextLevelStack.Clear();
level++;
}
}
}