数据结构试验——分类二叉树和堆排序

1、数据结构实验3»实验报告分类二叉树及堆排序构建1、预习要求：分类二叉树结构定义。2、实验目的：(1)了解分类二叉树结构概念、查找算法程序。(2)掌握堆排序算法程序。3、实验内容及要求：(1)建立包含10个结点的分类二叉树(树结构和数据元素的值由自己设定)(2)完成分类二叉树中序遍历程序；(3)给出程序和遍历程序的结果。附源程序#include<stdlib.h>#include<stdio.h>#defineMaxSize10typedefstructintNum;floatscore1;floatscore2;floatscore3;Student;储存学生

2、信息，依次为学号，语文成绩，数学成绩，英语成绩typedefstructfloattotal;/学生总分Student*p;HeapNode;/typedefstructBinaryTreeNode(HeapNodedata;BinaryTreeNode*LChild;BinaryTreeNode*RChild;BinaryTreeNode;/分类二叉树的结点intHeapSize=9;voidDisplayarray(HeapNodea)/输出堆排序的结果(inti;for(i=1;i<10;i+)printf("学号d总分fn",ai.p->Num,ai.t

3、otal);printf("n");voidMenu_name()/作存信息(printf("nnnnnnn");printf("*n");printf("堆排序和分类二叉树的查找nn");printf("制作：n学号0909050108n");printf("班级：n");printf("指导老师：n");printf("*5);printf("nnntt");voidMaxHeapInit(HeapNodea,intsiz

4、e)/对数组a中的数据初始化为一个最大堆HeapNode*heap=a;/数组a用Heap指向HeapSize=size;/数组中数据元素个数存放到HeapSizefor(inti=HeapSize/2;i>=1;i-)从最后一个结点的根开始，直到第一个结点heap0=heapi;/将子树根结点值复制到工作空间heap0中intson=2*i;/son的双亲结点是heap0的目标位置，/son首先指向i的左孩子while(son<=HeapSize)/找左右孩子中较大结点if(son<HeapSize&&heapson.total<heapson+1.t

5、otal)son+;/son<HeapSize时，存在右孩子，如左孩子小于右孩子，son指向右孩子if(heap0.total>=heapson.total)/大孩子再与工作空间中结点值再比较break;/工作空间中值大，找到heap0的目标位置heapson=heapson;/将大孩子上移至双亲位置son*=2;/son下移一层到上移的结点(大孩子)位置heapson=heap0;/heap0存放到目标位置/最大堆中删除顶结点，并放入x中返回算法boolMaxHeapDelete(HeapNodea,HeapNode&x)HeapNode*heap=a;if(HeapSi

6、ze=0)returnfalse;/堆空x=heap1;最大结点存放到xheap0=heapHeapSize-;/最后一个结点存放到heap0,调整堆中元素的个数inti=1,son=2*i;while(son<=HeapSize)if(son<HeapSize&&heapson.total<heapson+1.total)son+;if(heap0.total>=heapson.total)break;heapi=heapson;/孩子上移i=son;/下移根结点指针，继续比较son=son*2;heapi=heap0;returntrue;voidH

7、eapSort(HeapNodea,intn)/利用堆对a1:n数组中的数据排序HeapNode*heap=a;MaxHeapInit(heap,n);/Heap初始化为最大堆HeapNodex;intm=1;for(inti=n-1;i>=1;i-)MaxHeapDelete(heap,x);printf("第堆排序结果n",m);m+;Displayarray(a);system("pause");system("cls");heapi+1=x;)BinaryTreeNode*SortBinaryTreeInsert(Bin

8、aryTreeNode*&BT,HeapNode&x)/求如果不重复出现，则插入结点xBinaryTreeNode*p;BinaryTreeNode*parent=NULL;指向p的双亲p=BT;while(p)parent=p;if(x.total<p->data.total)p=p->LChild;elseif(x.total>p->data.total)p=p->RChild;elsereturnp;重复出现，即相等值结点出现)/找到插入点，为x申请一个空间填入其值，并将该结点连接至parentBinaryTreeNode*q=newB

9、inaryTreeNode;q->data=x;q->LChild=NULL;q->RChild=NULL;if(BT)/原树非空if(x.total<parent->data.total)parent->LChild=q;elseparent->RChild=q;else/插入到空树中BT=q;returnBT;intSortBinaryTreeSearch(BinaryTreeNode*BT,HeapNode&x,float&SearchKey)/求查找关键字为SearchKey的结点值xBinaryTreeNode*p=BT;wh

10、ile(p)if(SearchKey<p->data.total)p=p->LChild;elseif(SearchKey>p->data.total)p=p->RChild;elsex=p->data;return1;return0;voidmain()HeapNodea10;Studentstudent10;HeapNodex;floatkey;Student*p;BinaryTreeNode*BT;intre;intm=20010000;Menu_name();for(inti=0;i<=10;i+)studenti.Num=i;ai.p=

11、&studenti;）student0.score1=0;student0.score2=0;student0.score3=0;student1.score1=85;student1.score2=88;student1.score3=97;student2.score1=92.5;student2.score2=91;student2.score3=95;student3.score1=95;student3.score2=98;student3.score3=99;student4.score1=85;student4.score2=87;student4.score3=96.5

12、;student5.score1=96;student5.score2=93;student5.score3=100;student6.score1=72;student6.score2=76;student6.score3=70.5;student7.score1=65;student7.score2=53;student7.score3=53;student8.score1=88;student8.score2=94;student8.score3=90.5;student9.score1=96.5;student9.score2=83;student9.score3=65;输入学生信息p

13、rintf（"堆排序操作nn"）;for(i=0;i<=10;i+)(studenti.Num=m;ai.p=&studenti;ai.total=studenti.score1+studenti.score2+studenti.score3;m+;/构造堆树printf("未排序前的堆结点信息n");Displayarray(a);system("pause");system("cls");intkeep=HeapSize;HeapSort(a,HeapSize);printf("n堆排序结果:n");Displayarray(a);printf("n");system("pause");BT=NULL;printf("分类二叉树的操作n");for(i=1;i<10;i+)(SortBinaryTreeInsert(BT,ai);/构造分类二叉树for(;)(printf("请输入您要查找的学生的总分，输入0结束查找)scanf("%f&