对于BinarySearchTree类，一般的设计思想是使用 BinaryTree类作为BinarySearchTree类的父类，在BinaryTree类中实现二叉树的通用功能，再在BinarySearchTree类中实现它的特有功能。

BinaryTree类

类定义中的成员：

对BinaryTree类的定义使用一个内部的节点类对每个节点进行定义，包含E类的element，和三个Node类的指针left,right,parent.其中isLeaf方法和hasTwoChildren用于判断节点类型

在这里插入代码片	 //节点类protected static class Node<E>{E element;Node<E> right ;Node<E> left ;@SuppressWarnings("unused")Node<E> parent;public Node(E element,Node<E> parent) {this.element=element;this.parent=parent;}public boolean isLeaf() {return left==null&&right==null;}public boolean hasTwoChildren() {return left!=null&&right!=null;}}

在对二叉树的遍历过程中，使用一个Visitor接口，用于用户自定义遍历逻辑，即用户可在其他类中通过Visitor接口中的visit方法定义对遍历到的元素进行怎样的操作，在遍历过程中，为使用户能够自定义遍历结束条件（即不需要每次遍历都遍历整棵树），特维持一个Boolean的变量stop作为遍历结束依据。

二叉树需要维持一个root指针和保存树中元素个数的整型size变量，需要有能够传递遍历方式的构造方法

public class BinaryTree<E> {protected int size;protected Node<E> root;//节点类protected static class Node<E>{E element;Node<E> right ;Node<E> left ;@SuppressWarnings("unused")Node<E> parent;public Node(E element,Node<E> parent) {this.element=element;this.parent=parent;}public boolean isLeaf() {return left==null&&right==null;}public boolean hasTwoChildren() {return left!=null&&right!=null;}}

类中各个方法：

几个简单但必要的方法如下：

//检查元素是否为空protected void elementNotNullCheck(E element) {if(element==null) {throw new IllegalArgumentException("element must not null");}}public int size() {return size;}public boolean isEmpty() {return size==0;}public void clear() {root=null;size=0;}

四种遍历方法

在遍历之前，需要了解到用户遍历树的过程需要对树进行怎样的操作，为了实现用户能够传递对树中元素的操作逻辑，需要使用如下接口，该接口通过visit方法定义用于对树中元素的操作逻辑，并通过一个boolean 型变量来作为遍历结束的控制条件（因为用户并不是每次都对整棵树进行遍历）。

public static  abstract class Visitor<E>{//在此处定义一个boolean值，而不是在其他地方， 目的是获得较好的结构和实现。//每次调用遍历方法都传入一个Visitor，每个Visitor都维持一个stop变量。boolean stop;//visit 函数使用boolean返回值，如果返回true则结束遍历，如果返回false循环继续。abstract boolean visit(E elemnet);}

在定义了Visitor接口后，用户每次遍历树都需要传递遍历的逻辑，即一个Visitor类，并实现其中的vistor方法，于是四种遍历的实现如下：

前序遍历

public void preorder(Visitor<E> vistor) {if(vistor==null) return;preorderTraversal(root,vistor);}private void preorderTraversal(Node<E> node,Visitor<E> vistor) {//此处的vistor.stop是为了结束递归，即当vistor.stop==true时递归停止，函数执行结束if(node==null||vistor.stop) return;vistor.stop=vistor.visit(node.element);//每次循环保存当前的visit方法的返回值preorderTraversal(node.left,vistor);preorderTraversal(node.right,vistor);}

中序遍历

//中序遍历递归实现public void inorder(Visitor<E> vistor) {if(vistor==null) return;inorderTranversal(root,vistor);}private void inorderTranversal(Node<E> node,Visitor<E> vistor) {//此处的vistor.stop是为了结束递归，即当vistor.stop==true时递归停止，函数执行结束if(node==null||vistor.stop) return;inorderTranversal(node.left,vistor);//此处vistor.stop的作用是当node的左右子树递归中某次vistor.stop==true后，不在执行visit函数if(vistor.stop)return;//如果发现上一次循环的返回值为true则结束递归vistor.stop=vistor.visit(node.element);//每次循环保存当前的visit方法的返回值inorderTranversal(node.right,vistor);}

后序遍历

	//后序遍历递归实现public void postorder(Visitor<E> vistor) {if(vistor==null) return;postorderTranversal(root,vistor);}private void postorderTranversal(Node<E> node,Visitor<E> vistor) {//此处的vistor.stop是为了结束递归，即当vistor.stop==true时递归停止，函数执行结束if(node==null||vistor.stop) return;postorderTranversal(node.left,vistor);postorderTranversal(node.right,vistor);//此处vistor.stop的作用是当node的左右子树递归中某次vistor.stop==true后，不在执行visit函数if(vistor.stop)return;//如果发现上一次循环的返回值为true则结束递归vistor.stop=vistor.visit(node.element);//每次循环保存当前的visit方法的返回值		}

层序遍历

		//层序遍历public void levelOrder(Visitor<E> vistor) {if(root ==null||vistor==null) return;Queue<Node<E>> queue=new LinkedList<>();//创建一颗树queue.add(root);//头结点入队Node<E> node=null;while(!queue.isEmpty()) {//当队列不为空时循环node=queue.poll();//出队操作//调用visitor指定方法if(vistor.visit(node.element))return;//入队操作if(node.left!=null) {queue.add(node.left);				}if(node.right!=null) {queue.add(node.right);				}}}

判断树是否为完全二叉树的方法：

对于一棵完全二叉树，通过分析可知，其节点类型有三种：2度节点，1度节点和0度节点。当节点为2度时，表明该节点为树中间某节点，直接让它的左右节点入队，对于1度节点，当它右指针域不为空时直接表明该树不为完全二叉树，当它的左指针域不为空时，表明在它以后每次出队的节点都必须为叶子节点，如果不为叶子节点，说明该树不是完全二叉树。

	public boolean isComplete() {if(root==null) return false;Queue<Node<E>> queue=new LinkedList<>();queue.add(root);Node<E> node=root;boolean leaf=false;while(!queue.isEmpty()) {node=queue.poll();//出队操作if(leaf&&!node.isLeaf()) {return false;}//该写法避免的重复判断if(node.left!=null) {queue.add(node.left);}else {if(node.right!=null) {//当左边不为空而右边为空时return false;}}if(node.right!=null) {queue.add(node.right);}else {//当右边为空时，表明该节点以后的节点都应该是叶子节点leaf=true;}}return true;}

求树高的方法

对于求树高函数，使用层序遍历的方法，在对二叉树的层序遍历过程分析中可知，每当遍历完一层元素，队列中剩余的元素就是下一层的全部元素，即队列中的元素个数就是下一层的元素个数。基于此，使用两个整型变量height和levelSize分别存放树高和每层元素个数，通过每次出队levelSize–，每次levelSize减到0就让height++同时用队列中的size重置levelSize，并可求得树高height。

	public int height() {if(root ==null) return 0;int height=0;int levelSize=1;//第一层有一个元素Queue<Node<E>> queue=new LinkedList<>();//创建一颗树queue.add(root);//头结点入队Node<E> node=null;while(!queue.isEmpty()) {//当队列不为空时循环node=queue.poll();//出队操作levelSize--;//入队操作if(node.left!=null) {queue.add(node.left);		}if(node.right!=null) {queue.add(node.right);				}if(levelSize==0) {levelSize=queue.size();height++;}}return height;}

打印函数

由于普通的打印无法直观看到元素之间的关系，所以重写toString方法，通过每次打印都输出prefix获得树状结构的打印结果

	@Overridepublic String toString() {StringBuffer sb=new StringBuffer();toString(root,sb,"---");return sb.toString();}private void toString(Node<E> node,StringBuffer sb,String prefix) {if(node==null) return;sb.append(prefix).append(node.element).append("\n");toString(node.left,sb,prefix+"L---");toString(node.right,sb,prefix+"R---");}

BinarySearchTree类

类中成员定义

在BinarySearchTree类中，需要有一个用于对节点域比较的方法，对于该方法，需要用户传递比较逻辑（与前面需要用户传操作元素的逻辑类似），该功能的实现方法是添加一行定义：

publicComparator<E> comparator;

然后其比较方法的函数如下，函数判断构造树的时候是否传入了一个比较器，如果传入了比较器，使用比较器定义的比较逻辑进行比较操作，如果没有传入比较器，将使用compare方法进行元素比较。对此应设置两个树的构造方法，有参构造（传比较器）和无参构造。
这种实现方法的特殊之处在于用户可以在构造树的时候传入一个自定义比较器，也可以在构造树的时候不传比较器而使用E类中实现的compare比较方法，也就是说，对于用同一个类构造的不同的树，可有不同的比较逻辑。

	@SuppressWarnings("unchecked")private int compare(E e1,E e2) {if(comparator!=null) {return comparator.compare(e1, e2);}//如果没有传入比较器，就将元素强制转换成Comparable接口类，如果转换失败，表明元素不合法，自动报错，否则完成比较操作。return ((Comparable<E>)e1).compareTo(e2);}

添加的两个构造方法：

public BinarySeachTree(){this(null);}public BinarySeachTree(Comparator<E> comparator){this.comparator =comparator;}

元素添加方法

在比较逻辑完成的情况下，添加元素的方法实现如下：

	public void add(E element) {elementNotNullCheck(element);//先检查元素是否为空//当root节点为空时if(root==null) {root=new Node<>(element,null);//此处不加<>会出现警告size++;return;}int cmp = 0;//定义为0避免警告Node<E> node=root;Node<E> parent = null;//初始为空避免警告//找到父节点while(node!=null) {parent=node;//保存父节点cmp=compare(element, node.element);if(cmp>0) {//如果待插入元素较大node=node.right;}else if(cmp<0) {//如果待插入元素较小node=node.left;}else {//如果相等，覆盖node.element=element;return;}}//将当前元素插入到父节点的指定位置if(cmp>0) {parent.right= new Node<>(element,parent); }if(cmp<0) {parent.left= new Node<>(element,parent); }size++;}

元素移除方法

对于元素移除方法，需要先有两个辅助函数， 获取某个节点的前驱节点或后继节点的函数。

获取元素的前驱节点，分为两种情况，一种是当该节点的左子节点不为空时，从其左子树依次往右节点查找，直到找到某个节点的右指针域为空，该节点即为所求的前驱节点；另种情况是左子树为空，此时该节点的前驱节点应为该节点的某祖宗节点，依次向上遍历，直到某一节点的父节点的右子节点为该节点。

	//对于中序遍历返回某个节点的前驱节点  precursor 前驱private Node<E> precursor(Node<E> node){Node<E> pre=node.left;//情况1，当node的左子节点不为空时，说明前驱节点在左子树中，依次向右遍历，直到某一节点的右子树为空，该节点即为所求if(pre!=null) {while(pre.right!=null) {pre=pre.right;				}return pre;}//情况2,，当node的左子节点为空，说明前驱节点为某一祖宗节点，判断，依次向上遍历，直到某一节点的父节点的右子节点为该节点//该情况包括如果祖宗节点中不存在某一节点的父节点的右子节点为该节点的情况返回null//第一次进行while判断语句时，如果node.parent为空，直接返回node.parent，之后每次向上，如果一直没找到node.parent.right!=node//依然返回空while(node.parent!=null&&node.parent.left==node) {node=node.parent;}return node.parent;}

后继节点逻辑类似，代码如下：

//对于中序遍历返回某个节点的后继节点protected Node<E> successor(Node<E> node){//当该节点存在右子节点时，该节点的后继在其右子树树中，从右子树的根节点依次向左遍历，知道某个节点的左子节点为空Node<E> child=node.right;if(child!=null) {while(child.left!=null) {child=child.left;}return child;}//当该节点没有右子树时，依次向其父节点遍历，直到某一个节点的父节点的左子节点为该节点时，这个节点即为所求while(node.parent!=null&&node.parent.right==node) {return node.parent;}return node.parent;}

再添加一个用于查找指定元素值的节点位置的方法：

	//查找指定E类数值的元素所在节点位置的逻辑private Node<E> node(E element){Node<E> node=root;int tmp=0;while(node!=null) {tmp=compare(element, node.element);if(tmp==0) {//当值相等时return node;}else if(tmp<0) {node=node.left;}else {//if（tmp>0)node=node.right;}}//如果能够退出循环，说明在树中没有查找到指定值return null;}

还需要一个用于删除指定节点的方法

对于节点的删除，有删除2度节点，删除1度节点和删除0度节点三种情况。如果是二度节点，先将该节点的后继（也可以写前驱）节点的值域赋值给待删除节点，然后以后的操作就删除该后继（也可以是前驱）节点。而该后继（或者前驱节点）的删除逻辑和删除度为1或0 的节点的逻辑完全相同（因为某个节点的前驱节点或者后继节点的度数只能为0或1），所以将删除该节点的逻辑和删除度为1或0 的逻辑共用。
对度为1的节点，删除操作是让该点的父节点对应的指针域指向当前节点的不为空的指针域，对于度为0 的节点，让它父节点对应指针域为空。当然，如果待删除的节点为root节点，将特殊处理。

private void remove(Node<E> node) {if(node==null) return;size--;//if(node.hasTwoChildren()) {//当该节点有两个孩子节点，即度为2时Node<E> s=successor(node);//获取该节点的后继节点node.element=s.element;//将后继节点的值域的值赋值给待删除节点，后面的过程就只需要删除这个snode=s;//后面删除s的操作换成对node的操作}//删除node的过程//此时node节点的度数要么为0要么为1,Node<E> replacement=node.left!=null?node.left:node.right;//当节点度为1时if(replacement!=null) {replacement.parent=node.parent;//这一句写在前面，而不是写在各个if语句内，因为它对各个语句都适用if(root==node) {root=replacement;//此处本应该有一句将更改后的root的parent域置空，但是这类逻辑已经在前面用replacement.parent=node.parent;//进行了统一处理，所以不再需要该逻辑}else {if(node.parent.left==node) {//node为其父的左子节点node.parent.left=replacement;}else {//node为其父的右子节点node.parent.right=replacement;}}}else {//当node的度数为0时if(root==node) {//或者写成node.parent==nullroot=null;}else {//是叶子节点但不是根节点if(node.parent.left==node) {//当前节点为其父的左子节点node.parent.left=null;}else {//当前节点为其父的右子节点node.parent.right=null;}}		}}

移除元素的方法

所以，在以上工作的基础上，删除指定元素的方法如下：

public void remove(E element) {//调用方法完成功能remove(node(element));}

判断某个元素是否存在

该判断逻辑实际上已经在node方法中出现过，所以方法代码如下：

//判断是否包含某个元素public boolean contains(E element) {//查找某个元素的逻辑已经在私有方法node中写完，直接调用即可return node(element)!=null;}