发布时间 : 星期日 文章二叉排序树的建立与删除更新完毕开始阅读3a4d5ae7c1c708a1284a445e
周国庆 《二叉排序树的建立与删除》 第4页 共19页
3 程序设计及算法流程
3.1程序设计的算法流程
对于二叉排序树的设计主要分为四个大块，分别是二叉排序树的建立、查找、插入和删除任意节点。当然除了这几个主要要的部分外，还需要将二叉排序树一般用二叉链表来存储，并对其节点进行结构体定义，以及一些显示函数来显示操作结果。最后就是主程序的编写，在主程序中将会调用以上各种函数，从而实现题目的要求。
3.2程序运行流程图
在程序开始执行后，会显示选择操作列表，操作为0：退出程序、1：创建二叉排序树、2：节点的查找 、3：节点的插入、4：节点的删除。首先判断输入的选择操作号是否在区间[0,4]内，若不在，重新输入选择操作号。若在该区间内，则根据它的值为0、1、2、3、4进行相应的操作，具体流程如图3.1。
图3.1 程序运行流程图
周国庆 《二叉排序树的建立与删除》 第5页 共19页
3.3函数设计及注释
(1)二叉排序树一般用二叉链表来存储，其节点的结构体定义如下： typedef struct bitnode {
int data; //定义数据域 struct bitnode *lchild; //定义左孩子指针 struct bitnode *rchild; //定义右孩子指针 }bitnode,*bitree; (2)建立二叉排序树
void createbst(bitree *root) //二叉排序树的建立 {
int i,data,cnt;
*root=NULL; //置空树
printf(\请输入数据个数: \ //设置输入数据个数 scanf(\ printf(\请输入数据: \
for(i=0;i （3）二叉排序树的查找，实际就是遍历该二叉排序树，并在此过程中判断要查找的数据元素是否存在。 int searchbst(bitree root,int data) //在二叉排序树的根root中查找关键字等于data的数据元素 { bitree p; //定义指针p p=root; //使指针p指向根root while(p){ if(p->data==data) //data等于当前节点的关键字，返回当前节点的关键字 return p->data; if(p->data>data) //data小于当前节点的关键字，则查找左子树 p=p->lchild; else p=p->rchild; //data大于当前节点的关键字，则查找右子树 } return INF; } (4)二叉排序树的插入操作，先要判断该数据元素是否存在，如果存在，则不进行插入操作；否则，将该数据元素插入到查找路径上访问的最后一个节点的左孩子或右孩子上。插入后仍要保持二叉排序树的特性。 void insertbst(bitree *root,int data) //在二叉排序树中进行插入 周国庆 《二叉排序树的建立与删除》 第6页 共19页 { bitree s; //定义树s if(*root==NULL){ //树为空的情况 s=(bitree)malloc(sizeof(bitnode)); //给s分配内存空间 s->data=data; //给定关键字与根节点关键字相等 s->lchild=s->rchild=NULL; //则左、右子树都为空 *root=s; } else if(data<(*root)->data) //给定关键字小于根节点关键字 insertbst(&((*root)->lchild),data); //则在左子树上搜索合适的位子进行插入 else if(data>(*root)->data) //给定关键字大于根节点关键字 insertbst(&((*root)->rchild),data); //在右子树上搜索合适的位子进行插入 } （5）二叉排序树的删除操作，相当于删除数据元素集合中的一个元素，不能将以该节点为根的子树都删掉，只能删除该节点，并且删除该节点后剩下的数据元素构成的仍然要求是一棵二叉排序树。 bitnode *deletebst(bitree t,int k) //二叉排序树的删除 { bitnode *p,*f,*s,*q; p=t; f=NULL; while(p){ if(p->data==k) break; f=p; if(p->data>k) p=p->lchild; else p=p->rchild; } if(p==NULL){ printf(\关键字不存在!\\n\ 周国庆 《二叉排序树的建立与删除》 第7页 共19页 } return t; if(p->lchild==NULL){ } (6)主函数模块，根据题目的要求，调用各函数来实现对二叉排序树的建立、查找、插入和删除任意节点，再调用显示函数将操作运行的结果显示出来。 int main() { int data,menu;bitree root; if(f==NULL) t=p->rchild; else if(f->lchild==p) f->lchild=p->rchild; else f->rchild=p->rchild; free(p); } else{ } return t; q=p; s=p->lchild; while(s->rchild){ } if(q==p) q->lchild=s->lchild; q=s; s=s->rchild; else q->rchild=s->lchild; p->data=s->data; free(s);