二叉排序树的建立与删除

周国庆 《二叉排序树的建立与删除》 第12页 共19页

5 结束语

在本次的课程设计中我对数据结构的知识有了更加深入的了解，认识到自己在学习编程方面还有很多的不足，还很缺乏实践锻炼。今后我要多看一些编程的书籍，不能只拘泥于课本上的知识，并注重理论与实践的结合，多上机练习编写程序，提高自己的实际动手能力和独立思考的能力，不断充实自己，更好的掌握编程思想。

而且在此次课程设计中我明白了一个道理，在实践锻炼的时候，我们要懂得总结经验，懂得反思错误，这样我们的体会才会更加的深刻。还要永保一颗虚心求教的心，这样你才能学到更多的东西。

周国庆 《二叉排序树的建立与删除》 第13页 共19页

参考文献

[1] 严蔚敏，吴伟民．数据结构（C语言版）．北京：清华大学出版社，2002 [2] 许卓群．数据结构与算法．北京：高等教育出版社，2004 [3] 金远平．数据结构(C语言版）． 北京：清华大学出版社，2005 [4] 殷人昆．数据结构（C语言版）． 北京：清华大学出版社，2001

[5] 严蔚敏，吴伟民．数据结构习题集（C语言版）．北京：清华大学出版社，2004

周国庆 《二叉排序树的建立与删除》 第14页 共19页

附 录

代码清单：

#include #include #include const int INF=0x3f3f3f3f;

typedef struct bitnode //二叉排序树一般用二叉链表来存储，这里是对其节点的结构体定义 {

int data; //定义数据域 struct bitnode *lchild; //定义左孩子指针 struct bitnode *rchild; //定义右孩子指针 }bitnode,*bitree;

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大于当前节点的关键字，则查找右子树

}

周国庆 《二叉排序树的建立与删除》 第15页 共19页

}

return INF;

void insertbst(bitree *root,int data) //在二叉排序树中进行插入 {

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); //在右子树上搜索合适的位子进行插入 }

void display(bitree root) {

if(root!=NULL){ display(root->lchild); printf(\ display(root->rchild); } }

bitnode *deletebst(bitree t,int k) //二叉排序树的删除 {

bitnode *p,*f,*s,*q;