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

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

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

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

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

以下代码实现了：

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

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<current.data){
 current=current.left;
 if(current==null){
 parent.left=newNode;
 return;
 }
 }else{
 current=current.right;
 if (current==null) {
 parent.right=newNode;
 return;
 }
 }
 }
 }
 }
 //将数值输入构建二叉树
 public void buildTree(int[] data){
 for (int i = 0; i < data.length; i++) {
 insert(data[i]);
 }
 }
 //中序遍历方法递归实现
 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);
 }
 //先序遍历方法递归实现
 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);
 }
 //后序遍历方法递归实现
 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);
 }
 /**
 * 层序遍历二叉树：现将根结点放入队列中，然后每次都从队列中取一个结点打印该结点的值，
 * 若这个结点有子结点，则将它的子结点放入队列尾，直到队列为空
 */
 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);
 //计算左字树中距离根结点的最大距离
 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); 
 }
}

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