二叉排序树:BST(BinarySort ( Search ) Tree),对于二叉排序树的任何一个非叶子节点,要求左子节点的值比当前节点的值小,右子节点的值比当前节点的值大。
我们先看一个需求,给一个数列(7,3,10,12,5,1,9),要求能够高效的完成对数据的查询和添加。
使用数组数组
未排序:
- 优点:直接在数组尾添加,速度快。
- 缺点:查找速度慢
数组排序,
- 优点:可以使用二分查找,查找速度快
- 缺点:为了保证数组有序,在添加新数据时,找到插入位置后,后面的数据需整体移动,速度慢。
使用链式存储-链表
不管链表是否有序,查找速度都慢,添加数据速度比数组快,不需要数据整体移动。
我们可以使用二叉排序树来完成。
我们先定义一个Node节点:
1 | class Node{ |
再写二叉排序树的类:
1 | class BinarySortTree{ |
下面我们完成添加元素的方法。
先在Node
类中添加 add
方法:
1 | //添加方法 |
然后在 BinarySortTree
类中完成添加方法:
1 | //添加节点的方法 |
下面我们写中序遍历的方法:
先在Node节点中添加中序遍历的方法:
1 | //中序遍历 |
然后在 BinarySortTree
类中完成遍历方法:
1 | //中序遍历 |
删除元素的方法有点小麻烦,没敲,还要找父节点什么的,有点小恶心,下面说一下方向。
若要删除p,可有下面三种情况:
- 若p为叶子节点
- p有且只有一个左孩子或者右孩子
- p有左右子树