import java.util.LinkedList;
import java.util.Queue;
class Node{
 public int data;
 public Node left;
 public Node right;
 public int leftMaxDistance;
 public int rightMaxDistance;
 public Node(int data){
 this.data=data;
 this.left=null;
 this.right=null;
 }
}
/**
 * @author TY
 * 實(shí)現(xiàn)二叉排序樹，包括插入、中序遍歷、先序遍歷、后序遍歷、計算所有節(jié)點(diǎn)的最大距離的功能
 */
public class BinaryTree {
 private Node root;
 public BinaryTree(){
 root=null;
 }
 public void insert(int data){
 Node newNode=new Node(data);
 if(root==null)
 root=newNode;
 else{
 Node current=root;
 Node parent;
 while (true) {//尋找插入位置
 parent=current;
 if(data<current.data){
 current=current.left;
 if(current==null){
 parent.left=newNode;
 return;
 }
 }else{
 current=current.right;
 if (current==null) {
 parent.right=newNode;
 return;
 }
 }
 }
 }
 }
 //將數(shù)值輸入構(gòu)建二叉樹
 public void buildTree(int[] data){
 for (int i = 0; i < data.length; i++) {
 insert(data[i]);
 }
 }
 //中序遍歷方法遞歸實(shí)現(xiàn)
 public void inOrder(Node localRoot){
 if(localRoot!=null){
 inOrder(localRoot.left);
 System.out.print(localRoot.data+" ");
 inOrder(localRoot.right);
 }
 }
 public void inOrder(){
 this.inOrder(this.root);
 }
 //先序遍歷方法遞歸實(shí)現(xiàn)
 public void preOrder(Node localRoot){
 if(localRoot!=null){
 System.out.print(localRoot.data+" ");
 preOrder(localRoot.left);
 preOrder(localRoot.right);
 }
 }
 public void preOrder(){
 this.preOrder(this.root);
 }
 //后序遍歷方法遞歸實(shí)現(xiàn)
 public void postOrder(Node localRoot){
 if(localRoot!=null){
 postOrder(localRoot.left);
 postOrder(localRoot.right);
 System.out.print(localRoot.data+" ");
 }
 }
 public void postOrder(){
 this.postOrder(this.root);
 }
 /**
 * 層序遍歷二叉樹：現(xiàn)將根結(jié)點(diǎn)放入隊(duì)列中，然后每次都從隊(duì)列中取一個結(jié)點(diǎn)打印該結(jié)點(diǎn)的值，
 * 若這個結(jié)點(diǎn)有子結(jié)點(diǎn)，則將它的子結(jié)點(diǎn)放入隊(duì)列尾，直到隊(duì)列為空
 */
 public void layerTranverse(){
 if(this.root==null)
 return;
 Queue<Node> q=new LinkedList<Node>();
 q.add(this.root);
 while(!q.isEmpty()){
 Node n=q.poll();
 System.out.print(n.data+" ");
 if(n.left!=null)
 q.add(n.left);
 if(n.right!=null)
 q.add(n.right);
 }
 }
 private int maxLen=0;
 private int max(int a,int b){
 return a>b?a:b;
 }
 public void findMaxDistance(Node root){
 if(root==null)
 return;
 if(root.left==null)
 root.leftMaxDistance=0;
 if(root.right==null)
 root.rightMaxDistance=0;
 if(root.left!=null)
 findMaxDistance(root.left);
 if(root.right!=null)
 findMaxDistance(root.right);
 //計算左字樹中距離根結(jié)點(diǎn)的最大距離
 if(root.left!=null)
 root.leftMaxDistance=max(root.left.leftMaxDistance, root.left.rightMaxDistance)+1;
 //計算右字樹中距離根結(jié)點(diǎn)的最大距離
 if(root.right!=null)
 root.rightMaxDistance=max(root.right.leftMaxDistance, root.right.rightMaxDistance)+1;
 //獲取二叉樹所有結(jié)點(diǎn)的最大距離
 if(root.leftMaxDistance+root.rightMaxDistance>maxLen){
maxLen=root.leftMaxDistance+root.rightMaxDistance;
 }
 }
 public static void main(String[] args) {
 BinaryTree biTree=new BinaryTree();
 int[] data={2,8,7,4,9,3,1,6,7,5};
 biTree.buildTree(data);
 System.out.print("二叉樹的中序遍歷：");
 biTree.inOrder();
 System.out.println();
 System.out.print("二叉樹的先序遍歷：");
 biTree.preOrder();
 System.out.println();
 System.out.print("二叉樹的后序遍歷：");
 biTree.postOrder();
 System.out.println();
 System.out.print("二叉樹的層序遍歷：");
 biTree.layerTranverse();
 System.out.println();
 biTree.findMaxDistance(biTree.root);
 System.out.println("二叉樹中結(jié)點(diǎn)的最大距離："+biTree.maxLen); 
 }
}