在C#实现二叉树遍历的示例

创建时间：2013年04月11日 15:39 阅读次数：(25839)

分享到：

今天在学习严蔚敏老师的数据结构教程，看到教程里面有介绍遍历二叉树的三种方式，就想到要用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;
        }
    }
}
}

代码就全部完成了，运行结果如下图：
二叉树遍历结果