1.实现思路
- 根据二分搜索树的性质，存储的数据都是根据数据大小排序的，因此存储的元素都可以通过比较进行相应操作
- 二分搜索树定义成泛型，可以存储各种类型的结构，表现形式上是一种集合。
2.实现代码
- 定义一个类代表该二分搜索树，类中有一个私有类为结点类，对结点进行定义。
public class BST2<E extends Comparable<E>> {
/**
* 结点定义
*/
private class Node {
//该结点存储的元素
private E e;
//结点的右孩子
private Node right;
//结点的左孩子
private Node left;
private Node(E e) {
this.e = e;
left = null;
right = null;
}
}
//根节点
private Node root;
//保存存储元素数量
private int size;
//二分搜索树构造方法
public BST2() {
this.root = null;
this.size = 0;
}
}
1.实现Comparable<E>接口，使存储的元素可以比较
2.当初始化一个二分搜索树时，会先创建一个根节点
- 实现二分搜索树的基础方法
/**
* 二分搜索树元素数量
* @return ：
*/
public int size() {
return this.size;
}
/**
* 二分搜索树是否为空
* @return ：
*/
public boolean isEmpty() {
return size == 0;
}
- 实现二分搜索树的添加
/**
* 向二叉树中添加一个元素
*
* @param e ：需要添加的结点
*/
public void add(E e) {
root = add(root, e);
}
/**
* 返回插入元素的二叉搜索树的根节点
*
* @param node ：
* @param e ：需要添加的结点
*/
private Node add(Node node, E e) {
if (node == null) {
size++;
return new Node(e);
}
//若添加的结点小于node，往node的左子树上添加该节点
if (e.compareTo(node.e) < 0) {
node.left = add(node.left, e);
}//若添加的结点大于node，往node的右子树上添加该节点
else if (e.compareTo(node.e) > 0) {
node.right = add(node.right, e);
}
return node;
}
1.添加方法中，若添加的元素已经存在，采取不进行任何操作，所以该二分搜索树默认所有的元素都不重复
2.在私有add方法中，采用递归方式向以root为根结点的二分搜索树中添加一个新元素，并返回这个二分搜索树的根节点root.
二分搜索树add
- 实现二分搜索树的查询
/**
* 二分搜索树中是否拥有该元素
*
* @param e ：
* @return ：
*/
public boolean contains(E e) {
return contains(root, e);
}
/**
* 查询以node为根节点的二叉树是否拥有该元素
*
* @param node ：
* @param e ：
* @return ：
*/
private boolean contains(Node node, E e) {
if (node == null) {
return false;
}
if (e.compareTo(node.e) == 0) {
return true;
}
if (e.compareTo(node.e) < 0) {
return contains(node.left, e);
}//(e.compareTo(node.e) > 0)
else {
return contains(node.right, e);
}
}
- 实现二分搜索树的删除
/**
* 删除二分搜索树中为e的结点
*/
public void remove(E e) {
root = remove(root, e);
}
/**
* 删除以node为根的二分搜索树中值为e的结点，递归算法
* 返回删除节点后新的二分搜索树的根
*
* @param node：
* @param e：
* @return ：
*/
private Node remove(Node node, E e) {
if (node == null) {
return null;
}
//首先确定要删除的结点
//若删除结点比当前node结点小，遍历node的左子树;
//并让删除的左子树结点的孩子继承左子树的位置
if (e.compareTo(node.e) < 0) {
node.left = remove(node.left, e);
return node;
}
//若删除结点比当前结点大，遍历node的右子树
//并让删除的右子树结点的孩子继承右子树的位置
else if (e.compareTo(node.e) > 0) {
node.right = remove(node.right, e);
return node;
}
//若删除结点为当前结点，删除该结点，并让其孩子继承其位置
else {
//若删除结点的左孩子为空，让其右孩子继承其位置
if (node.left == null) {
Node rightNode = node.right;
node.right = null;
size--;
return rightNode;
}
//若删除结点的右孩子为空，则让其左孩子继承其位置
if(node.right == null){
Node leftNode = node.left;
node.left = null;
size--;
return leftNode;
}
//若删除结点左右子树都不为空
//找到删除节点的后继：找到待删除结点右子树中最小的结点
//用这个后继结点代替待删除节点
Node successor = minValue(node.right);
//在这个二分搜索树中删除这个后继节点,得到的新的二叉搜索树为这个后继的右孩子
successor.right = removeMin(node.right);
//待删除结点的左孩子成为后继结点的左孩子
successor.left = node.left;
//待删除结点脱离二叉搜索树
node.left = node.right = null;
//让这个后继结点继承待删除node结点的位置
return successor;
}
}
/**
* 获取以node为根节点的二叉树的最小元素
*
* @param node ：
* @return ：
*/
private Node minValue(Node node) {
if (node.left == null) {
return node;
}
return minValue(node.left);
}
/**
* 删除以node为根的二分搜索树的最小节点
* 返回删除结点后新的二分搜索树的根
* 右孩子继承被删除结点的位置，并返回删除最小值后的二叉树的根结点。
*
* @param node ：
* @return ：
*/
private Node removeMin(Node node) {
//若该结点的左结点为空，说明该结点为最小值，保留该结点的右子树
if (node.left == null) {
//保留该结点的右子树
Node rightNode = node.right;
node.right = null;
size--;
return rightNode;
}
//判断该结点的左子树是否为最小结点
//该结点的左子树为删除最小结点的右子树
node.left = removeMin(node.left);
return node;
}
1.删除结点需要考虑三种情况下：(双孩子为空，包含在只有某一个孩子情况中)
①.删除的结点只有左子树，右子树为空
①.删除的结点只有右子树，左子树为空
①.删除的结点双孩子皆不为空
2.删除结点的后继(谁继承删除结点的位置)
①.只有左子树，说明后继为左儿子
①.只有右子树，说明后继为右儿子
①.两个孩子的话，后继可以为⑴左子树中最大的结点 或者 ⑵右子树中最小的结点(因为要保证二分搜索树的性质)：代码中采用右子树中最小的结点
二分搜索树删除
- 实现二分搜索树的遍历
6.1. 前序遍历
6.2. 中序遍历/** * 二叉搜索树的前序遍历：最常规 */ public void preOrder() { preOrder(root); } /** * 前序遍历以node为根的二分搜索树 * * @param node ： */ private void preOrder(Node node) { if (node == null) { return; } //先根操作->左孩子遍历->右孩子遍历 System.out.println(node.e); preOrder(node.left); preOrder(node.right); }
6.3.后序遍历/** * 二叉树的中序遍历：遍历时排序 */ public void inOrder() { inOrder(root); } /** * 中序遍历以node为根的二分搜索树 * * @param node : */ private void inOrder(Node node) { if (node == null) { return; } inOrder(node.left); System.out.println(node.e); inOrder(node.right); }
6.4.层序遍历/** * 二叉树的后序遍历：内存释放，分治排序 */ public void postOrder() { postOrder(root); } /** * 后序遍历以node为根的二分搜索树 * * @param node : */ private void postOrder(Node node) { if (node == null) { return; } postOrder(node.left); postOrder(node.right); System.out.println(node.e); }/** * 层序遍历：广度优先遍历 */ public void levelOrder() { Queue<Node> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { Node node = queue.poll(); System.out.println(node.e); if (node.left != null) { queue.add(node.left); } if (node.right != null) { queue.add(node.right); } } }1.使用队列实现层序遍历，先进先出
2.先当放入根结点，弹出根结点的值时，判断其左右儿子，不为空，压入栈底
3.此时栈顶为根左儿子，弹出栈，并将其不为空左右儿子压入栈底，之后栈顶为根右儿子，弹出站，同时将其左右儿子压入栈底。
4.之后重复上述3过程，直至所有子树孩子都为空时，栈为空结束
3.时间复杂度
- 以深度为h的排序满二叉树共有n个结点来说。其增删查的时间复杂度为深度O(h)，即结点在第几层需要和几个结点进行比较；而满二叉树拥有2h-1个结点.
第h层有多少个结点：n = 2h-1 ---> h = log2(n+1)
时间复杂度：O(h) = O(logn)
4.二分搜索树的缺陷
-
在极端的情况下，二分搜索树会退化成链表，此时的时间复杂度变成O(N)
即所有的元素都是排过序的，例如把，元素1，2，3，4，5添加到二分搜索树
极端二叉树.png
如何维持二叉树的时间复杂度在O(logn),就需要维护二叉树的平衡，所以便会需要平衡二叉树。
