数据结构实验十二

一、实验目的

1.理解动态查找表的动态生成过程；

2.掌握二叉排序树的建立和查找；

二、实验环境

1.硬件：每个学生需配备计算机一台。

操作系统：DOS或Windows；

2.软件：DOS或Windows操作系统+Turbo c;

三、实验要求

1.定义二叉排序树的数据结构；

2.实现二叉排序树的插入算法与查找算法，并建立二叉排序树；

3.进行数据查找和建树过程的比较。

四、实验内容

1.已知一个个数为12的数据元素序列为{Dec，

Feb,Nov,Oct,June,Sept,Aug,Apr,May,July,Jan,Mar}，要求：

（1）按各数据元素的顺序构造一棵二叉排序树，并中序打印排序结果。

（2）查找数据“Sept”是否存在。 2.已知一棵二叉排序树，其根结点的地址为root。请编写一个程序，构造出一棵具有相同结点的满二叉树，且它同样是二叉排序树。提示：可利用中序遍历，分别找出各个结点序列的中点元素，然后重新构造一棵二叉树排序树。

五、代码如下

#include #include #define TRUE 1

#define FALSE 0 #define OK 1 #define ERROR 0 typedef int Status;

#define EQ(a,b)((a)==(b)) #define LT(a,b)((a)<(b)) #define LQ(a,b)((a)<=(b)) typedef int KeyType; typedef struct{ KeyType key;//关键字 char others[5];//其他数据 }ElemType;

typedef struct BiTNode{ ElemType data; struct BiTNode*lchild; struct BiTNode*rchild; }BiTNode,*BiTree;

void ylx_InitBiTree(BiTree &T){ T=NULL;//构造空二叉树 }// InitBiTree

void ylx_DestroyBiTree(BiTree &T){ if(T){ylx_DestroyBiTree(T->lchild); ylx_DestroyBiTree(T->rchild); free(T); T=NULL;} }// DestroyBiTree void ylx_InOrderTraverse(BiTree T,void(*Visit)(ElemType)){ if(T){ylx_InOrderTraverse(T->lchild,Visit); Visit(T->data);

ylx_InOrderTraverse(T->rchild,Visit);} }//InOrderTraverse

void ylx_Visit(ElemType c){ printf(\"%s\\n\

}//Visit

void ylx_Input(ElemType &c){ scanf(\"%d%s\}//Input

void ylx_Inputkey(KeyType &k){ scanf(\"%d\}//Inputkey

BiTree ylx_SearchBST1(BiTree T,KeyType else if LT(e.key,p->data.key)

p->lchild=s; else p->rchild=s; return TRUE;} else return FALSE; }//InsertBST key){ if(!T||EQ(key,T->data.key)) return T; else if LT(key,T->data.key) return

ylx_SearchBST1(T->lchild,key); else return

ylx_SearchBST1(T->rchild,key); }//SearchBST1

Status ylx_SearchBST(BiTree &T,KeyType key,BiTree f,BiTree &p){ if(!T){ p=f;//p指向查找路径上访问的最后一个结点 return FALSE;} else if EQ(key,T->data.key){ p=T;//p指向该数据元素结点 return TRUE;} else if LT(key,T->data.key) return

ylx_SearchBST(T->lchild,key,T,p); else//key大于T所指结点的关键字 return

ylx_SearchBST(T->rchild,key,T,p); }// SearchBST

Status ylx_InsertBST(BiTree &T,ElemType e){ BiTree p,s; if(!ylx_SearchBST(T,e.key,NULL,p)){ s=(BiTree)malloc(sizeof(BiTNode)); s->data=e; s->lchild=s->rchild=NULL; if(!p)//树T空 T=s;

void main(){ int i,n; BiTree t,p; KeyType j; ElemType r; Status k; printf(\"输入数据元素的个数:\"); scanf(\"%d\ ylx_InitBiTree(t);//构造空二叉树 printf(\"输入关键字(a-z或A-Z对应输入1-26)和数据:\\n\"); for(i=0;idata.others);} else ylx_DestroyBiTree(t);//销毁二叉排序树 }

六、运行结果截图