二叉树广度优先搜索，并且实现打印二叉树

二叉树广度优先搜索，简单的说就是按层一层一层的遍历。

主要的算法是借助一个队列。

然后从根节点先入列，再根节点出列，同时把根节点的左右孩子入列。

然后再从队列中出列下一个节点，同时把该节点的左右孩子入列。

循环这样的步骤，直到这个队列变为空。

1. using System;  
2. using System.Collections.Generic;  
3. using System.Linq;  
4. using System.Text;  
5.  
6. namespace tree  
7. {  
8.     #region 节点的定义  
9.     class node  
10.     {  
11.         public int nodevalue;  
12.         public node leftchild, rightchild;  
13.  
14.         public node()  
15.         { }  
16.         public node(int value)  
17.         {  
18.             nodevalue = value;  
19.         }  
20.  
21.         public void assignchild(node left, node right)//设定左右孩子  
22.         {  
23.             this.leftchild = left;  
24.             this.rightchild = right;  
25.         }  
26.  
27.         public bool hasleftchild//是否有左孩子  
28.         {  
29.             get 
30.             {  
31.                 return (leftchild != null);  
32.             }  
33.         }  
34.  
35.         public bool hasrightchild//是否有右孩子  
36.         {  
37.             get 
38.             {  
39.                 return (rightchild != null);  
40.             }  
41.         }  
42.  
43.         public bool haschild//是否有右孩子  
44.         {  
45.             get 
46.             {  
47.                 return hasleftchild || hasrightchild;  
48.             }  
49.         }  
50.     }  
51.     #endregion  
52.     class Program  
53.     {  
54.         static void Main(string[] args)  
55.         {  
56.             node node_1 = new node(1);  
57.             node node_2 = new node(2);  
58.             node node_3 = new node(3);  
59.             node node_4 = new node(4);  
60.             node node_5 = new node(5);  
61.             node node_6 = new node(6);  
62.             node node_7 = new node(7);  
63.             node node_8 = new node(8);  
64.             node node_9 = new node(9);  
65.             node node_10 = new node(10);  
66.             node node_11 = new node(11);  
67.             node node_12 = new node(12);  
68.             node node_13 = new node(13);  
69.             node node_14 = new node(14);  
70.             node node_15 = new node(15);  
71.  
72.             node_1.assignchild(node_2, node_3);  
73.             node_2.assignchild(node_4, node_5);  
74.             node_3.assignchild(node_6, node_7);  
75.             node_4.assignchild(node_8, node_9);  
76.             node_5.assignchild(node_10, node_11);  
77.             node_6.assignchild(node_12, node_13);  
78.             node_7.assignchild(node_14, node_15);  
79.  
80.             BreadthFirstSearch(node_1);  
81.         }  
82.  
83.         static void BreadthFirstSearch(node root)  
84.         {  
85.             Queue<node> leafqueue = new Queue<node>();  
86.             leafqueue.Enqueue(root);//根结点入列  
87.             while (leafqueue.Count > 0)  
88.             {  
89.                 node current = leafqueue.Dequeue();  
90.                 Console.WriteLine(current.nodevalue);  
91.                 if (current.hasleftchild)//左孩子入列  
92.                     leafqueue.Enqueue(current.leftchild);  
93.                 if (current.hasrightchild)//右孩子入列  
94.                     leafqueue.Enqueue(current.rightchild);  
95.             }  
96.         }  
97.     }  
98. } 

运行结果如下：

但是广度优先搜索的时候，并不知道目前元素到底在第几层。因为并不是所有的二叉树都是满二叉树，因此不太容易确定当前访问的结点的具体位置。比如不知道是左还是右。

因此要实现按照树形结构打印二叉树有点困难。

所以本人修改了广度优先搜索算法，使之能够知道目前是第几层的元素。

算法很简单，对于不存在左右孩子的结点，程序给它构造一个自定义的空结点，这样的话把整棵树补充完整为满二叉树。

这样的话，每次访问完一层后。队列中还会入列2的k次方个元素（其中可能包含部分自定义的空结点），同时可以确定后续的2的k次方个元素肯定是属于一层的，不可能分在2层。

因此，第一层有1个元素，第二层2个，第三层4个，第三层8个（都可能包含部分自定义的空结点）。只需要在打印完相应的元素个数后换行打印即可。

直到发现队列中新入列的2的k次方个元素全是自定义的空结点，这时可以断定，这个树已经打印完成了。程序可以退出。

具体代码如下：

1. static void printtree(node root)  
2.        {  
3.            Queue<node> leafqueue = new Queue<node>();  
4.            leafqueue.Enqueue(root);  
5.            int i = 0;  
6.            int j = 0;  
7.            node nullnode = new node(-1);//自定义-1的结点为空结点  
8.            while (leafqueue.Count > 0)  
9.            {  
10.                node current = leafqueue.Dequeue();  
11.                //每次循环都会入列2的n次方个元素  
12.                Console.Write(current.nodevalue+",");  
13.                if (current.hasleftchild)  
14.                    leafqueue.Enqueue(current.leftchild);  
15.                else 
16.                    leafqueue.Enqueue(nullnode);//没有就加入空结点  
17.  
18.                if (current.hasrightchild)  
19.                    leafqueue.Enqueue(current.rightchild);  
20.                else 
21.                    leafqueue.Enqueue(nullnode);//没有就加入空结点  
22.                i++;  
23.                //对于满二叉树来说，每层都是有2的n次方个，所以  
24.                //当i是2的n次方的时候，说明该层已经打完了。同时又增加了下一次的2的n+1次放个元素  
25.                if (i == Math.Pow(2, j))//打印了2的整数次幂个后，换行。依次是1,2,4,8.  
26.                {  
27.                    i = 0;//i清空，重新计数。  
28.                    j++;//可以表示打印在第几层。  
29.                    Console.WriteLine();//换行  
30.  
31.                    //如果队列后面的2的j次方的元素都是空节点，那么说明已经对这个树打完了。  
32.                    if (leafqueue.Where(m => m == nullnode).ToList().Count == Math.Pow(2, j))  
33.                    {  
34.                        break;  
35.                    }  
36.                }  
37.  
38.            }  
39.  
40.        } 

运行的结果如下：

如果不是满二叉树，比如：

    node_1.assignchild(node_2, node_3);

            node_2.assignchild(node_4, node_5);

            node_3.assignchild(null, node_7);

            node_4.assignchild(node_8, node_9);

            node_5.assignchild(null, node_11);

            node_6.assignchild(node_12, node_13);

            node_7.assignchild(node_14, node_15);

这样的树结构，则打印的结果如下：

此程序没有格式化，比如打印/,\之类的符号，并且根结点居中之类的方法也没实现。

但是再此算法的基础上，要实现这些，都不是很难了。