本文主要是介绍二叉排序树(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;
}
知乎：Solo | 微博@从流域到海域
这篇关于二叉排序树(BSTree)关于查找算法结合的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
