package com.lever;

import java.util.LinkedList;

import java.util.Queue;

/**

* 二叉树遍历

* @author lckxxy

*

*/

public class Node {

public int value;

public Node left;

public Node right;

public Node(int v) {

this.value = v;

this.left = null;

this.right = null;

}

public static void main(String[] args) {

StringBuffer str = new StringBuffer();

str.append("hello world");

String test = str.toString();

System.out.println(test.replace(" ", "%20"));

Node n1 = new Node(1);

Node n2 = new Node(2);

Node n3 = new Node(3);

Node n4 = new Node(4);

Node n5 = new Node(5);

Node n6 = new Node(6);

Node n7 = new Node(7);

Node n8 = new Node(8);

Node n9 = new Node(9);

Node n10 = new Node(10);

n1.left = n2;

n1.right = n3;

n2.left = n4;

n2.right = n5;

n3.left = n6;

n3.right = n7;

n4.left = n8;

n4.right = n9;

n5.left = n10;

levelTravel(n1);

}

/**

*

* @param root

* 树根节点

* 层序遍历二叉树，用队列实现，先将根节点入队列，只要队列不为空，然后出队列，并访问，接着讲访问节点的左右子树依次入队列

*/

public static void levelTravel(Node root) {

if (root == null)

return;

// 当前行最后一个元素

Node last = root;

// 下一行最后一个元素

Node nlast = root.right == null ? root.left : root.right;

Queue q = new LinkedList();

q.add(root);

while (!q.isEmpty()) {

Node temp = (Node) q.poll();

System.out.print(temp.value + " ");

if (temp.left != null) {

q.add(temp.left);

// 如果左儿子不为空，把nlast置为左儿子，这样保证nlast永远是当前行最新一个

nlast = temp.left;

}

if (temp.right != null) {

q.add(temp.right);

// 如果右儿子不为空，把nlast置为右儿子

nlast = temp.right;

}

// 如果当前node跟last相同，说明该换行了，输出换行符，并将nlast的赋给last

if (temp.equals(last)) {

System.out.println();

last = nlast;

}

}

}

}