记录生活中的点点滴滴

0%

二叉排序树

发表于 Valine：

二叉排序树：BST（BinarySort ( Search ) Tree），对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。

我们先看一个需求，给一个数列（7,3,10,12,5,1,9），要求能够高效的完成对数据的查询和添加。

  • 使用数组数组

    未排序：

    • 优点：直接在数组尾添加，速度快。
    • 缺点：查找速度慢

    数组排序，

    • 优点：可以使用二分查找，查找速度快
    • 缺点：为了保证数组有序，在添加新数据时，找到插入位置后，后面的数据需整体移动，速度慢。

  • 使用链式存储-链表

    不管链表是否有序，查找速度都慢，添加数据速度比数组快，不需要数据整体移动。

我们可以使用二叉排序树来完成。

我们先定义一个Node节点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Node{
    int data;
    Node left;
    Node right;
    public Node(int data){
        this.data = data;
    }
    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                '}';
    }
}

再写二叉排序树的类：

1
2
3
4
class BinarySortTree{
    //根节点
    Node root;
}

下面我们完成添加元素的方法。

先在Node类中添加 add 方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//添加方法
public void add(Node node){
    if(node==null)
        return;
    if(node.data < this.data){//向左添加
        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);
        }
    }
}

然后在 BinarySortTree 类中完成添加方法：

1
2
3
4
5
6
7
//添加节点的方法
public void add(Node node){
    if(root==null)
        root = node;
    else
        root.add(node);
}

下面我们写中序遍历的方法：

先在Node节点中添加中序遍历的方法：

1
2
3
4
5
6
7
8
//中序遍历
public void inorder_traversal(){
    if(this.left!=null)
        this.left.inorder_traversal();
    System.out.print(this+"-->");
    if(this.right!=null)
        this.right.inorder_traversal();
}

然后在 BinarySortTree 类中完成遍历方法：

1
2
3
4
5
6
7
8
9
10
11
//中序遍历
public void inorder_traversal(){
    if(root==null)
    {
        System.out.println("二叉排序树为空，遍历失败");
        return;
    } else{
        root.inorder_traversal();
        System.out.println();
    }
}

删除元素的方法有点小麻烦，没敲，还要找父节点什么的，有点小恶心，下面说一下方向。

若要删除p，可有下面三种情况：

  1. 若p为叶子节点
  2. p有且只有一个左孩子或者右孩子
  3. p有左右子树