二叉搜索树(BST, Binary Searching Tree):一棵二叉树,可以为空;如果不为空,满足以下性质:
- 非空左子树的所有键值小于其根结点的键值;
- 非空右子树的所有键值大于其根结点的键值;
- 左、右子树都是二叉搜索树;
- 中序遍历一定是从小到大的顺序,因为中序是左→根→右。
- 操作集:
Insert
:注意树要初始化为NULL
!否则容易出现段错误
Find
操作步骤:- 从根结点开始,如果为空返回
NULL
,否则进入下一步; - 如果等于当前结点,就返回当前结点;否则如果比当前结点的值大,就在右子树中查找;否则就在左子树中查找。
Delete
:有以下几种情况:- 如果删除的结点是叶子结点,那么直接删除就可以;
- 如果删除的是只有左子树或者只有右子树的结点,那么只需要用其左子树或者右子树代替就可以;
- 如果删除的是既有左子树又有右子树的结点,那么只需要在其左子树中找到最大的结点(或右子树中最小的结点),用其代替要删除的结点,并将其也删除就可以了;
- 完整代码: