1、基本概念
- 二叉查找树是为了实现快速查找而生的
- 左子树结点值 < 根结点值 < 右子树节点值
- 默认不允许两个结点的关键字相同
2、查找操作
- 先取根结点,如果它等于要查找的数据,那就返回;
- 如果要查找的数据比根结点的值小,那就在左子树中递归查找;
- 如果要查找的数据比根结点的值大,那就在右子树中递归查找
2.1 查找成功ASL
查找成功的前提:只需考虑查找树中已有的结点即可。
方法:将所有查找成功的情况都列举出来,然后比较次数求和再取平均。

- 找40:比较一次
- 找45:比较两次
- 找10:比较两次
- 找15:比较三次
所以:
ASLsucc = (1+2+2+3)/4 = 2
2.2 查找失败ASL
找到空子树,还没找到结点,那么结点一定不存在
空结点算不算一次比较?比较是跟结点比较,但是空指针域是属于最后一个比较节点上的,所以空结点不算一次比较
- 第一种 40→ 10 → 左空子树,2次
- 第二种 40 → 10 → 15 → 左空子树,3次
- 第三种 40 → 10 → 15 → 右空子树,3次
- 第四种 40 → 45 → 左空子树,2次
- 第五种 40 → 45 → 右空子树,2次
所以:
ASLfail = (2+3+3+2+2)/5 = 12/5
2.4 递归查找
// 递归搜索,空间复杂度为O(h) BSTNode* searchRecBST(BSTree T, ElemType key) { if (key == T->data) return T; if (key < T->data) T = searchRecBST(T->lchild, key); else T = searchRecBST(T->rchild, key); return T; }
2.5 非递归查找
// 非递归查找,空间复杂度为O(1) BSTNode* searchBST(BSTree T, ElemType key) { // 若树空或等于根结点,则循环结束 while (T != NULL && key != T->data) { if (key < T->data) T = T->lchild; else T = T->rchild; } return T; }
3、插入操作
- 新插入的数据一般都是在叶子结点
- 只需要从根结点开始,依次比较要插入的数据和结点的大小关系;
- 如果要插入的数据比结点的数据大,并且结点的右子树为空,就将新数据插入到右节点的位置,如果不为空,就再递归遍历右子树,查找插入位置;
- 同理,插入左子树
// 插入数据 bool insertBST(BSTree& T, ElemType key) { if (T == NULL) { BSTNode* pNode = (BSTNode*)malloc(sizeof(BSTNode)); pNode->lchild = NULL; pNode->rchild = NULL; pNode->data = key; T = pNode; return true; } else if (key == T->data) return false; else if (key < T->data) return insertBST(T->lchild, key); else return insertBST(T->rchild, key); }
4、创建二叉排序树
// 指向二叉排序树根结点的指针T为空 // 不断往这颗T指向的二叉排序树中插入结点 BSTree createBST(ElemType keyList[], int keyListLength) { if (keyListLength <= 0) return NULL; BSTree T = NULL; for (int i = 0; i < keyListLength; i++) { insertBST(T, keyList[i]); } return T; }
5、删除操作
主要思想:针对删除结点的子树个数不同,将删除结点存在两个子树,转化为存在一个子树的方式删除。
5.1 方法一
- 如果删除的结点没有子节点,直接将父节点中指向该结点的指针置为NULL;
- 如果删除的结点只有一个结点,只需要将父结点中,指向删除结点的指针,指向要删除结点的子结点即可;
- 如果删除的结点有两个子结点,需要找到这个结点的右子树中的最小结点,把它替换到要删除的结点上,然后再删除这个最小结点,因为最小结点肯定没有左子节点,用上面两条规则删除。
5.2 方法二
- 如果删除的结点没有子节点,直接将父节点中指向该结点的指针置为NULL;
- 如果删除的结点只有一个结点,只需要将父结点中,指向删除结点的指针,指向要删除结点的子结点即可;
- 如果删除的结点有两个子结点,找到删除结点的左子树中的最大者,将右子树的根结点挂到左子树中最大者的右孩子上,之后使用删除一个结点的方法删除。
代码实现主要分两步:
5.2.1 删除值的查找
使用递归方法找到要删除的结点
// 删除递归操作 void deleteNodeBST(BSTree& T, ElemType x) { if (T == NULL) return; if (x == T->data) { deleteOper(T); } else if (x < T->data) deleteNodeBST(T->lchild, x); else deleteNodeBST(T->rchild, x); }
5.2.2 删除这个结点
删除结点分四种情况:
- 只有一个结点:直接删除
- 右孩子存在,左孩子不存在:删除结点,将指针指向右孩子
- 左孩子存在,右孩子不存在:删除结点,将指针指向左孩子
- 左右孩子都存在:找到删除结点左子树中的最大值结点(右侧寻找),将删除结点的右子树挂在左子树的最大节点的右孩子上。
// 结点删除操作 void deleteOper(BSTree& T) { // 1、只有这一个结点,直接置为空 if (T->lchild == NULL && T->rchild == NULL) { free(T); T = NULL; } // 2、右孩子存在,左孩子不存在 else if (T->lchild == NULL) { BSTNode* pNode = T; T = T->rchild; free(pNode); } // 3、左孩子存在,右孩子不存在 else if (T->rchild == NULL) { BSTNode* pNode = T; T = T->lchild; free(pNode); } // 4、左右孩子都存在 else { // 寻找左子树的最大值 BSTNode* pLeftMax = T->lchild; while (pLeftMax->rchild != NULL) { pLeftMax = pLeftMax->rchild; } // 将右子树挂在左子树的最大值 pLeftMax->rchild = T->rchild; // 释放删除结点的内存 BSTNode* pNode = T; T = T->lchild; free(pNode); } }
6、Sample
6.1 将树分成两颗
问题
将一棵二叉排序树t分解成两棵二叉排序树t1与t2,使得t1中的所有结点关键字的值都小于key,t2中所有关键字的值都大于key。
算法思想
- 如果key等于根结点(子树根节点),那么将左子树和右子树分别插入到T1和T中;
- 如果key大于根结点,那么将根和左子树插入T1中,然后继续分解右子树;
- 如果key小于根结点,那么将根和右子树插入T2中,继续对左子树进行划分;
- 重复上述步骤,直到树中不存在为划分结点;

删除结点(分解)一般使用先序遍历。左子树和右子树的情况进行下一部分的操作,必须结点。
代码
// 将一个结点插入排序树中 void insertNodeBSTree(BSTree& T, BSTNode* rNode) { if (T == NULL) T = rNode; else if (rNode->data < T->data) insertNodeBSTree(T->lchild, rNode); else insertNodeBSTree(T->rchild, rNode); }
// 先序遍历划分树 void preOrderTraversing(BSTree T, ElemType key, BSTree& T1, BSTree& T2) { if (T == NULL) return; // 1、key小于根,说明右子树和根都大于key, // 将右子树和根插入T2,左子树继续分解 if (key < T->data) { preOrderTraversing(T->lchild, key, T1, T2); T->lchild = NULL; // 注意:左子树分完了,不存在了 insertNodeBSTree(T2, T); } // 2、key等于根,左子树插入T1,右子树插入T2 else if (key == T->data) { insertNodeBSTree(T1, T->lchild); insertNodeBSTree(T2, T->rchild); free(T); T = NULL; } // 3、key大于根,说明左子树和根都小于key, // 将左子树和根插入T1,右子树继续分解 else { preOrderTraversing(T->rchild, key, T1, T2); T->rchild = NULL; insertNodeBSTree(T1, T); } }
void spiltBST(BSTree T, ElemType key, BSTree& T1, BSTree& T2) { T1 = NULL; T2 = NULL; preOrderTraversing(T, key, T1, T2); }
6.2 删除小于x的结点
问题
已知二叉排序树中每一个结点值为整型,采用二叉链表存储编写算法,删除二叉排序树中所有结点值小于x的结点。
分析
最关键要知道根结点,然后左右子树的取值范围!然后根据这个范围,要不要对子树进行递归操作。先序遍历,先知道根结点才能知道左右子树的范围。
算法思想
- 使用先序遍历搜索小于x的结点并将其删除。
- 如果当前访问结点大于x,那么使用先序遍历搜索并删除其左子树中小于x的结点,保留该节点与其右子树;
- 如果当前结点小于x,那么先序遍历搜索并删除其右子树中小于x的结点后,再直接删除左子树中所有结点;
- 如果当前访问结点等于x,那么直接删除该结点及其左子树,保留右子树。
代码
// 删除一颗二叉树 void deleteTree(BSTree& T) { if (T == NULL) return; deleteTree(T->lchild); deleteTree(T->rchild); T->lchild = NULL; T->rchild = NULL; free(T); T = NULL; }
// 先序遍历删除小于x的结点 void preOrderDeleteLessNode(BSTree &T, ElemType x) { if (T == NULL) return; // 等于根结点,删除左子树 if (T->data == x) { // 删除左孩子,指控左指针 deleteTree(T->lchild); T->lchild = NULL; } // 根结点小于x,删除左子树,右子树可能存在小于x的数 else if (T->data < x) { // 右子树递归删除小于x的结点 preOrderDeleteLessNode(T->rchild, x); // 删除左子树 deleteTree(T->lchild); T->lchild = NULL; // 删除根结点 BSTNode* pNode = T; T = T->rchild; free(pNode); pNode = NULL; } // 根结点大于x,左子树可能存在小于x的数,右子树全部大于x else if (T->data > x) { // 左子树递归删除小于x的结点 preOrderDeleteLessNode(T->lchild, x); } }
6.3 查找二叉排序树中小于key的关键字
问题
查找二叉排序树中小于key的关键字
算法思想
方法一:在中序遍历输出哪儿判断是否要输出
方法二:中序遍历的时候,如果访问的结点大于等于key,后面的结点都不再访问。
如果说只要打印小于key的结点,那么中序遍历时访问根结点,根结点大于等于key,右子树一定时大于key,那么右子树的中序遍历将不再执行。
- 中序遍历左、中、右,将获得升序序列
- 中序遍历右、中、左,将获得降序序列
注意
可用于:topK,最大的几个,最小的几个,大于x值得结点 ...
// 查找二叉排序树中小于key的关键字 void inOrderPrintLessNode(BSTree T, ElemType x) { if (T == NULL) return; inOrderPrintLessNode(T->lchild, x); if (T->data >= x) // 这个地方判断打印的结点小于key ? 是的, 就打印 return; printf("%d ", T->data); //这个函数执行的时候,一定打印大于key的关键字 inOrderPrintLessNode(T->rchild, x); }
6.4 寻找比value大的最小值
问题
存在一个二叉排序树,给定一个value值,若查找value值,就返回比value值大的所有值中最小的值。若value最大就返回空。
分析
找一批值,中序序列获得大于Value的值,从中选取最小的值;使用变量保存上一次打印的值。
算法思想
- 使用中序序列获得降序序列;
- 先访问右子树,再访问(打印)根结点,如果根结点小于等于key,那么上一次打印的结点即为比key大的结点中的最小值;
- 反之,继续遍历左子树,直到遇见小于等于key的结点或结点访问完时停止搜索。
利用中序遍历序列获得一个序列,利用根结点的判断,截取这个序列中的一部分序列。
代码
// 寻找比value大的最小值 // preNode :保存上一次访问的结点 void inOrderCloserValue(BSTree T, ElemType value, BSTNode*& preNode) { if (T == NULL) return; inOrderCloserValue(T->rchild, value, preNode); if (T->data > value) { preNode = T; // 保存当前结点,然后从左子树中查找大于value的结点 // /如果有可能存在大于value的结点在左子树中,所以递归调用进行查找 inOrderCloserValue(T->lchild, value, preNode); } }