知识导航
一.二叉搜索树背景
对于动态数组来说，查找元素，从头向后遍历最好情况是O(1),最坏情况是O(n).平均下来复杂度是O(n)
如果维护一个有序的动态数组，使用二分搜索，最坏时间复杂度：O(logn)
但是添加、删除的平均时间复杂度是 O(n)
所以对于动态数组其实有进一步优化的空间
但是如果用二叉搜索树，由于根节点，左边都是比根节点小的元素，根节点右边都是比根节点大的元素。最坏的情况下也只是之前一半的执行次数。上一章我们提到了二叉树的高度为，floor(log2n)+1（2的n次取对数在向下取整加一）所以最坏复杂度才为O(log2n)–>无论是添加还是删除;
二.二叉搜索树的性质
? 二叉搜索树是二叉树的一种，是应用非常广泛的一种二叉树，英文简称为 BST
任意一个节点的值都大于其左子树所有节点的值
?任意一个节点的值都小于其右子树所有节点的值
它的左右子树也是一棵二叉搜索树
? 二叉搜索树可以大大提高搜索数据的效率
? 二叉搜索树存储的元素必须具备可比较性
😅比如 int、double 等
🤡如果是自定义类型，需要指定比较方式(对于类型的比较
有两种方式---->（1）通过类实现Comparable接口，重写compareTo方法指定比较逻辑（或者直接利用Comparable自带的）
（2）通过比较器重写比较逻辑
)
🤡不允许为 null
三.二叉搜索树的接口设计
? int size() // 元素的数量
? boolean isEmpty() // 是否为空
? void clear() // 清空所有元素
? void add(E element) // 添加元素
? void remove(E element) // 删除元素
? boolean contains(E element)// 是否包含某元素
四.添加元素
🌟🌟添加元素，肯定是添加到叶子节点，所以只要只要找到可以存放特定元素的位置，放置元素即可。但是设计并不是直接找到这个叶子节点，而是找到该位置节点的父节点位置，然后通过parent.left或parnet.right=new Node<>(element,null)
private void elementNullCheck(E element)
{
if(element==null){
throw new UnsupportedOperationException("element="+null+"不合法");
}
}
public void add(E element){
//element可能为空，为避免其为空要进行事先的检验
elementNullCheck(element);
if(this.root==null)
{
root=new Node<>(element,null);
size++;
return;
}
//添加的不是第一个节点
//所以要从根接待你往下去寻找合适的位置，首先先记录根节;
Node<E> parent1=this.root;//这里只是初始化一下，写成null也可以
//node可以认为是一个工具节点，去寻找可以存放的位置
Node<E> node=this.root;
int ins=0;
while (node!=null)
{
ins=compare(element,node.element);
//实时记录目标节点的根节点
parent1=node;
if (ins>0){
node=node.right;
}else if(ins<0){
node=node.left;
}else {
return;
}
}
Node<E> newNode=new Node<>(element,parent1);
//注意节点的插入位置要与前面一致
if (ins>0){
parent1.right=newNode;
}else {
parent1.left=newNode;
}
}
//自定义比较标准：如果e1>e2返回正数，e1<e2返回负数，相等返回0;
private int compare(E e1,E e2){
/**
* 两种方法的优化：如果传入了构造器则优先靠考虑用构造器的逻辑，如果没有传入构造器，则使用
* Comparable<E>接口本身的逻辑进行判定
*/
if(comparator!=null) {
return comparator.compare(e1, e2);
}
return ((java.lang.Comparable<E>)e1).compareTo(e2);
}
设计点： 比较器与Comparable接口的结合设计
private int compare(E e1,E e2){
/**
* 两种方法的优化：如果传入了构造器则优先靠考虑用构造器的逻辑，如果没有传入构造器，则使用
* Comparable<E>接口本身的逻辑进行判定
*/
if(comparator!=null) {
return comparator.compare(e1, e2);
}
return ((java.lang.Comparable<E>)e1).compareTo(e2);
}
五.删除元素
（1）删除度为2节点
将删除度为2的节点转化为删除度为1的叶子节点
删除的节点是度为二的节点
1.找到要删除的节点
2.找到该节点的前驱（后继），用前驱（后继）覆盖要删除的值
3.删除相应的前驱（后继）
4.如果一个节点的度为 2，那么
5.它的前驱、后继节点的度只可能是 1 和 0
（2）删除度为1节点
(2)删除的节点是度为一的节点
1.找到要删除的节点node
2.找到要删除的节点的下一个节点child
以node是左子节点为例
node.parent.left=child
child.parent=node.parent;
（3）删除度为0节点
（1）删除的节点是叶子节点
1.找到叶子节点node
2.判断此叶子节点是它父节点的左树还是右树
3.直接删除
删除代码
//提供给外界的接口
public void remove(E element){
Node<E> s= node(element);
remove(s);
}
//具体实施删除操作
private void remove(Node<E> node){
//处理顺序先难后易->先处理度为2的时候
if (node==null)return;
//度为2
if(node.doubleChildren()){
//找到前驱节点
Node<E> s=preTarget(node);
node.element=s.element;
//可以和其他情况达到统一，到时候直接删除node
node=s;
}
//删除node节点(此时node已经指向前驱或者后继，度只可能为1或0)
Node<E> child=node.left==null?node.right:node.left;
if(child!=null){
//能进到这里说明不是叶子节点
//更新parent,删除node
child.parent=node.parent;
if (node.parent==null){//node是度为一节点，且是根节点
//类似链表，删除头节点
//root指向child
root=child;
//问：不用删除之前的根节点对象吗；child.parent=node.parent;更新就完成了
}else if(node==node.parent.left){//node是度为一节点，且不是根节点，在父节点的左子树
node.parent.left=child;
}else if(node==node.parent.right){
node.parent.right=child;
}
//往后都是被叶子节点的几种情况
}else if(node.parent==null){
root=null;
} else {
//删除叶子节点（不是根节点）
if(node==node.parent.left){
node.parent.left=null;
}else {
node.parent.right=null;
}
}
}
//查找要删除的节点
private Node<E> node(E element){
Node<E> node=this.root;
while (node != null) {
//这个要写在循环内因为node是时刻更新的
int cmp=compare(element,node.element);
if (cmp == 0) {
return node;
} else if (cmp < 0) {
node = node.left;
} else {
node = node.right;
}
}
return null;
}
六.整体代码
package com.Domain;
/**
* ? int size() // 元素的数量
* ? boolean isEmpty() // 是否为空
* ? void clear() // 清空所有元素
* ? void add(E element) // 添加元素
* ? void remove(E element) // 删除元素
* ? boolean contains(E element)// 是否包含某元素
* @param <E>
*/
import Util.printer.BinaryTreeInfo;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
/**
* 比较的两种方式：1.Comparable接口
* （1）让BinarySearch类严格遵守Comparable方法
* public class BinarySearch<E extends Comparable>
* （也就是比较类型必须重写Comparable中的compareTo方法）
* （2）Person必须严格遵守Comparable接口，实现这个接口并重写compareTo方法
*public class Person<E> implements Comparable<Person>，括号注明要比较的类型
* 比较的两种方式：2.Comparator比较器
* （1）在BinarySearch中创建比较器类型，并设计构造方法
* （2）在main函数中设计比较器类：
* private static class personComparator implements Comparator<Person>注明比较类型
* （3）通过构造方法传入比较器。
* BinarySearch<Person> list=new BinarySearch<>(new personComparator());
* （4）compare调用自己比较器中的方法进行比较
* private int compare(E e1,E e2){
* return comparator.compare(e1,e2);
* }
* 比较器的优点：不用拘泥于Comparable固定的比较逻辑（一次只能按照一种逻辑，避免反复重写），
* 可以根据需要定义重写多中逻辑，只要传入的构造器不同就可以按不同的逻辑执行
*
*
* 完美结合：l08行（不一开始就写死）
* @param <E>
*/
@SuppressWarnings("unchecked")
public class BinarySearch<E> {
private int size;//节点个数
private Node<E> root;//根节点
private Comparator<E> comparator;
public BinarySearch (){this(null);};
public BinarySearch(Comparator<E> comparator){
this.comparator=comparator;
}
public int size(){
return this.size;
}
public boolean isEmpty(){
return this.size==0;
}
public void clear(){
size=0;
}
private void elementNullCheck(E element)
{
if(element==null){
throw new UnsupportedOperationException("element="+null+"不合法");
}
}
public void add(E element){
//element可能为空，为避免其为空要进行事先的检验
elementNullCheck(element);
if(this.root==null)
{
root=new Node<>(element,null);
size++;
return;
}
//添加的不是第一个节点
//所以要从根接待你往下去寻找合适的位置，首先先记录根节;
Node<E> parent1=this.root;//这里只是初始化一下，写成null也可以
//node可以认为是一个工具节点，去寻找可以存放的位置
Node<E> node=this.root;
int ins=0;
while (node!=null)
{
ins=compare(element,node.element);
//实时记录目标节点的根节点
parent1=node;
if (ins>0){
node=node.right;
}else if(ins<0){
node=node.left;
}else {
return;
}
}
Node<E> newNode=new Node<>(element,parent1);
//注意节点的插入位置要与前面一致
if (ins>0){
parent1.right=newNode;
}else {
parent1.left=newNode;
}
}
//自定义比较标准：如果e1>e2返回正数，e1<e2返回负数，相等返回0;
private int compare(E e1,E e2){
/**
* 两种方法的优化：如果传入了构造器则优先靠考虑用构造器的逻辑，如果没有传入构造器，则使用
* Comparable<E>接口本身的逻辑进行判定
*/
if(comparator!=null) {
return comparator.compare(e1, e2);
}
return ((java.lang.Comparable<E>)e1).compareTo(e2);
}
/**
* 删除树的节点：
* （1）删除的节点是叶子节点
*1.找到叶子节点node
* 2.判断此叶子节点是它父节点的左树还是右树
* 3.直接删除
* node==node.parent.left-->node.parent.left=null;
* node==node.parent.right-->node.parent.right=null;
* (2)删除的节点是度为一的节点
* 1.找到要删除的节点node
* 2.找到要删除的节点的下一个节点child
* 以node是左子节点为例
* node.parent.left=child
* child.parent=node.parent;
* (3)删除的节点是度为二的节点
*1.找到要删除的节点
* 2.找到该节点的前驱（后继），用前驱（后继）覆盖要删除的值
* 2.删除相应的前驱（后继）
* ? 如果一个节点的度为 2，那么
* ?它的前驱、后继节点的度只可能是 1 和 0
* @param element
*/
//提供给外界的接口
public void remove(E element){
Node<E> s= node(element);
remove(s);
}
//具体实施删除操作
private void remove(Node<E> node){
//处理顺序先难后易->先处理度为2的时候
if (node==null)return;
//度为2
if(node.doubleChildren()){
//找到前驱节点
Node<E> s=preTarget(node);
node.element=s.element;
//可以和其他情况达到统一，到时候直接删除node
node=s;
}
//删除node节点(此时node已经指向前驱或者后继，度只可能为1或0)
Node<E> child=node.left==null?node.right:node.left;
if(child!=null){
//能进到这里说明不是叶子节点
//更新parent,删除node
child.parent=node.parent;
if (node.parent==null){//node是度为一节点，且是根节点
//类似链表，删除头节点
//root指向child
root=child;
//问：不用删除之前的根节点对象吗；child.parent=node.parent;更新就完成了
}else if(node==node.parent.left){//node是度为一节点，且不是根节点，在父节点的左子树
node.parent.left=child;
}else if(node==node.parent.right){
node.parent.right=child;
}
//往后都是被叶子节点的几种情况
}else if(node.parent==null){
root=null;
} else {
//删除叶子节点（不是根节点）
if(node==node.parent.left){
node.parent.left=null;
}else {
node.parent.right=null;
}
}
}
//查找要删除的节点
private Node<E> node(E element){
Node<E> node=this.root;
while (node != null) {
//这个要写在循环内因为node是时刻更新的
int cmp=compare(element,node.element);
if (cmp == 0) {
return node;
} else if (cmp < 0) {
node = node.left;
} else {
node = node.right;
}
}
return null;
}
public boolean contains(E element){
return false;
}
@Override
public Object root() {
return root;
}
@Override
public Object left(Object node) {
return ((Node)node).left;
}
@Override
public Object right(Object node) {
return ((Node)node).right;
}
//告诉打印器打印的内容；
@Override
public Object string(Object node) {
//在原有基础上打印父节点，便于对结果的分析，维护父节点，减小产生bug的概率
Node<E> myNode=(Node<E>)node;
String parentString=(myNode.parent==null?null:myNode.parent.element.toString());
return myNode.element+"(p)"+parentString;
}
//进一步改进，限制控制（设置阀门）
// 为控制遍历，需要一个变量存储visit的boolean的返回值，一旦返回为true 终止便利。为了统一这个变量将其放在接口中
//又因为接口不能设置成员变量所以将其改变为抽象方法：抽象方法和接口有异曲同工之秒
public abstract static class Visitor<E>{
abstract boolean visit(E element);
//方法改为抽象类型，否则必须实例化
boolean stop;
}
public void preDisplay1(Visitor<E> visitor) {
if (visitor==null){
return;
}
preDisplay(this.root,visitor);
}
private void preDisplay(Node<E> node,Visitor<E> visitor) {
//stop初始默认为false
if(node==null||visitor.stop){
return;
}
//处理选中的遍历元素：好处——>可以在main()函数里重写visit()方法，可以对选定元素进行任意操作
//根据主函数中重写的visit()方法，对stop进行更新 ，如果为true，直接终止递归
visitor.stop=visitor.visit(node.element);
preDisplay(node.left,visitor);
preDisplay(node.right,visitor);
}
//中序遍历
public void inOderDisplay(Visitor<E> visitor){
if(visitor==null)
{
return;
}
inOderDisplay1(this.root,visitor);
}
private void inOderDisplay1(Node<E> node,Visitor<E>visitor)
{
if (node==null||visitor.stop)
{
return;
}
inOderDisplay1(node.left,visitor);
visitor.stop=visitor.visit(node.element);
//减少复杂度，只要stop一不符合直接终止方法,不用在执行一下的递归
if(visitor.stop){
return;
}
inOderDisplay1(node.right,visitor);
}
//后序遍历
public void postDisplay(Visitor<E> visitor){
if(visitor==null)
{
return;
}
postDisplay1(this.root,visitor);
}
private void postDisplay1(Node<E> node,Visitor<E> visitor) {
if (node==null||visitor.stop){
return;
}
postDisplay1(node.left,visitor);
postDisplay1(node.right,visitor);
//减少运行次数：上一次已经是true了所以没必要在进行了
if(visitor.stop)
{
return;
}
visitor.stop=visitor.visit(node.element);
}
//重点：层序遍历
public void levelDisplay(Visitor<E>visitor){
Queue<Node<E>> queue=new LinkedList<>();
if (this.root==null||visitor==null)
{
return;
}
queue.offer(root);
while (!queue.isEmpty()){
Node<E> node=queue.poll();
//在开发中还有一种需求就是：遍历二叉树，但是控制遍历的长度，比如说限制遍历到2，或者只遍历前三个元素
//此时就需要有一个开关（阀门）来进行控制-->通过boolean类性
if(visitor.visit(node.element)){
return;
}
if (node.left!=null) {
queue.offer(node.left);
}
if (node.right!=null){
queue.offer(node.right);
}
}
}
//添加判断叶子节点的方法
public static class Node<E>{
E element;
Node<E> left;
Node<E> right;
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 doubleChildren(){
return left!=null&&right!=null;
}
}
//判断是否是完全二叉树
public boolean isComplete(){
if(this.root==null){
return false;
}
Queue<Node<E>> queue=new LinkedList<>();
queue.offer(root);
boolean leaf=false;
while (!queue.isEmpty()){
Node<E> node=queue.poll();
/**
* leaf->true要求为叶子节点
* !node.isLeaf()如果成立->node节点并不是叶子节点->不是完全二叉树
*/
if(!node.isLeaf()&&leaf){
return false;
}
if (node.left!=null){
queue.offer(node.left);
}else if(node.right!=null)
{
return false;
}
if (node.right!=null){
queue.offer(node.right);
}else{
leaf=true;
}
}
return true;
}
/**
* 计算二叉树的高度
*
* 方法一：递归——>二叉树深度=Math.max(左子树深度，右子树深度）+1（+1就是加上本身这一层）
public int height(){
return height(root);
}
private int height(Node<E>node){
if(node==null){
return 0;
}
return 1+Math.max(height(node.left),height(node.right));
}
方法二;利用层序遍历统计层数
*/
public int height(){
if(root==null){
return 0;
}
Queue<Node<E>> queue=new LinkedList<>();
queue.offer(root);
//记录高度
int height=0;
//记录每层的元素
int levelSize=1;
while (!queue.isEmpty()){
Node<E> node=queue.poll();
levelSize--;
if(node.left!=null){
queue.offer(node.left);
}
if (node.right!=null){
queue.offer(node.right);
}
//换层，高度加一
if (levelSize==0){
levelSize=queue.size();
height++;
}
}
return height;
}
/**
* 重构而二叉树
* 前序遍历+中序遍历
* 后序遍历+中序遍历
*
* 前序遍历+后序遍历（前提：是一颗真序二叉树）
*/
/**
* 前缀节+后继节点
*/
//后继节点就是前驱节点代码中left和right对换
public Node<E> preTarget(Node<E> node){
if (node==null){
return null;
}
Node<E> p=node.left;
//该节点有左子树的情况，直接找左子树的最右节点
if (p!=null) {
while (p.right != null) {
//遍历左子树找到最右边的最后一个节点
p = p.right;
}
return p;
}
//到这里说明没有左子树。遍历右子树（从右子树最左边的节点开始）
//从该节点通过parent不断向上遍历，只到发现某个节点将目标节点当作右节点（找到比节点小的前一个节点）
while (node.parent!=null&&node==node.parent.left)
{
node=node.parent;
}
//走到这有两种情况1.node.parent==null,node=node.parent.right
//如果第一种情况，没有前驱节点返回null。
return node.parent;
}
}
