C＃实现二叉树的层次遍历

本文讲解C#实现二叉树的层次遍历
1、 /// 层次遍历
///
/// 层次遍历
///
///
static void LevelOrder(BiTNode T) {
SqQueue Q = new SqQueue();
Q.data = new BiTNode[MaxSize];
InitQueue(ref Q);
BiTNode p = null;
EnQueue(ref Q, T);
while (!isEmpty(Q)) {
DeQueue(ref Q, ref p);
visit§;
if (p.lchild!=null) { EnQueue(ref Q, p.lchild); }
if (p.rchild!=null) { EnQueue(ref Q,p.rchild); }
}
}

2、节点值访问
///
/// 结点值的输出
///
static void visit(BiTNode T) {
Console.Write(T.data+" ");
}

3、队列结构
///
/// 队列结构体定义
///
public struct SqQueue
{
public BiTNode[] data;//队列存放的元素
public int front, real;//队头和队尾指针
}
///
/// 队列初始化
///
///
static void InitQueue(ref SqQueue Q)
{
Q.real = Q.front = 0;
}
///
/// 判断队列是否为空
///
///
///
static bool isEmpty(SqQueue Q)
{
if (Q.front == Q.real) { return true; }
else return false;
}
///
/// 入队
///
///
///
///
static bool EnQueue(ref SqQueue Q, BiTNode x)
{
if ((Q.real + 1) % MaxSize == Q.front) { return false; }
Q.data[Q.real] = x;
Q.real = (Q.real + 1) % MaxSize;
return true;
}
///
/// 出队
///
///
///
///
static bool DeQueue(ref SqQueue Q, ref BiTNode x)
{
if (Q.real == Q.front) { return false; }
x = Q.data[Q.front];
Q.front = (Q.front + 1) % MaxSize;
return true;
}
4、实际main函数测试
public const int MaxSize = 50;
static void Main(string[] args)
{
BiTNode T = new BiTNode() ;
int x=0;
//创建二叉树
T.data = 1;
T.lchild= new BiTNode();
T.lchild.data = 2;
T.rchild = new BiTNode();
T.rchild.data = 3;
T.lchild.rchild=new BiTNode();
T.lchild.rchild.data = 4;
T.lchild.rchild.lchild= new BiTNode();
T.lchild.rchild.lchild.data = 6;
T.rchild.rchild = new BiTNode();
T.rchild.rchild.data = 5;
Console.WriteLine(“先序遍历的值：”);
PreOrder(T);
Console.WriteLine();
Console.WriteLine(“中序遍历的值：”);
InOrder(T);
Console.WriteLine();
Console.WriteLine(“后序遍历的值：”);
PostOrder(T);
Console.WriteLine();
Console.WriteLine(“非递归中序遍历的值：”);
InOrder2(T);
Console.WriteLine();
Console.WriteLine(“层次遍历的值：”);
LevelOrder(T);
Console.ReadLine();

    }