二叉排序树(BSTree)关于查找算法结合

本文主要是介绍二叉排序树(BSTree)关于查找算法结合，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

/*基于树的顺序查找法*/
/*二叉排序树的存储结构*/
typedef struct node {KeyType key;                      /*关键字的值*/struct node *lchild, *rchild;     /*左右指针*/
} NSTNode, *BSTree;
/*二叉排序树插入递归算法*/
void InsertBST(BSTree *bst, KeyType key) {BiTree s;if(*bst == NULL) {s = (BSTree)malloc(sizeof(BSTNode));s->key = key;s->lchild = NULL; s->rchild = NULL;*bst = s;}else if(key < (*bst)->key) {InsertBST(&((*bst)->lchild), key);}else if(key > (*bst)->rchild, key) {InsertBST(&((*bst)->rchild), key);}
/*创建二叉排序树*/
void CreateBST(BSTree *bst) {KeyType key;*bst = NULL;scanf("%d", &key);while(key != ENDKEY) {      /*ENDKEY为自定义常量*/InsertBST(bst, key);scanf("%d", &key);}
}
/*二叉排序树查找的递归算法*/
BSTree SearchBST(BSTree bst, KeyType key) {if(!bst) return NULL;else if(bst->key = key) return bst;else if(bst->key > key) return SearchBST(bst->lchild, key);else return SearchBST(bst->rchild,key);
}
/*二叉排序树查找的非递归算法*/
BSTree SearchBST(BSTree bst, KeyType key) {BSTree q;q = bst;while(q) {if(q->key == key) {return q;}if(q->key > key) {q = q->lchild;}else q = q->rchild;}return NULL;
}
/*二叉排序树的删除*/
BSTree* DelBST(BSTree t, KeyType k) {BSTNode *p,*f,*s,*q;p = t; f =NULL;while(p) {if(p->key == key) break;f = p;     /*f指向p结点的双亲结点*/if(p->key > key) p = p->lchild;else p = p->rchild;}    /*以上步骤找到p在二叉排序树中的位置*/if(p == NULL) return t;    /*若找不到，返回原来的二叉排序树*/if(p->lchild == NULL) {    /*p无左子树*/if(f = NULL) {         /*如果根结点就是要删除的结点*/t = p->rchild;     /*t右子树置为根*/}else if(f->lchild == p) {    /*如果p是f的左孩子*/f->lchild = p->rchild;   /*将p的右子树连在f的左链上*/}else {     /*如果p是f的右孩子*/f->rchild = p->rchild;  /*将p的右子树连在f的右链上*/}free(p);}else {     /*p有左子树*/q = p; s = p->lchild;while(s->rchild) {q = s; s = s->rchild;     /*在p的左子树中找最右下结点*/}if(q == p) {                  /*如果p的左子树没有右子树*/q->lchild = s->lchild;    /*将s的左子树连到q(此时即为p)上*/}else {                        /*如果p的左子树有右子树 此时s为最右下结点*/q->rchild = s->lchild;}p->key = s->key;             /*将s的值赋给p*/free(s);}return t;
}