童鞋们好！今天，我们来学习面试常考知识点：数据结构之二分搜索树！记得做好笔记哦！
关于二分搜索树
二分搜索树是一颗二叉树，满足二叉树的所有定义。
二分搜索树每个节点左子树值都小于该节点值，每个节点右子树值都大于该节点值。
任意节点每颗子树都满足二分搜索树定义。
二分搜索树如此定义的意义何在？
二分搜索树实际上是做数据整理。因为左右子树的值和根节点关系，我们每次查找元素在根节点进行对比后，每次几乎能排除掉近一半的查找范围，大大加快了查询速度。插入元素时也一样，比如，如果我们知道超市二楼卖水果，就不用在一楼找了，大大加快了购买速度。
为了达到这样的高效，树结构也需要每个节点间具备可比较性。而链表数据结构就没有这类要求，所以有得必有失。
定义二分搜索树类
向上滑动阅览
publicclassBinarySearchTreeE{
//节点内部类
privatestaticclassNodeE{
Eelement;//当前节点
NodeEleft;//左子节点
NodeEright;//右子节点
NodeEparent;//父节点
publicNode(Eelement,NodeEparent){
this.element=element;
this.parent=parent;
}
}
}
添加属性及相应接口；
向上滑动阅览
publicclassBinarySearchTreeE{privateintsize;//记录个数privateNodeEroot;//根节点//树的大小publicintsize(){returnsize;}//是否为空的方法publicbooleanisEmpty(){returnsize==0;}//添加节点方法publicvoidadd(Eelement){}//节点内部类privatestaticclassNodeE{Eelement;//当前节点NodeEleft;//左子节点NodeEright;//右子节点NodeEparent;//父节点publicNode(Eelement,NodeEparent){this.element=element;this.parent=parent;}}}
因二分搜索树节点不能为null，所以添加判断方法；
向上滑动阅览
publicclassBinarySearchTreeE{
privateintsize;//记录个数
privateNodeEroot;//根节点
//树的大小
publicintsize(){
returnsize;
}
//是否为空的方法
publicbooleanisEmpty(){
returnsize==0;
}
//添加节点方法
publicvoidadd(Eelement){}
//判断节点不能为null
privatevoidelementCheckNull(Eelement){
if(element==null){
thrownewIllegalArgumentException("elementmustnotbenull");
}
}
//节点内部类
privatestaticclassNodeE{
Eelement;//当前节点
NodeEleft;//左子节点
NodeEright;//右子节点
NodeEparent;//父节点
publicNode(Eelement,NodeEparent){
this.element=element;
this.parent=parent;
}
}
}
add方法，添加节点设计。添加步骤如下：
找到父节点
创建新节点node
parent.left=node或parent.right=node
相等的值怎么处理？方案：return或覆盖
向上滑动阅览
publicclassBinarySearchTreeE{
...
//添加节点方法
publicvoidadd(Eelement){
//判断添加的是否为空
elementCheckNull(element);
//添加的是第一个节点
if(root==null){
root=newNode(element,null);
size++;
return;
}
//添加的不是第一个节点
//定义一个父节点
NodeEparent=root;
NodeEnode=root;
int