今天在学习严蔚敏老师的数据结构教程，看到教程里面有介绍遍历二叉树的三种方式，就想到要用C#来实现一次。
在严蔚敏老师的数据结构教程里面有介绍，二叉树的遍历有三种方式，分别是：先（根）序遍历算法,中（根）序遍历算法,后（根）序遍历算法。下面我们就以下图中的二叉树为例来实现这三个算法。
从上面我们先计算出三种遍历算法的结果:
先(根)序算法：1 2 4 5 3 6 7
中(根)序算法：4 2 5 1 3 7 6
后(根)序算法：4 5 2 7 6 3 1
下面我们用C#方法来实现它，全部代码如下：
using System;
namespace ConsoleApplication4
{
//先定义一个树的类型，包括数据及左右字树及父节点
public class Tree<T>
{
//节点数据
public T Data
{
get;
set;
}
//左子树
public Tree<T> LNode
{
get;
set;
}
//右子树
public Tree<T> RNode
{
get;
set;
}
//双亲节点
public Tree<T> PNode
{
get;
set;
}
public Tree(T _data)
{
this.Data = _data;
}
}
class Program
{
static Program() { }
public Program() { }
static void Main(string[] args)
{
//初始化各节点
Tree<int> node_1 = new Tree<int>(1);
Tree<int> node_2 = new Tree<int>(2);
Tree<int> node_3 = new Tree<int>(3);
Tree<int> node_4 = new Tree<int>(4);
Tree<int> node_5 = new Tree<int>(5);
Tree<int> node_6 = new Tree<int>(6);
Tree<int> node_7 = new Tree<int>(7);
//将各节点组成上图中的树
SetTree(ref node_1, node_2, node_3, null);
SetTree(ref node_2, node_4, node_5, node_1);
SetTree(ref node_3, null, node_6, node_1);
SetTree(ref node_6, node_7, null, node_3);
//输出各遍历的结果
Console.Write("先序遍历：");
ReadFirst(node_1);
Console.WriteLine();
Console.Write("中序遍历：");
ReadSecond(node_1);
Console.WriteLine();
Console.Write("后序遍历：");
ReadThird(node_1);
Console.WriteLine();
Console.ReadLine();
}
//给各节点初始化左右子树及双亲节点
public static void SetTree(ref Tree<int> tree, Tree<int> ltree, Tree<int> rtree, Tree<int> ptree)
{
tree.LNode = ltree;
tree.RNode = rtree;
tree.PNode = ptree;
}
//先序遍历
public static void ReadFirst(Tree<int> tree)
{
if (tree != null)
{
Console.Write(tree.Data);
ReadFirst(tree.LNode);
ReadFirst(tree.RNode);
}
else
{
return;
}
}
//中序遍历
public static void ReadSecond(Tree<int> tree)
{
if (tree != null)
{
ReadSecond(tree.LNode);
Console.Write(tree.Data);
ReadSecond(tree.RNode);
}
else
{
return;
}
}
//后序遍历
public static void ReadThird(Tree<int> tree)
{
if (tree != null)
{
ReadThird(tree.LNode);
ReadThird(tree.RNode);
Console.Write(tree.Data);
}
else
{
return;
}
}
}
}
代码就全部完成了，运行结果如下图：
