1. 算法简介文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25221.html
二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。该树属于一种输入数据就默认产生一种顺序的数据结构，这不像本章前面的内容所描述的静态的在某一个数据段内进行查找，动态查找是一种输入时就会自动对其进行排序的数据结构，前文学过的STL中的set集合其底层就是一个类似的树形结构红黑树。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25221.html
2. 定义文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25221.html
二叉排序树有以下性值：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25221.html
a) 若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25221.html
b) 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25221.html
c) 左、右子树也分别为二叉排序树；文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25221.html
即对于每一个根结点，其左孩子永远小于根，右孩子永远大于根。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25221.html
3. 查找文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25221.html
考虑如果树是空的，则查找结束，无匹配。如果被查找的值和根结点的值相等，查找成功。否则就在子树中继续查找。如果被查找的值小于根结点的值就选择左子树，大于根结点的值就选择右子树。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25221.html
参考代码如下：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25221.html
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */ /* 二叉树的二叉链表结点结构定义 */typedef struct BiTNode /* 结点结构 */{ int data; /* 结点数据 */ struct BiTNode *lchild, *rchild; /* 左右孩子指针 */} BiTNode, *BiTree; /* 递归查找二叉排序树T中是否存在key, *//* 指针f指向T的双亲，其初始调用值为NULL *//* 若查找成功，则指针p指向该数据元素结点，并返回TRUE *//* 否则指针p指向查找路径上访问的最后一个结点并返回FALSE */Status SearchBST(BiTree t, int key, BiTree f, BiTree *p) { if (!t) /* 查找不成功 */ { *p = f; return FALSE; } else if (key == t->data) /* 查找成功 */ { *p = t; return TRUE; } else if (key < t->data) return SearchBST(t->lchild, key, t, p); /* 在左子树中继续查找 */ else return SearchBST(t->rchild, key, t, p); /* 在右子树中继续查找 */} |
4.插入方法及实现文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25221.html
二叉排序的插入是建立在二叉排序的查找之上的，插入一个结点，就是通过查找发现该结点合适插入位置，把结点直接放进去。 其实在2.2节中一步步构造二叉排序树的过程中就是结点插入过程，并考虑查找的关键字已经有在树中，则指向该数据结点，若查找的关键字没有在树中，则指向查找路径上最后一个结点。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25221.html
参考代码文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25221.html
struct BiTree { int data; BiTree *lchild; BiTree *rchild;}; //在二叉排序树中插入查找关键字keyBiTree* InsertBST(BiTree *t,int key){ if (t == NULL) { t = new BiTree(); t->lchild = t->rchild = NULL; t->data = key; return t; } if (key < t->data) t->lchild = InsertBST(t->lchild, key); else t->rchild = InsertBST(t->rchild, key); return t;} //n个数据在数组d中，tree为二叉排序树根BiTree* CreateBiTree(BiTree *tree, int d[], int n){ for (int i = 0; i < n; i++) tree = InsertBST(tree, d[i]);} |
5.删除方法与实现文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25221.html
二叉树的删除可不再像二叉树的插入那么容易了，以为删除某个结点以后，会影响到树的其它部分的结构。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25221.html
删除的时候需要考虑以下几种情况：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25221.html
a)删除结点为叶子结点；文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25221.html
b)删除的结点只有左子树；文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25221.html
c)删除的结点只有右子树文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25221.html
d)删除的结点既有左子树又有右子树。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25221.html
参考代码如下：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25221.html
/* 若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素结点, *//* 并返回TRUE；否则返回FALSE。 */Status DeleteBST(BiTree *T,int key){ if(!*T) /* 不存在关键字等于key的数据元素 */ return FALSE; else { if (key==(*T)->data) /* 找到关键字等于key的数据元素 */ return Delete(T); else if (key<(*T)->data) return DeleteBST(&(*T)->lchild,key); else return DeleteBST(&(*T)->rchild,key); }}/* 从二叉排序树中删除结点p，并重接它的左或右子树。 */Status Delete(BiTree *p){ BiTree q,s; if((*p)->rchild==NULL) /* 右子树空则只需重接它的左子树（待删结点是叶子也走此分支) */ { q=*p; *p=(*p)->lchild; free(q); } else if((*p)->lchild==NULL) /* 只需重接它的右子树 */ { q=*p; *p=(*p)->rchild; free(q); } else /* 左右子树均不空 */ { q=*p; s=(*p)->lchild; while(s->rchild) /* 转左，然后向右到尽头（找待删结点的前驱） */ { q=s; s=s->rchild; } (*p)->data=s->data; /* s指向被删结点的直接前驱（将被删结点前驱的值取代被删结点的值） */ if(q!=*p) q->rchild=s->lchild; /* 重接q的右子树 */ else q->lchild=s->lchild; /* 重接q的左子树 */ free(s); } return TRUE;} |