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 * 實現(xiàn)二叉排序樹，包括插入、中序遍歷、先序遍歷、后序遍歷、計算所有節(jié)點的最大距離的功能 */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]); } } //中序遍歷方法遞歸實現(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); } //先序遍歷方法遞歸實現(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); } //后序遍歷方法遞歸實現(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é)點放入隊列中，然后每次都從隊列中取一個結(jié)點打印該結(jié)點的值， * 若這個結(jié)點有子結(jié)點，則將它的子結(jié)點放入隊列尾，直到隊列為空 */ 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é)點的最大距離 if(root.left!=null) root.leftMaxDistance=max(root.left.leftMaxDistance, root.left.rightMaxDistance)+1; //計算右字樹中距離根結(jié)點的最大距離 if(root.right!=null) root.rightMaxDistance=max(root.right.leftMaxDistance, root.right.rightMaxDistance)+1; //獲取二叉樹所有結(jié)點的最大距離 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é)點的最大距離："+biTree.maxLen);  }}