import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class Main {
public static class TreeNode<T>{
T data;
TreeNode<T> left=null;
TreeNode<T> right=null;
public TreeNode() {}
public TreeNode(T data){
this.data=data;
}
public TreeNode(T data, TreeNode left, TreeNode right) {
super();
this.data = data;
this.left = left;
this.right = right;
}
}
public static class BinaryTree<T>{
/**二叉樹的根節點*/
private TreeNode<T> root;
public BinaryTree(){}
public BinaryTree(TreeNode<T> root){
this.root = root;
}
/* public TreeNode<Integer> createBinaryTree(){
TreeNode<Integer> e = new TreeNode<Integer>(5);
TreeNode<Integer> g = new TreeNode<Integer>(7);
TreeNode<Integer> h = new TreeNode<Integer>(8);
TreeNode<Integer> l = new TreeNode<Integer>(12);
TreeNode<Integer> m = new TreeNode<Integer>(13);
TreeNode<Integer> n = new TreeNode<Integer>(14);
TreeNode<Integer> k = new TreeNode<Integer>(11, n, null);
TreeNode<Integer> j = new TreeNode<Integer>(10, l, m);
TreeNode<Integer> i = new TreeNode<Integer>(9, j, k);
TreeNode<Integer> d = new TreeNode<Integer>(4, null, g);
TreeNode<Integer> f = new TreeNode<Integer>(6, h, i);
TreeNode<Integer> b = new TreeNode<Integer>(2, d, e);
TreeNode<Integer> c = new TreeNode<Integer>(3, f, null);
TreeNode<Integer> root = new TreeNode<Integer>(1, b, c);
return root;
}*/
//遞歸前序
public void preOrder(TreeNode<T> root){
if(root!=null){
visit(root);
preOrder(root.left);
preOrder(root.right);
}
}
/*非遞歸前序:對于任一結點P：
1)通路結點P，并将結點P入棧;
2)判斷結點P的左孩子是否為空，若為空，則取棧頂結點并進行出棧操作，并将棧頂結點的右孩子置為目前的結點P，循環至1);若不為空，則将P的左孩子置為目前的結點P;
3)直到P為NULL并且棧為空，則周遊結束。
*/
public void nonRecursivePreOrder(TreeNode<T> root){
Stack<TreeNode<T>> s=new Stack<TreeNode<T>>();
if(root!=null){
s.push(root);//先把根節點入棧
while(!s.isEmpty()){//while棧不為空
TreeNode<T> node=s.pop();//彈出棧
visit(node);
if(node.right!=null) s.push(node.right);//把右節點入棧
if(node.left!=null) s.push(node.left); //把左節點入棧
}
}
}
//遞歸中序
public void inOrder(TreeNode<T> root){
if(root!=null){
inOrder(root.left);
visit(root);
inOrder(root.right);
}
}
//非遞歸中序周遊：對于任一結點P，将其入棧，然後沿其左子樹一直往下搜尋，直到搜尋到沒有左孩子的結點，此時該結點出現在棧頂，
//但是此時不能将其出棧并通路，是以其右孩子還為被通路。是以接下來按照相同的規則對其右子樹進行相同的處理，當通路完其右孩子時，該結點又出現在棧頂，此時可以将其出棧并通路。
public void nonRecursiveInOrder(TreeNode<T> root){
Stack<TreeNode<T>> stack=new Stack<TreeNode<T>>();
TreeNode<T> node=root;
while(node!=null||!stack.isEmpty()){
//左子樹一直入棧
while(node!=null){//一直找到節點左子樹是空的節點
stack.push(node);
node=node.left;
}
node=stack.pop();//左子樹是空的就是通路這個節點
visit(node);
node=node.right;//在找該節點的右子樹
}
}
//遞歸後序
public void postOrder(TreeNode<T> root){
if(root!=null){
postOrder(root.left);
postOrder(root.right);
visit(root);
}
}
//非遞歸後序周遊
public void nonRecursivePostOrder(TreeNode<T> root){
TreeNode<T> node=root;
TreeNode<T> preNode=null;//記錄之前周遊的右結點
Stack<TreeNode<T>> stack=new Stack<TreeNode<T>>();
while(node!=null||!stack.isEmpty()){
/*左子樹一直入棧*/
while(node!=null){
stack.push(node);
node=node.left;
}
node=stack.peek();//獲得棧頂節點但不出棧
/*如果右結點為空，或者右結點之前周遊過，列印根結點*/
if(node.right==null||node.right==preNode){
visit(node);
node=stack.pop();
preNode = node;
node=null;
}
else{
node=node.right;
}
}
}
//層次周遊
public void levelTraverse(TreeNode<T> root){
//Queue是一個接口，不能直接執行個體化，一般使用它的實作類LinkedList當做隊列用，
//Queue的實作類還有LinkedList, PriorityQueue, LinkedBlockingQueue, BlockingQueue, ArrayBlockingQueue, LinkedBlockingQueue, PriorityBlockingQueue
Queue<TreeNode<T>> queue=new LinkedList<TreeNode<T>>();
TreeNode<T> node=root;
queue.offer(node);//隊列用offer添加元素
/*對每一個節點先出隊列再讓其左節點和右節點入隊列*/
while(!queue.isEmpty()){
node=queue.poll();//隊列用poll出隊列
if(node!=null){
visit(node);
//左右節點入隊列
queue.offer(node.left);
queue.offer(node.right);
}
}
}
//遞歸求樹的高度
public int treeHeight(TreeNode<T> root){
if(root==null){
return 0;
}
else{
int leftTreeHeight=treeHeight(root.left);
int rightTreeHeight=treeHeight(root.right);
return leftTreeHeight>rightTreeHeight?leftTreeHeight+1:rightTreeHeight+1;
}
}
//遞歸求節點總數
public int treeNodes(TreeNode<T> root){
if(root==null){
return 0;
}
else{
int leftTreeNodes=treeNodes(root.left);
int rightTreeNodes=treeNodes(root.right);
return leftTreeNodes+rightTreeNodes+1;
}
}
//遞歸求葉子節點總數
public int treeLeaf(TreeNode<T> root){
if(root==null){
return 0;
}
else{
int leftTreeLeaf=treeLeaf(root.left);
int rightTreeLeaf=treeLeaf(root.right);
if(root.left==null&&root.right==null){
return leftTreeLeaf+rightTreeLeaf+1;
}
else{
return leftTreeLeaf+rightTreeLeaf;
}
}
}
public void visit(TreeNode<T> root) {
System.out.print(root.data+" ");
}
}
public static void main(String[] args) {
TreeNode<Integer> e = new TreeNode<Integer>(5);
TreeNode<Integer> g = new TreeNode<Integer>(7);
TreeNode<Integer> h = new TreeNode<Integer>(8);
TreeNode<Integer> l = new TreeNode<Integer>(12);
TreeNode<Integer> m = new TreeNode<Integer>(13);
TreeNode<Integer> n = new TreeNode<Integer>(14);
TreeNode<Integer> k = new TreeNode<Integer>(11, n, null);
TreeNode<Integer> j = new TreeNode<Integer>(10, l, m);
TreeNode<Integer> i = new TreeNode<Integer>(9, j, k);
TreeNode<Integer> d = new TreeNode<Integer>(4, null, g);
TreeNode<Integer> f = new TreeNode<Integer>(6, h, i);
TreeNode<Integer> b = new TreeNode<Integer>(2, d, e);
TreeNode<Integer> c = new TreeNode<Integer>(3, f, null);
TreeNode<Integer> root = new TreeNode<Integer>(1, b, c);
BinaryTree<Integer> tree=new BinaryTree<Integer>(root);
System.out.println("遞歸前序周遊二叉樹結果：");
tree.preOrder(root);
System.out.println();
System.out.println("非遞歸前序周遊二叉樹結果：");
tree.nonRecursivePreOrder(root);
System.out.println();
System.out.println("遞歸中序周遊二叉樹結果：");
tree.inOrder(root);
System.out.println();
System.out.println("非遞歸中序周遊二叉樹結果：");
tree.nonRecursiveInOrder(root);
System.out.println();
System.out.println("遞歸後序周遊二叉樹結果：");
tree.postOrder(root);
System.out.println();
System.out.println("非遞歸後序周遊二叉樹結果：");
tree.nonRecursivePostOrder(root);
System.out.println();
System.out.println("層次周遊二叉樹結果：");
tree.levelTraverse(root);
System.out.println();
System.out.println("遞歸求二叉樹的高度："+ tree.treeHeight(root));
System.out.println("遞歸二叉樹的結點數："+ tree.treeNodes(root));
System.out.println("遞歸二叉樹的葉子節點："+tree.treeLeaf(root));
}
}
輸出
遞歸前序周遊二叉樹結果：
1 2 4 7 5 3 6 8 9 10 12 13 11 14
非遞歸前序周遊二叉樹結果：
1 2 4 7 5 3 6 8 9 10 12 13 11 14
遞歸中序周遊二叉樹結果：
4 7 2 5 1 8 6 12 10 13 9 14 11 3
非遞歸中序周遊二叉樹結果：
4 7 2 5 1 8 6 12 10 13 9 14 11 3
遞歸後序周遊二叉樹結果：
7 4 5 2 8 12 13 10 14 11 9 6 3 1
非遞歸後序周遊二叉樹結果：
7 4 5 2 8 12 13 10 14 11 9 6 3 1
層次周遊二叉樹結果：
1 2 3 4 5 6 7 8 9 10 11 12 13 14
遞歸求二叉樹的高度：6
遞歸二叉樹的結點數：14
遞歸二叉樹的葉子節點：6
![Java小案例——随機數猜測随機數猜測[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)