[算法] C#与数据结构--二叉树的遍历 - EaBIM

1usingSystem;
2publicclassNode
3{
4　　//成员变量
5　　privateobject_data;//数据
6　　privateNode_left;//左孩子
7　　privateNode_right;//右孩子
8　　publicobjectData
9　　{
10　　　　get{return_data;}
11　　}
12　　publicNodeLeft//左孩子
13　　{
14　　　　get{return_left;}
15　　　　set{_left=value;}
16　　}
17　　publicNodeRight//右孩子
18　　{
19　　　　get{return_right;}
20　　　　set{_right=value;}
21　　}
22　　//构造方法
23　　publicNode(objectdata)
24　　{
25　　　　_data=data;
26　　}
27　　publicoverridestringToString()
28　　{
29　　　　return_data.ToString();
30　　}
31}
32

复制代码

1usingSystem;
2publicclassBinaryTree
3{　　//成员变量
4　　privateNode_head;//头指针
5　　privatestringcStr;//用于构造二叉树的字符串
6　　publicNodeHead//头指针
7　　{
8　　　　get{return_head;}
9　　}
10　　//构造方法
11　　publicBinaryTree(stringconstructStr)
12　　{
13　　　　cStr=constructStr;
14　　　　_head=newNode(cStr[0]);//添加头结点
15　　　　Add(_head,0);//给头结点添加孩子结点
16　　}
17　　privatevoidAdd(Nodeparent,intindex)
18　　{
19　　　　intleftIndex=2*index+1;//计算左孩子索引
20　　　　if(leftIndex<cStr.Length)//如果索引没超过字符串长度
21　　　　{
22　　　　　　if(cStr[leftIndex]!='#')//'#'表示空结点
23　　　　　　{　//添加左孩子
24　　　　　　　　parent.Left=newNode(cStr[leftIndex]);
25　　　　　　　　//递归调用Add方法给左孩子添加孩子节点
26　　　　　　　　Add(parent.Left,leftIndex);
27　　　　　　}
28　　　　}
29　　　　intrightIndex=2*index+2;
30　　　　if(rightIndex<cStr.Length)
31　　　　{
32　　　　　　if(cStr[rightIndex]!='#')
33　　　　　　{　//添加右孩子
34　　　　　　　　parent.Right=newNode(cStr[rightIndex]);
35　　　　　　　　//递归调用Add方法给右孩子添加孩子节点
36　　　　　　　　Add(parent.Right,rightIndex);
37　　　　　　}
38　　　　}
39　　}
40　　publicvoidPreOrder(Nodenode)//先序遍历
41　　{
42　　　　if(node!=null)
43　　　　{
44　　　　　　Console.Write(node.ToString());//打印字符
45　　　　　　PreOrder(node.Left);//递归
46　　　　　　PreOrder(node.Right);//递归
47　　　　}
48　　}
49　　publicvoidMidOrder(Nodenode)//中序遍历
50　　{
51　　　　if(node!=null)
52　　　　{
53　　　　　　MidOrder(node.Left);//递归
54　　　　　　Console.Write(node.ToString());//打印字符
55　　　　　　MidOrder(node.Right);//递归
56　　　　}
57　　}
58　　publicvoidAfterOrder(Nodenode)//后继遍历
59　　{
60　　　　if(node!=null)
61　　　　{
62　　　　　　AfterOrder(node.Left);//递归
63　　　　　　AfterOrder(node.Right);//递归
64　　　　　　Console.Write(node.ToString());//打印字符
65　　　　}
66　　}
67}
68

复制代码

1usingSystem;
2classDemo6_1
3{
4　　staticvoidMain(string[]args)
5　　{　//使用字符串构造二叉树
6　　　　BinaryTreebTree=newBinaryTree("ABCDE#F");
7　　　　bTree.PreOrder(bTree.Head);//先序遍
8　　　　Console.WriteLine();
9　　　　bTree.MidOrder(bTree.Head);//中序遍
10　　　　Console.WriteLine();
11　　　　bTree.AfterOrder(bTree.Head);//后序遍
12　　　　Console.WriteLine();
13　　}
14}
15

复制代码

1　　publicvoidLevelOrder()//宽度优先遍历
2　　{
3　　　　Queuequeue=newQueue();//声明一个队例
4　　　　queue.Enqueue(_head);//把根结点压入队列
5　　　　while(queue.Count>0)//只要队列不为空
6　　　　{
7　　　　　　Nodenode=(Node)queue.Dequeue();//出队
8　　　　　　Console.Write(node.ToString());//访问结点
9　　　　　　if(node.Left!=null)//如果结点左孩子不为空
10　　　　　　{　//把左孩子压入队列
11　　　　　　　　queue.Enqueue(node.Left);
12　　　　　　}
13　　　　　　if(node.Right!=null)//如果结点右孩子不为熔
14　　　　　　{　//把右孩子压入队列
15　　　　　　　　queue.Enqueue(node.Right);
16　　　　　　}
17　　　　}
18　　}
【例6-2Demo6-2.cs】二叉树宽度优先遍历测试
1usingSystem;
2classDemo6_2
3{
4　　staticvoidMain(string[]args)
5　　{　//使用字符串构造二叉树
6　　　　BinaryTreebTree=newBinaryTree("ABCDE#F");
7　　　　bTree.LevelOrder();
8　　}
9}

复制代码