二叉排序树的实现

2021-02-11 21:20

阅读：404

标签：使用 free 代码 turn 关键字 arch color insert 伪代码

二叉排序树的实现

1.1. 编写SearchBST(T, key)与InsertBST(T, key)的伪代码，并实现；

InsertBST(T, key){
if(T为空）
{创建一个新结点BSTNode；
T=key=k;
p->lchild=p->rchild=NULL;}
else if(k=T值){return 0;}
else if(T值>k){插入到左子树中}
else if(T值}
}

SearchBST(T, key){
if(T为空||T->key==k){
return T;}
if{T值>k){在左子树中递归查找}
else{在右子树中递归查找}

实现：

InsertBST(T, key){
if(T==NULL）
{T=new BSTNode;
T=key=k;
p->lchild=p->rchild=NULL;}
else if(k=T->key){return 0;}
else if(T->key>k){return InSertBST(p->lchild,k);}
else if(T->keyreturn InSertBST(p->rchild,k);}
}

SearchBST(T, key){
if(T==NULL||T->key==k){
return T;}
if{T->key>k)
{return SearchBST(T->lchild,k)；}
else{return SearchBST(T->rchild,k);}

2. 编写CreateBST(T)的伪代码实现从控制台输入创建BST树。最后使用代码实现。使用“50 30 80 20 40 90 10 25 35 85 23 88”创建BST，并中序输出该BST

CreateBST(T){
初始化T为空树；
关键字下标设为i=0；
while（in){调用插入函数；}
return T;
}

实现：

BSTNode* CreateBST(int A[],int n){
BSTree T=NULL;
int i=0；
while（i;}
return T;
}

3. 编写DeleteBST(T, key)的伪代码实现从T中删除关键字key。如果无法编写出来，请写出在BST中删除关键字key所需注意的事项

DeleteBST(T, key){
创建一个新结点*q；
if(T->rchild不为空){递归找被删结点的左子树的前驱节点}
else{
将关键字赋给T
将左子树的根节点放在被删结点位置上
q指针指向被删结点，释放其空间
}
}

注意事项：

在删除时必须先进行查找操作；删除结点时不能把以该结点为根的子树删除掉。

4. 选做：使用代码实现

void DeleteBST(BSTNode *p, BSTNode *&r){
BSTNode *q；
if(T->rchild!=NULL){
DeleteBST(p,r->rchild)}
else{
p->key=r->key
;q=r;
r=r->lchild;
free(q);}
}

二叉排序树的实现

标签：使用 free 代码 turn 关键字 arch color insert 伪代码

原文地址：https://www.cnblogs.com/1360175655z/p/12733997.html

上一篇：从零搭建一个SpringCloud项目之Sleuth+Zipkin(六)

下一篇：C#多线程(8)：线程完成数

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：二叉排序树的实现
文章链接：http://soscw.com/index.php/essay/54186.html

亲，登录后才可以留言！

二叉排序树的实现

评论

热门文章

推荐文章

最新文章

置顶文章