二叉排序树的实现与基本操作
程序员文章站
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); } }
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,同时也希望多多支持!
上一篇: SpringMVC拦截器实现登录认证
下一篇: kubernetes service