本文讲解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();
}
