- 二叉排序树相关概念以及性质
- 在二叉搜索树中添加元素:
add() - 查看二叉搜索树中是否存在某个元素 :
contains() - 找出二叉搜索树中的最小值和最小值 :
minimum()、maximum() - 删除二叉搜索树中的最小结点和最大结点:
removeMin()、removeMax() - 删除二叉搜索树中的任意结点:
remove() - 完整测试源代码
二叉查找树（Binary Search Tree），也称二叉搜索树，是指一棵空树或者具有下列性质的二叉树：
- 任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值
- 任意节点的左、右子树也分别为二叉查找树；
- 没有键值相等的节点(一般)。
相关的性质：
- 二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低,为O(log n)。
- 二叉排序树要求所有的项都能排序，要写出一个一般的类，我们需要实现
Comparable接口，使得可以使用泛型来比较任意的数据类型。注意这里不是使用equals方法来实现，根据两项相等当且仅当compareTo方法返回0。 这里给出BSTreeNode的定义结构类
public class BSTree<E extends Comparable<E>> {
private class Node{
public E e;
public Node left,right;
public Node(E e, Node left, Node right) {
this.e = e;
this.left = left;
this.right = right;
}
public Node(E e) {
this.e = e;
left = null;
right = null;
}
}
private Node root;
private int size;
public BSTree() {
root = null;
size = 0;
}
public int size(){
return size;
}
public boolean isEmpty(){
return size == 0;
}
}- 如果根节点为
null，就新建一个根节点； - 如果要插入的元素比当前访问结点
node小，而且node.left == null，就可以插入到node的左孩子那里； - 如果要插入的元素比当前访问结点
node大，而且node.right == null，就可以插入到node的右孩子那里； - 如果要插入的元素比当前访问结点
node小，而且node.left != null，就递归的去左子树插入这个值； - 如果要插入的元素比当前访问结点
node大，而且node.right != null，就递归的去右子树插入这个值；
public void add(E e){
if(root == null){
root = new Node(e);
size++;
}else {
add(root,e);
}
}
// 向以node为根的二分搜索树中插入元素，递归算法
private void add(Node node, E e) {
if(node.e.equals(e))return;
if(e.compareTo(node.e) < 0 && node.left == null){ //比node.e小
node.left = new Node(e);
size++;
return;
}else if(e.compareTo(node.e) > 0 && node.right == null){
node.right = new Node(e);
size++;
return;
}
if(e.compareTo(node.e) < 0)// e < node.e && node.left != null
add(node.left,e);
else //e > node.e && node.right != null
add(node.right,e);
}- 更加简单的写法，也就是当我们递归插入的时候，再多递归一层，当递归到空结点的时候，就插入这个结点，注意
add(Node node,E e)方法的作用: - 向以
node为根的二分搜索树中插入元素，返回插入新结点之后二分搜索树的根，我们在递归的时候要得到返回值和上一层的结点进行连接:
public void add(E e){
root = add(root,e);
}
private Node add(Node node, E e) { /**向以node为根的二分搜索树中插入元素，返回插入新结点之后二分搜索树的根 */
if(node == null) {//在这里插入
size++;
return new Node(e);
}
if(e.compareTo(node.e) < 0){
node.left = add(node.left,e); //node.left是变化的
}else if(e.compareTo(node.e) > 0){
node.right = add(node.right,e);
}
return node;
}在二叉搜索树bsTree中查找x的过程为：
- 若
bsTree是空树，则返回false； - 若
x等于bsTree的根节点的数据域之值，则查找成功； - 若
x小于bsTree的根节点的数据域之值，则搜索左子树； - 否则搜索右子树；
//query
public boolean contains(E e){
return contains(root,e);
}
private boolean contains(Node node, E e) {
if (node == null) return false;
if (e.compareTo(node.e) == 0) {
return true;
} else if (e.compareTo(node.e) < 0) {
return contains(node.left, e);
} else {
return contains(node.right, e);
}
}实现很简单就是一直往左边，或者一直忘右边走，递归和非递归实现都很简单；
//min
public E minimum(){
if(size == 0)
throw new IllegalArgumentException("BST is empty!");
return minimum(root).e;
}
private Node minimum(Node node) {
if(node.left == null)return node;
return minimum(node.left);
}
//max
public E maximum(){
if(size == 0)
throw new IllegalArgumentException("BST is empty!");
return maximum(root).e;
}
private Node maximum(Node node){
if(node.right == null)return node;
return maximum(node.right);
}先看删除最小结点：
-
如果最小结点是叶子结点，很简单直接删除即可；
-
如果不是叶子结点，就删除这个结点，并且将它的父亲和它的右孩子连接起来即可，看下图:
删除之后就是下面的样子:
注意这里的连接就是按照返回值的形式，父亲的左孩子连接上删除之后的树的根即可。
// 删除二叉搜索树中最小值所在的结点,返回最小值
public E removeMin(){
E ret = minimum();
root = removeMin(root); //remove the min node and then connect the tree
return ret;
}
private Node removeMin(Node node){/**删除掉以node为根的二叉搜索树中的最小结点,返回删除节点后新的结点的二分搜索树的根 */
if(node.left == null){ //node is min
Node rightNode = node.right;
node.right = null; //remove from the tree
size--;
return rightNode; /** 返回删除节点后新的结点的二分搜索树的根 然后上一层就可以连接上*/
}
node.left = removeMin(node.left); /** 去删除左子树, 然后我要连上你删除之后返回的新的根*/
return node; /** 返回删除之后的根 ，上一层还要连接*/
}删除最大结点同理:
public E removeMax(){
E ret = maximum();
root = removeMax(root);
return ret;
}
private Node removeMax(Node node){
if(node.right == null){
Node leftNode = node.left;
node.left = null;
size--;
return leftNode;
}
node.right = removeMax(node.right);
return node;
}删除结点比较复杂，分为四种情况，前三种情况很简单，最后一种情况稍微复杂一点:
- 如果是叶子结点，直接删除；
- 如果
node只有右孩子，和之前removeMin()的处理一样，删除之后，返回右子树的根节点； - 如果
node只有左孩子，和之前removeMax()的处理一样，删除之后，返回左子树的根节点； - 如果
node既有左孩子又有右孩子，就找到node的右子树最小的结点 (后继结点)successor结点，然后用这个结点来顶替node，具体过程和实现看图片和代码；
代码：
//remove any node
public void remove(E e){
root = remove(root,e);
}
private Node remove(Node node,E e){/**删除以node为根的二分搜索树中值为e的节点，返回删除节点后新的二叉搜索树的根*/
if(node == null) return null; // 树中没有这个结点
if(e.compareTo(node.e) < 0){
node.left = remove(node.left,e);
return node;
}else if(e.compareTo(node.e) > 0){
node.right = remove(node.right,e);
return node;
}else { //e == node.e ---> should remove
if(node.left == null){ // only have rightchild or leaf
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 = minimum(node.right); //找到右子树的最小结点
successor.right = removeMin(node.right); //将successor.right设置成 原先结点node的右子树移除 successor之后的树
successor.left = node.left; //
//remove node
node.left = node.right = null;
//size--; //这个不需要，因为在removeMin(node.right)中已经减了一次
return successor; //返回新树的根
}
}还有一个要注意的就是删除之后不需要size--，因为我们在node的右子树中删除那个最小的(successor)结点并顶替node的时候，在removeMin()中已经size- -了，所以不要再减去。
package DataStructure.Tree.BST;
public class BSTree<E extends Comparable<E>> {
private class Node{
public E e;
public Node left,right;
public Node(E e, Node left, Node right) {
this.e = e;
this.left = left;
this.right = right;
}
public Node(E e) {
this.e = e;
left = null;
right = null;
}
}
private Node root;
private int size;
public BSTree() {
root = null;
size = 0;
}
public int size(){
return size;
}
public boolean isEmpty(){
return size == 0;
}
/**
//easy understand version
public void add(E e){
if(root == null){
root = new Node(e);
size++;
}else {
add(root,e);
}
}
// 向以node为根的二分搜索树中插入元素，递归算法
private void add(Node node, E e) {
if(node.e.equals(e))return;
if(e.compareTo(node.e) < 0 && node.left == null){ //比node.e小
node.left = new Node(e);
size++;
return;
}else if(e.compareTo(node.e) > 0 && node.right == null){
node.right = new Node(e);
size++;
return;
}
if(e.compareTo(node.e) < 0)// e < node.e && node.left != null
add(node.left,e);
else //e > node.e && node.right != null
add(node.right,e);
}
*/
//add
public void add(E e){
root = add(root,e);
}
private Node add(Node node, E e) { /**向以node为根的二分搜索树中插入元素，返回插入新结点之后二分搜索树的根 */
if(node == null) {//在这里插入
size++;
return new Node(e);
}
if(e.compareTo(node.e) < 0){
node.left = add(node.left,e); //node.left是变化的
}else if(e.compareTo(node.e) > 0){
node.right = add(node.right,e);
}
return node;
}
//query
public boolean contains(E e){
return contains(root,e);
}
private boolean contains(Node node, E e) {
if (node == null) return false;
if (e.compareTo(node.e) == 0) {
return true;
} else if (e.compareTo(node.e) < 0) {
return contains(node.left, e);
} else {
return contains(node.right, e);
}
}
public E minimum(){
if(size == 0)
throw new IllegalArgumentException("BST is empty!");
return minimum(root).e;
}
private Node minimum(Node node) {
if(node.left == null)return node;
return minimum(node.left);
}
public E maximum(){
if(size == 0)
throw new IllegalArgumentException("BST is empty!");
return maximum(root).e;
}
private Node maximum(Node node){
if(node.right == null)return node;
return maximum(node.right);
}
// 删除二叉搜索树中最小值所在的结点,返回最小值
public E removeMin(){
E ret = minimum();
root = removeMin(root); //remove the min node and then connect the tree
return ret;
}
private Node removeMin(Node node){/**删除掉以node为根的二叉搜索树中的最小结点,返回删除节点后新的结点的二分搜索树的根 */
if(node.left == null){ //node is min
Node rightNode = node.right;
node.right = null; //remove from the tree
size--;
return rightNode; /** 返回删除节点后新的结点的二分搜索树的根 然后上一层就可以连接上*/
}
node.left = removeMin(node.left); /** 去删除左子树, 然后我要连上你删除之后返回的新的根*/
return node; /** 返回删除之后的根 ，上一层还要连接*/
}
public E removeMax(){
E ret = maximum();
root = removeMax(root);
return ret;
}
private Node removeMax(Node node){
if(node.right == null){
Node leftNode = node.left;
node.left = null;
size--;
return leftNode;
}
node.right = removeMax(node.right);
return node;
}
//remove any node
public void remove(E e){
root = remove(root,e);
}
private Node remove(Node node,E e){/**删除以node为根的二分搜索树中值为e的节点，返回删除节点后新的二叉搜索树的根*/
if(node == null) return null; // 树中没有这个结点
if(e.compareTo(node.e) < 0){
node.left = remove(node.left,e);
return node;
}else if(e.compareTo(node.e) > 0){
node.right = remove(node.right,e);
return node;
}else { //e == node.e ---> should remove
if(node.left == null){ // only have rightchild or leaf
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 = minimum(node.right); //找到右子树的最小结点
successor.right = removeMin(node.right); //将successor.right设置成 原先结点node的右子树移除 successor之后的树
successor.left = node.left; //
//remove node
node.left = node.right = null;
//size--; //这个不需要，因为在removeMin(node.right)中已经减了一次
return successor; //返回新树的根
}
}
public void printTree(){
printTree(root,0,"H",8);
}
public void printTree(Node head,int height,String to,int len){
if(head == null)return;
printTree(head.right,height + 1,"v",len);
String val = to + head.e + to; //两边指示的字符
int lenV = val.length();
int lenL = (len - lenV)/2; //左边的空格(分一半)
int lenR = len - lenV - lenL; // 右边的空格
System.out.println( getSpace(len * height) + getSpace(lenL) + val + getSpace(lenR));
printTree(head.left,height + 1,"^",len);
}
public static String getSpace(int len){
StringBuffer str = new StringBuffer();
for(int i = 0; i < len; i++) str.append(" ");
return str.toString();
}
public static void main(String[] args) {
Integer[] arr = {21,14,28,11,18,25,32,5,12,15,19,23,27,30,37};
// Arrays.sort(arr); //退化成链表
BSTree<Integer>bsTree = new BSTree<>();
for(int i = 0; i < arr.length; i++) bsTree.add(arr[i]);
bsTree.printTree();
System.out.println("--------------华丽分割线-------------");
System.out.println(bsTree.contains(27));
System.out.println(bsTree.contains(99));
System.out.println(bsTree.minimum());
System.out.println(bsTree.maximum());
System.out.println("--------------华丽分割线-------------");
// bsTree.removeMin();
// bsTree.removeMax();
// bsTree.printTree();
bsTree.remove(25);
bsTree.printTree();
}
}效果:
