A - 解决方案
我在这里写了直接的解决方案。如果您想要详细的答案、演示代码和解释,请跳过并查看答案的其余标题;
public static <T> void printLevelOrder(TreeNode<T> root) {
System.out.println("Tree;");
System.out.println("*****");
if(root == null) {
System.out.printf(" Empty\n");
return;
}
MyQueue<TreeNode<T>> queue = new MyQueue<>();
queue.enqueue(root);
while(!queue.isEmpty()) {
handleLevel(queue);
}
}
private static <T> void handleLevel(MyQueue<TreeNode<T>> queue) {
int size = queue.size();
for(int i = 0; i < size; i++) {
TreeNode<T> temp = queue.dequeue();
System.out.printf("%s ", temp.data);
queue.enqueue(temp.left);
queue.enqueue(temp.right);
}
System.out.printf("\n");
}
B - 说明
为了按层次打印树,您应该使用简单的队列实现来处理每个级别。在我的演示中,我编写了一个非常简约的简单队列类,称为MyQueue。
公共方法printLevelOrder
将以参数形式接受TreeNode<T>
对象实例root,它代表树的根。私有方法handleLevel
以MyQueue
实例作为参数。
在每个级别上,handleLevel
方法出队队列,直到队列大小等于该级别的元素数量,然后将换行符放入输出中以控制级别限制。
C - TreeNode类
public class TreeNode<T> {
T data;
TreeNode<T> left;
TreeNode<T> right;
public TreeNode(T data) {
this.data = data;;
}
}
D - MyQueue类:一个简单的队列实现
public class MyQueue<T> {
private static class Node<T> {
T data;
Node next;
public Node(T data) {
this(data, null);
}
public Node(T data, Node<T> next) {
this.data = data;
this.next = next;
}
}
private Node head;
private Node tail;
private int size;
public MyQueue() {
head = null;
tail = null;
}
public int size() {
return size;
}
public void enqueue(T data) {
if(data == null)
return;
if(head == null)
head = tail = new Node(data);
else {
tail.next = new Node(data);
tail = tail.next;
}
size++;
}
public T dequeue() {
if(tail != null) {
T temp = (T) head.data;
head = head.next;
size--;
return temp;
}
return null;
}
public boolean isEmpty() {
return size == 0;
}
public void printQueue() {
System.out.println("Queue: ");
if(head == null)
return;
else {
Node<T> temp = head;
while(temp != null) {
System.out.printf("%s ", temp.data);
temp = temp.next;
}
}
System.out.printf("%n");
}
}
E - DEMO:按层次顺序打印树
public class LevelOrderPrintDemo {
public static void main(String[] args) {
TreeNode<Integer> root = new TreeNode<>(1);
root.left = new TreeNode<>(2);
root.right = new TreeNode<>(3);
root.left.left = new TreeNode<>(4);
root.right.left = new TreeNode<>(5);
root.right.right = new TreeNode<>(6);
printLevelOrder(root);
}
public static <T> void printLevelOrder(TreeNode<T> root) {
System.out.println("Tree;");
System.out.println("*****");
if(root == null) {
System.out.printf(" Empty\n");
return;
}
MyQueue<TreeNode<T>> queue = new MyQueue<>();
queue.enqueue(root);
while(!queue.isEmpty()) {
handleLevel(queue);
}
}
private static <T> void handleLevel(MyQueue<TreeNode<T>> queue) {
int size = queue.size();
for(int i = 0; i < size; i++) {
TreeNode<T> temp = queue.dequeue();
System.out.printf("%s ", temp.data);
queue.enqueue(temp.left);
queue.enqueue(temp.right);
}
System.out.printf("\n");
}
}
F - 样例输入
1 // root
/ \
2 3 // level-1
/ / \
4 5 6 // level-2
G - 样例输出
Tree;
*****
1
2 3
4 5 6