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

二叉排序树又称二叉查找树。它或者是一颗空树，或者是具有以下性质的二叉树：

①如果左子树不空，那么左子树上所有结点的值均小于它的根结点的值；

②如果右子树不空，那么右子树上所有结点的值均大于它的根结点的值；

③左右子树也分别为二叉排序树。

以下代码实现了：

• 二叉树的构建
• 二叉树的中、前、后、层序遍历
• 二叉树中结点的最大距离

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;
 }
}

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); 
 }
}

以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，同时也希望多多支持考高分网！