记录生活中的点点滴滴

0%

二叉排序树

二叉排序树: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有左右子树