二叉排序树建立的算法_二叉排序树的实现_二叉排序树设计

数据结构课程设计

二叉排序树的实现

起止日期： 2012 年 6 月 10日 至 2012年 6 月 16 日

学生姓名傅军荣

班

学

成级计本1102班 号11408100240 绩

指导教师(签字)

计算机与通信学院

2012年6 月 16日

1 任务描述：

功能描述：

(1)以回车(\n)为输入结束标志,输入数列L，生成一棵二叉排序树T；

(2)对二叉排序树T作中序遍历，输出结果；

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

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

二叉树及二叉链表

3.功能模块详细设计

3.1 详细设计思想

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

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

3.2 核心代码

（1）主菜单模块

void main()

{

BST T;

int crew[N];

int i=0;

int num,ch=0,j;

printf("请输入一系列的数字并以0为结束符:");

do

{

scanf("%d",&num);

if(!num) printf("您已完成输入!\n");

else { crew[i]=num; i++;}

}while(num);

T=create(crew,i);

printf("\n\n**********************\n");/*主程序菜单*/printf("\n 0: 退出程序!" );

printf("\n 1: 中序遍历树!");

printf("\n 2: 求树的ASL!");

printf("\n 3: 删除树中的元素!");

printf("\n 4: 判断是否为平衡二叉树!");

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

while(ch==ch)

{

printf("\n choose the opperation to continue:");

scanf("%d",&ch);

switch(ch){

case 0: exit(0);/*0－－退出*/

case 1: printf(" 中序遍历的结果是:\n ");

inordertraverse(T,1);/*1－－中序遍历*/break;

case 2: j=0;

computeASL(T,1,&j,0); /*2－－计算平均查找长度*/

printf(" ASL=%d/%d",j,i);

break;

case 3: printf(" 请输入您想删除的元素:");

scanf("%d",&num); /*3－－删除某个结点*/j=search(T,num,1);

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-26257-1.html