二叉树的按层遍历并实现换行

二叉树是一个非常重要的数据结构，在好多的面试题中总会出现，大多数要求回答者实现在二叉树的按层遍历的同时实现换行，其实按层遍历很好想，但是要求换行输出的时候，很多时候就比较懵，无从下手，其实仔细想一想问题就会水落石出。

先构建节点类TreeNode，让他有一个String类型的数据值，一个节点类型的左孩子，一个节点类型的右孩子

package demo_datastruct;

public class TreeNode {
public String data;
public TreeNode leftChild;
public TreeNode rightChild;
public TreeNode(){

}
public TreeNode(String data){
this.data=data;
this.leftChild=null;
this.rightChild=null;
}
}

接下来就是定义节点，二叉树，遍历二叉树，一个三层的简单的二叉树

这里定义一个辅助队列，利用队列先进先出的特点可以简化遍历过程

        private TreeNode A = new TreeNode();
private TreeNode B = new TreeNode();
private TreeNode C = new TreeNode();
private TreeNode D = new TreeNode();
private TreeNode E = new TreeNode();
private TreeNode F = new TreeNode();
private Queue<TreeNode> q = new LinkedList<TreeNode>();

public void init() {
A.data = "1";
B.data = "2";
C.data = "3";
D.data = "4";
E.data = "5";
F.data = "6";
A.leftChild = B;
A.rightChild = C;
A.rightChild.leftChild = D;
A.rightChild.rightChild = E;
A.rightChild.leftChild.rightChild = F;
}

一个初始化方法用来设置数据值，和定义二叉树，这里用到了非常容易理解的定义二叉树的的方法，ABCDEF六个节点的数据值分别设置为123456

重要的遍历方法来了

public void Traversal(TreeNode node) {
        int i = 0;//当前行未打印的节点数
        int j = 0;//下一行的节点数
        if (node != null) {
            q.offer(node);
            i++;
            while (!q.isEmpty()) {
                i--;
                TreeNode t = q.poll();
                System.out.print(t.data);
                if (t.leftChild != null) {
                    j++;
                    q.offer(t.leftChild);
                }
                if (t.rightChild != null) {
                    j++;
                    q.offer(t.rightChild);
                }
                if (i == 0) {
                    System.out.println();
                    i = j;
                    j = 0;
                }
            }
        }else{
            return;
        }
    }

首先我们定义两个变量，分别用来记录当前行未打印的节点数，下一行的节点数，接下来开始遍历整个二叉树，先把根节点放入队列，这样当前节点数加一，执行队列判空判断，当队列不为空的时候执行循环语句，每当有左右孩子节点的时候，下一节点数++，执行换行的条件是，当前行未打印的节点数为0，执行换行，这样这一行打印完毕，到了下一行，之前我们记录的下一行的节点数就成了当前行未打印的节点数，执行一下赋值语句，这样就巧妙地完成了一行的遍历并实现了换行。

以下完整代码：

package demo_datastruct;

import java.util.LinkedList;
import java.util.Queue;

public class BinTree2 {
private TreeNode A = new TreeNode();
private TreeNode B = new TreeNode();
private TreeNode C = new TreeNode();
private TreeNode D = new TreeNode();
private TreeNode E = new TreeNode();
private TreeNode F = new TreeNode();
private Queue<TreeNode> q = new LinkedList<TreeNode>();

public void init() {
A.data = "1";
B.data = "2";
C.data = "3";
D.data = "4";
E.data = "5";
F.data = "6";
A.leftChild = B;
A.rightChild = C;
A.rightChild.leftChild = D;
A.rightChild.rightChild = E;
A.rightChild.leftChild.rightChild = F;
}

public void Traversal(TreeNode node) {
int i = 0;//当前行未打印的节点数
int j = 0;//下一行的节点数
if (node != null) {
q.offer(node);
i++;
while (!q.isEmpty()) {
i--;
TreeNode t = q.poll();
System.out.print(t.data);
if (t.leftChild != null) {
j++;
q.offer(t.leftChild);
}
if (t.rightChild != null) {
j++;
q.offer(t.rightChild);
}
if (i == 0) {
System.out.println();
i = j;
j = 0;
}
}
}else{
return;
}
}

public static void main(String[] args) {
BinTree2 b = new BinTree2();
b.init();
b.Traversal(b.A);
}
}

输出结果：