蛇形打印:将一个树型结构按照层级首尾相接地打印。例如将
8
6 10
5 7 9 11
打印为
8
10 6
5 7 9 11
即将偶数层逆序
直接上代码:
public class SnakePrint {
public static void main(String[] args) {
Queue<btreenode> nodes = new LinkedBlockingQueue<btreenode>();/<btreenode>/<btreenode>
Stack<btreenode> stack = new Stack<btreenode>();/<btreenode>/<btreenode>
nodes.add(root);
nodes.add(xx);
// true:顺序打印,false:逆序
boolean flag = true;
while (!nodes.isEmpty()) {
BtreeNode n = nodes.poll();
if (n == xx) {
while (!flag && !stack.isEmpty()) {
System.out.print(stack.pop().val + " ");
}
if (!nodes.isEmpty()) {
System.out.println();
nodes.add(xx);
flag = !flag;
}
} else {
if (flag) {
System.out.print(n.val + " "); // flag为true直接顺序打印
} else {
stack.push(n);// flag为false的入栈待遇到换行标志再出栈打印
}
if (null != n.left) { // 左孩子入栈
nodes.add(n.left);
}
if (null != n.right) { // 右孩子入栈
nodes.add(n.right);
}
}
}
}
/** 分层标记 */
private static BtreeNode xx = new BtreeNode(Integer.MAX_VALUE);
/** 树根 */
private static BtreeNode root;
static {
BtreeNode t01, t02, t11, t12;
t01 = new BtreeNode(5);
t02 = new BtreeNode(7);
t11 = new BtreeNode(6);
t11.left = t01;
t11.right = t02;
t01 = new BtreeNode(9);
t02 = new BtreeNode(11);
t12 = new BtreeNode(10);
t12.left = t01;
t12.right = t02;
root = new BtreeNode(8);
root.left = t11;
root.right = t12;
}
static class BtreeNode {
BtreeNode left;
BtreeNode right;
int val;
public BtreeNode(int val) {
this.val = val;
}
@Override
public String toString() {
return super.toString() + "_" + val;
}
}
}
如有更好的实现请回复交流。
閱讀更多 道法自然理在悟心 的文章