C#实现二叉树的前序、中序、后序遍历。
public class BinaryTreeNode
{
int value;
BinaryTreeNode left;
BinaryTreeNode right;
/// <summary>
/// 前序遍历
/// </summary>
/// <param></param>
public static void PreOrder(BinaryTreeNode tree)
{
if (tree == null)
return;
System.Console.Write(tree.value + " ");
PreOrder(tree.left);
PreOrder(tree.right);
}
/// <summary>
/// 前序遍历循环实现
/// </summary>
/// <param></param>
public static void PreOrderLoop(BinaryTreeNode tree)
{
if (tree == null)
return;
Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
BinaryTreeNode node = tree;
while(node != null || stack.Any()){
if(node != null)
{
stack.Push(node);
System.Console.Write(node.value + " ");
node = node.left;
}
else
{
var item = stack.Pop();
node = item.right;
}
}
}
/// <summary>
/// 中序遍历
/// </summary>
/// <param></param>
public static void InOrder(BinaryTreeNode tree)
{
if (tree == null)
return;
InOrder(tree.left);
System.Console.Write(tree.value + " ");
InOrder(tree.right);
}
/// <summary>
/// 中序遍历循环实现
/// </summary>
/// <param></param>
public static void InOrderLoop(BinaryTreeNode tree)
{
if (tree == null)
return;
Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
BinaryTreeNode node = tree;
while (node != null || stack.Any())
{
if (node != null)
{
stack.Push(node);
node = node.left;
}
else
{
var item = stack.Pop();
System.Console.Write(item.value + " ");
node = item.right;
}
}
}
/// <summary>
/// 后序遍历
/// </summary>
/// <param></param>
public static void PostOrder(BinaryTreeNode tree)
{
if (tree == null)
return;
PostOrder(tree.left);
PostOrder(tree.right);
System.Console.Write(tree.value + " ");
}
/// <summary>
/// 后序遍历循环实现1
/// </summary>
/// <param></param>
public static void PostOrderLoop(BinaryTreeNode tree)
{
if (tree == null)
return;
Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
BinaryTreeNode node = tree;
BinaryTreeNode pre = null;
stack.Push(node);
while (stack.Any())
{
node = stack.Peek();
if ((node.left == null && node.right == null) ||
(pre != null && (pre == node.left || pre == node.right)))
{
System.Console.Write(node.value + " ");
pre = node;
stack.Pop();
}
else
{
if (node.right != null)
stack.Push(node.right);
if (node.left != null)
stack.Push(node.left);
}
}
}
/// <summary>
/// 后续遍历循环实现2
/// </summary>
/// <param></param>
public static void PostOrderLoop2(BinaryTreeNode tree)
{
HashSet<BinaryTreeNode> visited = new HashSet<BinaryTreeNode>();
Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
BinaryTreeNode node = tree;
while (node != null || stack.Any())
{
if (node != null)
{
stack.Push(node);
node = node.left;
}
else
{
var item = stack.Peek();
if (item.right != null && !visited.Contains(item.right))
{
node = item.right;
}
else
{
System.Console.Write(item.value + " ");
visited.Add(item);
stack.Pop();
}
}
}
}
}