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

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

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

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

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

以下代码实现了：

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

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

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