本文共 3185 字，大约阅读时间需要 10 分钟。
二叉排序树(Binary Sort Tree),又称为二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树:
如果它的左子树不空，则左子树上所有结点的值均小于它的根结点的值 如果它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。
#include#include #define TRUE 1#define FALSE 0#define OVERFLOW -2typedef int TElemType;typedef struct BiTNode{ TElemType data; struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;/****************二叉排序树的查找*******************参数说明： T 二叉排序树 key 待查找的关键字 f 指向T的双亲 p 查找成功则指向该关键字的结点，返回TRUE， 失败则指向查找路径的最后一个结点，返回FALSE****************************************************/int SearchBST(BiTree T, TElemType 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) {//关键字小于当前结点的值，则查找其左子树 SearchBST(T->lchild,key, T, p); } else {//关键字大于当前结点的值，则查找其右子树 SearchBST(T->rchild,key, T, p); }}/****************二叉排序树的插入*******************二叉排序树的中序遍历是一个有序序列参数说明： T 二叉排序树 key 待插入的关键字 插入成功返回TRUE，失败返回FALSE****************************************************/int InsertBST(BiTree &T, TElemType key){ BiTree p,s; if (!SearchBST(T,key,NULL,p)) {//如果该二叉排序树没有该关键字则插入 s = (BiTree)malloc(sizeof(BiTNode)); if (!s) { exit(OVERFLOW); } s->data = key; s->lchild = NULL; s->rchild = NULL; //插入新的结点 if (!p) {//如果当前是一棵空树 T = s; //插入s为新的根结点 } else if (key < p->data) {//关键字小则为其左子树 p->lchild = s; } else {//关键字大则为其右子树 p->rchild = s; } return TRUE; } else {//插入失败，即二叉树包含有该关键字的结点 return FALSE; }}/****************二叉排序树的删除*******************函数int Delete(BiTree &p);p是待删除的结点，并整理其左右子树函数int DeleteBST(BiTree &T, int key)删除值为key的结点****************************************************//*int 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的右子树 q->rchild = s->lchild ; } else {//重接q的左子树 q->rchild = s->lchild ; } free(s); } return TRUE;}*/int 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->rchild; while (s->lchild) {//转左，然后向右到尽头(找待删结点的前驱) q = s; s = s->lchild; } p->data = s->data ; //s指向被删结点的直接前驱 if (q != p) {//重接q的左子树,不相等，则说明q->lchild = s; q->lchild = s->rchild ; } else {//重接q的右子树，相等，则说明s = q->rchild,即只有一个结点的时候; q->rchild = s->rchild ; } free(s); } return TRUE;}int DeleteBST(BiTree &T, int key){ if (!T) { return FALSE; } else { if (key == T->data) { return Delete(T); } else if (key < T->data) { return DeleteBST(T->lchild, key); } else { return DeleteBST(T->rchild, key); } }}void InOrderTraverse(BiTree T){ if (T == NULL) { return; } InOrderTraverse(T->lchild);//访问左子树 printf("%d ",T->data);//访问根结点 InOrderTraverse(T->rchild);//访问右子树}int main(){ int i,n; int a[] = {62,88,58,47,35,73,51,99,37,93,29,37,36,49,56,48,50}; BiTree T = NULL,p; for (i=0; i
转载地址：http://pqmbn.baihongyu.com/