二叉查找树的定义：
二叉查找树或者是一颗空树，或者是一颗具有以下特性的非空二叉树：
1. 若左子树非空，则左子树上所有节点关键字值均小于根节点的关键字；
2. 若右子树非空，则右子树上所有节点关键字值均大于根节点的关键字；
3. 左、右子树本身也分别是一颗二叉查找树。
二叉查找树的实现，功能有：
1. 用一个数组去构建二叉查找树
2. 二叉查找树的中序遍历和层次遍历
3. 插入节点
4. 查找节点
5. 查找二叉树中的最大值和最小值
6. 得到节点的直接父节点
7. 得到节点的直接前驱和直接后继节点
8. 删除节点
import java.lang.Integer;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
/*
?* 二叉排序树（二叉查找树）的实现
?*/
public class BinarySearchTree {
? ? private TreeNode root;? //根节点
? ?
? ? public BinarySearchTree(){
? ? ? ? root = null;
? ? }
? ?
? ? //用一个数组去构建二叉查找树
? ? public TreeNode buildBST(Integer[] array){
? ? ? ? if(array.length == 0){
? ? ? ? ? ? return null;
? ? ? ? }else{
? ? ? ? ? ? root = null;? //初始化树为空树
? ? ? ? ? ? for(int i=0; i? ? ? ? ? ? ? ? root = insertNode(root,array[i]);
? ? ? ? ? ? }
? ? ? ? ? ? return root;
? ? ? ? }? ? ? ?
? ? }
? ?
? ? //在二叉查找树中插入一个数据域为data的结点，新插入的结点一定是某个叶子节点
? ? public TreeNode insertNode(TreeNode node, Integer data){
? ? ? ? if(node == null){? //原树为空，新插入的记录为根节点
? ? ? ? ? ? node = new TreeNode(data,null,null);? ? ? ?
? ? ? ? }else{
? ? ? ? ? ? if(node.getData() == data){? //树中存在相同关键字的结点,什么也不做
? ? ? ? ? ? ? ?
? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? if(node.getData() > data){? //根节点>插入数据，插入到左子树中
? ? ? ? ? ? ? ? ? ? node.setLchild(insertNode(node.getLchild(),data));
? ? ? ? ? ? ? ? }else{ //根节点<插入数据，插入到右子树中
? ? ? ? ? ? ? ? ? ? node.setRchild(insertNode(node.getRchild(),data));
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }? ? ? ?
? ? ? ? }
? ? ? ? return node;
? ? }
? ?
? ? //二叉查找树的中序遍历，可以得到一个递增的有序数列
? ? public void inOrder(TreeNode node){
? ? ? ? if(node != null){
? ? ? ? ? ? inOrder(node.getLchild());
? ? ? ? ? ? System.out.print(node.getData()+" ");
? ? ? ? ? ? inOrder(node.getRchild());
? ? ? ? }
? ? }
? ? //二叉查找树的层次遍历
? ? public void levelOrder(TreeNode root){
? ? ? ? Queue> nodeQueue = new LinkedList>();
? ? ? ? TreeNode node = null;
? ? ? ? nodeQueue.add(root);? //将根节点入队? ?
? ? ? ? while(!nodeQueue.isEmpty()){? //队列不空循环
? ? ? ? ? ? node = nodeQueue.peek();
? ? ? ? ? ? System.out.print(node.getData()+" ");
? ? ? ? ? ? nodeQueue.poll();? ? //队头元素出队
? ? ? ? ? ? if(node.getLchild() != null){? ? //左子树不空，则左子树入队列
? ? ? ? ? ? ? ? nodeQueue.add(node.getLchild());
? ? ? ? ? ? }
? ? ? ? ? ? if(node.getRchild() != null){? ? //右子树不空，则右子树入队列
? ? ? ? ? ? ? ? nodeQueue.add(node.getRchild());
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ?
? ? //查找数据域为data的结点，若不存在，返回null
? ? public TreeNode searchNode(TreeNode node, Integer data){
? ? ? ? while(node != null && node.getData() != data){
? ? ? ? ? ? if(node.getData() > data){
? ? ? ? ? ? ? ? node = node.getLchild();? //根节点>数据，向左走
? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? node = node.getRchild();? //根节点<数据，向右走
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return node;
? ? }
? ?
? ? //查找最大值：不断地寻找右子节点
? ? public TreeNode getMaxData(TreeNode node){
? ? ? ? if(node.getRchild() == null){
? ? ? ? ? ? return node;
? ? ? ? }else{
? ? ? ? ? ? return getMaxData(node.getRchild());
? ? ? ? }
? ? }
? ?
? ? //查找最小值：不断地寻找左子节点
? ? public TreeNode getMinData(TreeNode node){
? ? ? ? if(node.getLchild() == null){
? ? ? ? ? ? return node;
? ? ? ? }else{
? ? ? ? ? ? return getMinData(node.getLchild());
? ? ? ? }
? ? }
? ?
? ? //得到数据域为data的结点的直接父节点parentNode
? ? public TreeNode getParentNode(TreeNode root, Integer data){
? ? ? ? TreeNode parentNode = root;
? ? ? ? if(parentNode.getData() == data){? //根节点的父节点返回为null
? ? ? ? ? ? return null;
? ? ? ? }
? ? ? ? while(parentNode != null){
? ? ? ? ? ? //查找当前节点的父节点的左右子节点，若是相等，则返回该父节点
? ? ? ? ? ? if((parentNode.getLchild() != null && parentNode.getLchild().getData() == data) ||
? ? ? ? ? ? ? ? ? ? (parentNode.getRchild() != null && parentNode.getRchild().getData() == data)){
? ? ? ? ? ? ? ? return parentNode;
? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? if(parentNode.getData() > data){ //向左查找父节点
? ? ? ? ? ? ? ? ? ? p