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

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

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

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

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

以下代码实现了：

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

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

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