public class Tree {
private Node root;
public static class Node{
private Integer value;
private Node left;
private Node right;
public Node(Integer value) {
this.value = value;
}
}
public void add(Integer e){
if(root == null){
root = new Node(e);
} else {
recursionAdd(root, e);
}
}
public void recursionAdd(Node node, Integer key){
if(key > node.value){
if(node.right == null){
node.right = new Node(key);
}else{
recursionAdd(node.right, key);
}
} else {
if(node.left == null){
node.left = new Node(key);
} else {
recursionAdd(node.left, key);
}
}
}
/**
* 深度优先遍历
*/
public void deepOutPut(){
recursionScan(root);
}
public void recursionScan(Node node){
if(node == null){
return;
}
recursionScan(node.left);
// 中序遍历
System.out.println(node.value);
recursionScan(node.right);
}
/**
* 广度优先遍历
*/
public void breadthOutPut(){
BlockingQueue<Node> blockingQueue = new LinkedBlockingQueue();
blockingQueue.add(root);
while (!blockingQueue.isEmpty()){
Node poll = blockingQueue.poll();
if(poll != null){
System.out.println(poll.value);
if(poll.left != null){
blockingQueue.add(poll.left);
}
if(poll.right != null){
blockingQueue.add(poll.right);
}
}
}
}
public static void main(String[] args) {
Tree tree = new Tree();
tree.add(2);
tree.add(1);
tree.add(3);
tree.add(-5);
tree.add(3);
tree.add(3);
tree.add(0);
System.out.println("<=======深度优先遍历=======>");
tree.deepOutPut();
System.out.println("<=======广度优先遍历=======>");
tree.breadthOutPut();
}
}