二叉搜索树 (Binary Search Tree, BST) 又称二叉排序树或二叉查找树。 二叉搜索树的左子树均小于根节点，右子树均大于根节点。
// 节点定义 struct BSTNode { int key; BSTNode* lchild; BSTNode* rchild; BSTNode* parent; }先序遍历：访问根节点；遍历左子树；遍历右子树。 中序遍历：遍历左子树；访问根节点；遍历右子树。 (由于二叉搜索树具有 左子树<根节点<右子树 的性质，中序遍历二叉搜索树的结果是所有节点的升序序列。) 后序遍历：遍历左子树；遍历右子树；访问根节点。
遍历的时间复杂度：O(n)。（因为每个节点都要被访问一次。）
从根节点开始查找给定的key，若key<根节点，则继续查找左子树；若key>根节点，则继续查找右子树。
查找的时间复杂度：O(h)。（h为二叉搜索树的高度。） 可以发现当二叉搜索树近似平衡的时候，查找的时间复杂度为O(logn)；当二叉搜索树完全不平衡的时候，查找的时间复杂度为O(n)。
查找最小值，为二叉搜索树的最左端的节点；查找最大值，为二叉搜索树最右端的节点。
// 递归实现 BSTNode* searchRecursively(BSTNode* pNode, int key) { if (pNode == NULL || pNode->key == key) { return pNode; } if (key < pNode->key) { return searchRecursively(pNode->lchild, key); } else { return searchRecursively(pNode->rchild, key); } } // 迭代实现 BSTNode* searchIteratively(BSTNode* pNode, int key) { while(pNode != NULL && pNode->key != key){ if (key < pNode->key){ pNode = pNode-> lchild; } else { pNode = pNode->rchild; } } return pNode; }二叉树的最左节点。
BSTNode* searchMinimum(BSTNode* x) { while(x != NULL && x->lchild != NULL){ x = x->lchild; } return x; }二叉树的最右节点。
BSTNode* searchMaximum(BSTNode* x) { while(x != NULL && x->rchild != NULL){ x = x->rchild; } return x; }给定一棵二叉搜索树的结点，查找二叉树中序遍历的后继（即排序序列中该结点的后一个元素）。由于二叉搜索树的性质，我们可以通过没有任何关键字的比较来确定后继。
若该结点是最大关键字，则其后继为NULL；否则， 若该节点的右子树非空，其后继为该结点的右子树的最左结点。 若右子树为空， 若该结点为其父节点的左孩子，则该结点的后继为其父节点； 若该结点为其父节点的右孩子，则该结点的后继为其祖先结点中左孩子为该节点的祖先结点的结点。 BSTNode* searchSuccessor(BSTNode* x) { // 查找结点x的后继 // 若右子树非空，则后继为其右子树的最左结点（即右子树的最小关键字） if (x->rchild != NULL) return searchMinimum(x->rchild); BSTNode* y = x->parent; // 若该结点为其父节点的左孩子，则不进入循环，直接返回其父节点 while(y != NULL && y->rchild == x){ // 直到找到一个祖先结点的左孩子为其祖先结点，停止循环 // 若找到根节点仍找不到这样的结点，根节点的父节点为NULL，此时退出循环，返回NULL，即此时该结点为二叉搜索树中的最大关键字，无后继结点。 x = y; // 记住祖先结点 y = y->parent; // 继续查找 } return y;查找前驱与查找后继的情况是对称的。
若该结点是二叉搜索树中的最小关键字，则前驱为NULL；否则， 若该结点存在左子树，则其前驱为左子树中的最右结点（searchMaximum）； 若该结点的左子树为空， 若该结点为其父节点的右孩子，则其前驱为其父节点； 若该结点为其父节点的左孩子，则其前驱结点为其祖先结点中右孩子仍为其祖先结点的结点。 BSTNode* searchPredecessor(BSTNode* x) { if (x==NULL) return x; if (x->lchild != NULL) return searchMaximum(x->lchild); BSTNode* y = x->parent; while(y != NULL && x == y->lchild){ x = y; y = y->parent; } return y; }插入过程首先从根开始遍历，在遍历过程中我们要记录双亲，然后通过关键字的比较，决定向左向右移动，直到找到一个NULL，就是要插入的位置。 注意：插入结点后，新结点总是作为一个新的叶子结点而存在。
插入的时间复杂度：O(logn)
void insert(BSTNode *& T, int key) { // 注意这里的函数参数使用了指针的引用，意味着在函数内部改变其值会导致函数外其值的改变，可以用于当插入的结点为根结点时（例如树空时），根节点需要改变。 BSTNode* pNode = (BSTNode*)malloc(sizeof(BSTNode)); pNode->key = key; pNode->lchild = NULL; pNode->rchild = NULL; pNode->parent = NULL; BSTNode* x = T; BSTNode* y = NULL; while(x != NULL){ y = x; // y用于记住父节点 if (key < x->key) x = x->lchild; else x = x->rchild; } pNode->parent = y; if (y == NULL) T = pNode; // 插入的结点为根节点 else if (key < y->key) y->lchild = pNode; else y->rchild = pNode; }需要保证删除后不改变二叉搜素树的性质。
若待删除结点z没有孩子结点，只需要简单删除，将其父节点的孩子结点置为NULL以替换结点z;若z只有一个孩子结点，只需以这个孩子结点替换结点z；若z有两个孩子，寻找z的后继y，令y替换z，z原来的左子树称为y新的左子树，z原来的右子树称为y新的右子树（注意后继y一定没有左孩子）： 若z的后继为z的右孩子，则用y替换z，y的左子树为原来z的左子树，y的右子树保持不变； 若z的后继y不是z的右孩子，先用y的右孩子替换y，然后再用y替换z。删除的时间复杂度为：O(h)。h为二叉搜素树的高度。
// 用一棵以v为根的子树替换一棵以u为根的子树，u的父节点变为v的父节点，u的父节点的孩子结点变为v void transplant(BSTNode* &T, BSNode* u, BSTNode* v) { // 需要修改u的父节点的孩子以及v的父节点 if (u->parent == NULL) T = v; else if (u == u->parent->lchild) u->parent->lchild = v; else u->parent->rchild = v; if (v != NULL) v->parent = u->parent; } // 将结点z从以T为根节点的二叉搜索树中删除 BSTNode* delete(BSTNode* &T, BSTNode* z) { BSTNode* y = NULL; // 若存在0个或1个孩子结点，用其孩子结点替换 if (z->lchild == NULL) transplant(T, z, z->lchild); else if (z->rchild == NULL) transplant(T, z, z->lchild); else { // 存在两个孩子，则用其后继替换 y = searchMinimum(z->rchild); if (y->parent != z) { transplant(T, y, y->rchild); y->rchild = z->rchild; y->rchild->parent = y; } transplant(T, z, y); y->lchild = z->lchild; y->lchild->parent = y; } return z; }参考资料： [1] [深入学习理解二叉搜索树（附详细讲解与实例分析）] (https://blog.csdn.net/qq_21396469/article/details/78419609)
