二叉排序树的实现_课程设计报告

中北大学

数 据 结 构

课 程 设 计 说 明 书

学生姓名: 学 院: 专 业: 题 目: 指导教师

程亚男 学 号： 软件学院 软件工程 1021011616 二叉排序树的实现 何志英

2011年12月20日

1 / 7

真诚为您提供优质参考资料，若有不当之处，请指正。

1. 设计任务概述：

二叉链表作存储结构和顺序表作存储结构 输入数列L， 以回车(‘\\\\n’)为输入结束标志生成二叉排序树T； 对二叉排序树T作中序遍历,并输出结果

输入元素x，查找二叉排序树T 找到该节点x 无结点x 存在含x的结点，则删除该结点，并作中序遍历 二叉排序树T是否为平衡二叉树 NO! OK! 2 / 7

真诚为您提供优质参考资料，若有不当之处，请指正。

功能描述：

(1)以回车('\\n')为输入结束标志,输入数列L，生成一棵二叉排序树T； (2)对二叉排序树T作中序遍历，输出结果；

(3)输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”。

2.本设计所采用的数据结构

二叉树及二叉链表

3.功能模块详细设计

3.1 详细设计思想

建立二叉排序树采用边查找边插入的方式。查找函数采用递归的方式进行查找。如果查找到相等的则插入其左子树。然后利用插入函数将该元素插入原树。 对二叉树进行中序遍历采用递归函数的方式。在根结点不为空的情况下，先访问左子树，再访问根结点，最后访问右子树。

删除结点函数，采用边查找边删除的方式。如果没有查找到，进行提示；如果查找到结点则将其左子树最右边的节点的数据传给它，然后删除其左子树最右边的节点。

3.2 核心代码 （1）主菜单模块 int main(){

LNode root=NULL; int Num,a,x;

printf(\"\\n\\n *******************************\\n\");

printf(\" ************主菜单*************\\n\");

printf(\" *1:进行中序排列 *\\n\");

printf(\" *2:进行删除操作 *\\n\");

printf(\" *3:退出 *\\n\");

printf(\" *******************************\\n\");

printf(\"请输入要进行操作的数字以0结束：\\n\");

运行结果

3 / 7

真诚为您提供优质参考资料，若有不当之处，请指正。

（3）中序遍历模块

void view(LNode p){//中序遍历函数 } 运行结果

if(p){ } return;

view(p->lch);

printf(\"%d \view(p->rch);//递归调用 return;

4 / 7

真诚为您提供优质参考资料，若有不当之处，请指正。

（3）删除模块

LNode DelNode(LNode t,int x) {

LNode p=t; LNode q=NULL; LNode s;

LNode f;

while(p!=NULL){ }

if(p->date==x){ } q=p;

if(x<=p->date){ } else{ }

p=p->rch; p=p->lch; break;

5 / 7

真诚为您提供优质参考资料，若有不当之处，请指正。

if(p==NULL){ }

if(p->lch) {

s=p->lch; //s指向其左子树; f=p->lch; //f指向其左子树;

while(s-> rch)//搜索左子树的最右边的叶子结点 { }

p->date=s->date;

if(f !=s){

//若不是p的左孩子，把r的左孩子作为r的父

f=s; s=s->rch;

printf(\"不存在您要删除的数 %d !\return p;

亲的右孩子

} else {

if(q->lch==p){

q->lch = p->rch; } else { } free(s); return p;

p->lch = s->lch; //否则结点p的左子树指向s的左子树 f-> rch=s->lch;

6 / 7

真诚为您提供优质参考资料，若有不当之处，请指正。

}

}

} else{ } free(p); return q;

q->rch = p->rch;

3.3 程序运行结果

4.课程设计心得、存在问题及解决方法

通过这次课程设计，我进一步的懂得了二叉链表的建立方法，进一步的了解了二叉排序树的构造方法。对函数的构造以及调用有了更进一步的掌握，让我在调试程序是有了一定的经验。多考虑算法的可行性。在遇到问题是认真考虑。同时让我意识到数据结构在编程中的重要作用。算法的优越性对程序的重要性。让我在调试程序是有了一定的经验。

7 / 7