1、二叉排序树

1、二叉排序树

1、需求

给你一个数列(7,3,10,12,5,1,9)，要求能够高效的完成对数据的查询和添加

2、解决方案分析

使用数组
- 数组未排序，优点：直接在数组尾添加，速度快。缺点：查找速度慢
- 数组排序，优点：可以使用二分查找，查找速度快，缺点：为了保证数组有序，在添加新数据时，找到插入位置后，后面的数据需整体移动，速度慢。
使用链式存储-链表
- 不管链表是否有序，查找速度都比较慢，但是插入数据比数组快，不需要整体移动

使用二叉排序树

3、二叉排序树介绍

二叉排序树：BST:(Binary Sort(Search)Tree),对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。
特别说明：如果有相同的值，可以将该节点放在左子节点或右子节点
比如针对前面的数据(7,3,10,12,5,1,9)，对应的二叉排序树为：

4、二叉排序树创建和遍历

一个数组创建成对应的二义排序树，并使用中序遍历二叉排序树，比如：数组为array(7,3,10,12,5,1,9),创
建成对应的二叉排序树为：

1、代码实现

```java /**

@author djy
@createTime 2022/5/22 上午10:12

@description */ public class BinarySortTree> {

private Node root;

/**

添加节点
@param node */ public void add(Node node){ if (root == null){
```
 root = node;
```
}else{
```
 root.add(node);
```
} }

/**

打印 */ public void infixOrder(){ if (root != null){
```
 root.infixOrder();
```
} }

public static class Node {

T value;
Node left;
Node right;

public Node(T value) {
    this.value = value;
}

public T getValue() {
    return value;
}

public void setLeft(Node left) {
    this.left = left;
}

public void setRight(Node right) {
    this.right = right;
}

public Node getLeft() {
    return left;
}

public Node getRight() {
    return right;
}

@Override
public String toString() {
    return "Node{" +
            "value=" + value +
            '}';
}

/**
 * 添加节点
 * 相同节点添加到右边
 * @param node
 */
public void add(Node node){
    if (node == null){
        return;
    }

    if (this.getValue().compareTo(node.getValue()) > 0){
        if (this.left == null){
            this.left = node;
        }else{
            this.left.add(node);
        }
    }else{
        if (this.right == null){
            this.right = node;
        }else{
            this.right.add(node);
        }
    }
}

/**
 * 中序遍历
 */
public void infixOrder(){
    if (left != null){
        left.infixOrder();
    }
    System.out.println(this.value);
    if (right != null){
        right.infixOrder();
    }
}

}

} ```

5、二叉排序树的删除

1、删除有三种情况

删除叶子节点
- 从父节点直接删除当前子节点
删除只有一颗子树的节点
- 从父节点直接删除当前节点，并且把它的子节点作为新的叶子节点
删除有两颗子树的节点
- 从父节点删除当前节点
  - 从当前节点的右边节点中找到最小的叶子节点充当当前被删除节点的新节点
  - 从当前节点的左边节点中找到最大的叶子节点充当当前被删除节点的新节点

Java服务端技术

7、算法与数据结构（树-二叉排序树）