利用二叉排序树对一组数据排序并查找元素

1、数据结构实验报告实验题目: 利用二叉排序树对一组数据排序并查找元素实验目的：(1)熟悉二叉排序树的生成算法；了解将排序二叉树转化为有序排列的方法；学会在一组数据中查找元素。实验内容：建立一组数据的二叉排序树，然后中序遍历，并查找待查找元素。 一、需求分析1输入的形式和输入值的范围:本程序要求输入待排序数的个数，并逐个输入待排序数，最 后输入待查找元素的值。2输出的形式:按从小到大的顺序输出排过序的数，并输出查找结果，如果存在，还需输出 待查找数在已排序序列中的位置。3程序所能达到的功能:对确定个数的一组数实现递增排序，并查找待查找元素。 4测试数据：待排序数个数:5;待排序数:12 43 23

2、 54 8;已存在元素查找:23;不存在的元素查找:10概要设计二叉排序树的生成模块:根据二叉排序树的定义，任一节点如果有左子树，其左子 树各节点的数据必须小于该节点的数据；任一节点如果有右子树，其右子树各节点 的数据必须等于或大于该节点的数据。则可将第一个数据作为整个二叉排序树的根 节点，以后的数据都从根节点起，由上而下逐层与原有节点的数据相比较，若较原 节点数值小，则进而与其左孩子节点的数值比，否则与其右孩子节点数据比，直至 找到一个节点相应的指针是空指针了，即将新结点插入此处作为终端节点。已排序序列的输出与查找元素模块:根据排序二叉树的结构特点，只要对该二叉树 进行中序遍历，即可按从小到

3、大的顺序访问这些数据节点，再在访问这些节点的时 候与待查找元素比较，如果找到，记下该数据位置，如果访问完了还没找到，则待 查找元素不存在。详细设计定义结构体变量typedef struct nodeint data;struct node *lchild;struct node *rchild;Lnode,*Linklist;定义指针栈typedef structLinklist dataMAXSIZE;int top;Seqstack;初始化栈函数void Initstack(Seqstack &s)s.top=-1;判断栈空函数，如果栈空返回1，否则返回 0 int StackEmpty(

4、Seqstack &s)if(s.top=-1)return 1;elsereturn 0;入栈函数void push(Seqstack &s,Linklist x)s.top+;s.datas.top=x;出栈函数Linklist pop(Seqstack &s)return s.datas.top-;二叉排序树的生成函数，具体算法为:读取一个待排序数；生成一个新节点，将读入数据赋给新节点；若根节点为空，则另根节点等于该新节点，否则Q如果小于根节点，沿左链域比较；Q否则沿右链域比较；直至到终端，插入该结点。Linklist build(Linklist BT)int n,i,a100=0;L

5、inklist p,q;prin tf(请输入数的个数:)；scanf(%d,&n);prin tf(请输入待排序的数:n); for(i=0;idata=ai;p-lchild=NULL;p-rchild=NULL;if(BT=NULL)BT=p; q=p;elseq=BT;while(p-data!=q-data)if(p-datadata)if(q-lchild=NULL)q-lchild=p;else q=q-lchild;elseif(q-rchild=NULL)q-rchild=p;else q=q-rchild;return BT;已排序序列的输出与查找元素函数:对二叉树进行中序

6、遍历，并在访问节点的同时 以 m 计数器记下已访问节点的个数，同时将该节点数据与待查找数据比较，如果相等，则用n记下此时的m值，如果二叉树遍历完了n仍然为0则代表没找到，最 后返回 n 的值。int visit(Linklist BT,int &a,int &n)int m=0;Linklist p;Seqstack s;Initstack(s);p=BT;push(s,p);while(!StackEmpty(s)while(p-lchild!=NULL) p=p-lchild; push(s,p);dop=pop(s);m+;if(p-data=a)n=m;printf(%d ,p-dat

7、a);while(p-rchild=NULL&!StackEmpty(s); if(p-rchild!=NULL) p=p-rchild; push(s,p);return n;主函数模块，其中a为待排序数的个数，BT为二叉排序树的根节点 int main()int a,t,n=0;Linklist BT=NULL;BT=build(BT);prin tf(请输入待查找元素:)；scanf(%d,&a);prin tf(排序结果为:n); t=visit(BT,a,n);printf(n);if(n!=0)printf(待查找元素存在,且在已排序序列的第%d位!n,n); else prin

8、tf(待查找元素不存在!n);return 0;使用说明、测试分析及结果程序使用说明：(1)该程序在VC环境下运行；(2) 其余操作按提示进行即可。测试结果与分析:(1) 已存在数据查找测试G:E 学习 DS07Deb ugDS07.exe(2)不存在数据查找汚数素 在to 8兀 4w y 需4找G:E 学习 DS07Deb ugDS07.exe(2)不存在数据查找汚数素 在to 8兀 4w y 需4找：5不he 舉5查为43素y 馨23待果3兀an 天入3人结2找S 務 4 幫12杳一es 當12羸8待pr：10cont inue回顾与分析:在二叉排序树中，其节点是按照左子树、根、右子树的次序由小到大排序的 因此在生成模块中对每一个数据都需从根节点开始比较来确定其属于哪个节点的哪个孩子 而且在序列输出模块中采用了二叉树的中序遍历以让所得节点序列为一个有序序列。运行界面。五、实验总结本次程序在排序树生成模块中关于判断新结点是否已链到排序树终端的条件