二叉排序树的实现与基本操作

 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 * 实现二叉排序树，包括插入、中序遍历、先序遍历、后序遍历、计算所有节点的最大距离的功能 */ 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 q=new LinkedList(); 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); //计算左字树中距离根结点的最大距离 if(root.left!=null) root.leftMaxDistance=max(root.left.leftMaxDistance, root.left.rightMaxDistance)+1; //计算右字树中距离根结点的最大距离 if(root.right!=null) root.rightMaxDistance=max(root.right.leftMaxDistance, root.right.rightMaxDistance)+1; //获取二叉树所有结点的最大距离 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("二叉树中结点的最大距离："+biTree.maxLen); } }