树的层次遍历

概述

对树的遍历应用较多的为二叉树的顺序遍历。顺序遍历有三种：先序遍历、中序遍历、后续遍历。可以通过递归方式或者非递归方式实现。
而对树的层次遍历可以了解到树的层次结构，并且与循序遍历不同，层次遍历可以适用各种不同结构的树。

实现

层次遍历的本质是从根节点出发每访问一个节点就需要将该节点的所有孩子进行维护，用于后续遍历时访问。当每一层节点访问完成后，下一层的所有节点已经被维护了。所以最简单的方法通过队列维护所有的孩子节点。每次访问，将节点出队，并将该节点的孩子节点入队。

//伪代码如下
void levelTraversal(){
    node=Queue.dequeue()
    //do something to node
    for all children from node{
        Queue.enqueue(child)
    }
}

看道题目

Self-printable B+ Tree

In this project, you are supposed to implement a B+ tree of order 3, with the following operations: initialize, insert (with splitting) and search. The B+ tree should be able to print out itself.
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive number N (≤10⁴), the number of integer keys to be inserted. Then a line of the N positive integer keys follows. All the numbers in a line are separated by spaces.
Output Specification:
For each test case, insert the keys into an initially empty B+ tree of order 3 according to the given order. Print in a line Key X is duplicated where X already exists when being inserted. After all the insertions, print out the B+ tree in a top-down lever-order format as shown by the samples.

Sample Input 1:
6
7 8 9 10 7 4
Sample Output 1:
Key 7 is duplicated
[9]
[4,7,8][9,10]

Sample Input 2:
10
3 1 4 5 9 2 6 8 7 0
Sample Output 2:
[6]
[2,4][8]
[0,1][2,3][4,5][6,7][8,9]

Sample Input 3:
3
1 2 3
Sample Output 3:
[1,2,3]

这道题目需要实现Order为3的B+树，并且层次输出B+树。不考虑题目中的B+树的实现，由于题目输出需要层次输出，所以可以通过上述的方式实现层次输出。