数据结构实验——分类二叉树和堆排序.doc

数据结构实验报告 二一年数据结构实验3实验报告分类二叉树及堆排序构建1、预习要求：分类二叉树结构定义。2、实验目的： （1）了解分类二叉树结构概念、查找算法程序。（2）掌握堆排序算法程序。3、实验内容及要求：（1）建立包含10个结点的分类二叉树（树结构和数据元素的值由自己设定）；（2）完成分类二叉树中序遍历程序；（3）给出程序和遍历程序的结果。附源程序#include #include #define MaxSize 10typedef structint Num;float score1;float score2;float score3;Student;/储存学生信息，依次为学号，语文成绩，数学成绩，英语成绩typedef struct float total;/学生总分Student * p;HeapNode;/typedef struct BinaryTreeNodeHeapNode data;BinaryTreeNode * LChild;BinaryTreeNode * RChild;BinaryTreeNode;/分类二叉树的结点int HeapSize=9;void Displayarray(HeapNode a)/输出堆排序的结果int i;for(i=1;iNum,ai.total);printf(n);void Menu_name() /作者信息 printf(nnnnnnn);printf( *n);printf( 堆排序和分类二叉树的查找nn);printf( 制作: n 学号 0909050108n);printf( 班级: n);printf( 指导老师: n);printf( *n);printf(nnntt);void MaxHeapInit (HeapNode a, int size)/ 对数组a 中的数据初始化为一个最大堆HeapNode *heap=a;/数组a用Heap指向HeapSize=size;/数组中数据元素个数存放到HeapSize for (int i = HeapSize/2; i = 1; i-)/从最后一个结点的根开始，直到第一个结点heap0 = heapi; / 将子树根结点值复制到工作空间heap0中int son = 2*i; / son的双亲结点是heap0的目标位置，/ son首先指向i的左孩子while (son = HeapSize) / 找左右孩子中较大结点if (son HeapSize & heapson.total heapson +1.total)son +;/ son = heapson.total) / 大孩子再与工作空间中结点值再比较break;/工作空间中值大，找到heap0的目标位置heapson /2 = heapson; / 将大孩子上移至双亲位置son*= 2;/ son下移一层到上移的结点（大孩子）位置heapson /2 = heap0;/heap0存放到目标位置 /最大堆中删除顶结点，并放入x中返回算法bool MaxHeapDelete (HeapNode a, HeapNode &x)HeapNode *heap = a;if (HeapSize = 0) return false; / 堆空x = heap1; / 最大结点存放到xheap0 = heapHeapSize-; / 最后一个结点存放到heap0，调整堆中元素的个数int i = 1, son = 2*i; while (son = HeapSize) if (son HeapSize & heapson .total= heapson.total)break; heapi = heapson; / 孩子上移i = son; / 下移根结点指针，继续比较son = son * 2; heapi = heap0; return true;void HeapSort(HeapNode a, int n)/ 利用堆对a1:n 数组中的数据排序HeapNode *heap=a;MaxHeapInit(heap, n); / Heap初始化为最大堆HeapNode x;int m=1;for (int i = n-1; i = 1; i-) MaxHeapDelete (heap,x);printf(第%d堆排序结果n,m);m+;Displayarray(a);system(pause);system(cls);heapi+1 = x;BinaryTreeNode *SortBinaryTreeInsert (BinaryTreeNode *&BT, HeapNode &x)/求如果不重复出现，则插入结点x BinaryTreeNode *p; BinaryTreeNode *parent = NULL;/指向p的双亲 p=BT;while (p) parent = p;if (x.total data.total) p=p-LChild;else if (x.total p-data.total) p = p-RChild;else return p;/重复出现，即相等值结点出现 / 找到插入点，为x申请一个空间填入其值，并将该结点连接至 parent BinaryTreeNode *q = new BinaryTreeNode;q -data = x;q-LChild=NULL;q-RChild=NULL;if (BT) / 原树非空if (x.total data.total)parent -LChild = q;else parent -RChild = q;else / 插入到空树中BT = q;return BT;int SortBinaryTreeSearch (BinaryTreeNode *BT, HeapNode &x, float &SearchKey)/求查找关键字为SearchKey的结点值xBinaryTreeNode *p = BT;while (p) if (SearchKeydata.total)p = p-LChild;else if (SearchKeyp-data.total) p = p-RChild;else x = p-data;return 1;return 0;void main() HeapNode a10;Student student10;HeapNode x;float key;Student *p;BinaryTreeNode *BT;int re;int m=20010000;Menu_name();for(int i=0;i=10;i+)studenti.Num=i;ai.p=&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;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;/输入学生信息printf(堆排序操作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);int keep=Heap