欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2024-03-11 11:15:49
二叉排序树又称二叉查找树。它或者是一颗空树,或者是具有以下性质的二叉树: ①如果左子树不空,那么左子树上所有结点的值均小于它的根结点的值; ②如果右子树不空,那么右子树...

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

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

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

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

以下代码实现了:

  • 二叉树的构建
  • 二叉树的中、前、后、层序遍历
  • 二叉树中结点的最大距离
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); 
 }
}

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