數據結構試驗——分類二叉樹和堆排序

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;/下移根結點指針，繼續(xù)比較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&