二叉排序樹的實(shí)現(xiàn)(最終版)

課程名稱數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 題目名稱二叉樹的實(shí)現(xiàn) 學(xué)生學(xué)院應(yīng)用數(shù)學(xué)學(xué)院 學(xué)號(hào) 學(xué)生姓名阮志敏 指導(dǎo)教師劉志煌 二叉排序樹的實(shí)現(xiàn)1)編程實(shí)現(xiàn)二叉排序樹，包括生成、插入、刪除；2)對(duì)二叉排序樹進(jìn)行先根、中根和后根非遞歸遍歷；3)每次對(duì)樹的修改操作和遍歷操作的顯示結(jié)果都需要在屏幕上用樹的形狀表示出來(lái)。4)分別用二叉排序樹和數(shù)組去存儲(chǔ)一個(gè)班(50人以上)的成員信息(至少包括學(xué)號(hào)、姓名、成績(jī)3項(xiàng))，對(duì)比查找效率，并說(shuō)明在什么情況下二叉排序樹效率高，為什么？5)格式按照作業(yè)的要求，對(duì)數(shù)據(jù)測(cè)試，分析，總結(jié)和改進(jìn)的工作要做詳細(xì)一點(diǎn)。二、解決方案和關(guān)鍵代碼1)首先定義二叉樹的結(jié)構(gòu)體，代碼如下：TreeNodetypedefstructTreeNode*TreePosition;typedefstructTreeNode*SearchTree;typedefstructTreeNode*Tree;typedefintTreeElementType;structTreeNode{//二叉樹TreeElementTypeelement;//節(jié)點(diǎn)中的元素SearchTreeleft;//左兒子SearchTreeright;//右兒子intleght;//節(jié)點(diǎn)的深度，用于打印intposition;//節(jié)點(diǎn)的位置，用于打印2)實(shí)現(xiàn)插入和生成二叉樹節(jié)點(diǎn)的方法。在這里用到了遞歸插入的方法。chTreeinsertTreeNodeTreeElementTypexSearchTreetreeif(tree==NULL){tree=makeTree(x,NULL,NULL);//插入在該處}elseif(x<tree->element){tree->left=insertTreeNode(x,tree->left);}elseif(x>tree->element){tree->right=insertTreeNode(x,tree->right);}//如果相等，什么也不做ree}當(dāng)tree==NULL時(shí)，就是遞歸終止的條件，也是插入該節(jié)點(diǎn)的地方，在這里，用makeTree()其代碼如下：emakeTreeTreeElementTypexSearchTreeleftSearchTreerightSearchTreenode=(SearchTree)malloc(sizeof(structTreeNode));if(node==NULL){printf("makeTreeNodefail!\n");}else{node->element=x;node->left=left;node->right=right;}returnnode;}3)實(shí)現(xiàn)二叉樹節(jié)點(diǎn)刪除的方法。情況一：被刪除的節(jié)點(diǎn)同時(shí)含有左兒子和右兒子。在這種情況下，必須找出一個(gè)合適的節(jié)點(diǎn)來(lái)替代被刪除的節(jié)點(diǎn)。由于二叉樹的特性，被刪除節(jié)點(diǎn)右子樹中的節(jié)點(diǎn)都比左子樹節(jié)點(diǎn)大，因此，可以替代原節(jié)點(diǎn)的節(jié)點(diǎn)必然在被刪除節(jié)點(diǎn)的右子樹中，并且是右子樹的最小節(jié)點(diǎn)。所以，在這種情況下，應(yīng)該把被刪除節(jié)點(diǎn)的右子樹中最小節(jié)點(diǎn)替代被刪除節(jié)點(diǎn)。情況二：被刪除節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)。顯然，應(yīng)該把它的子節(jié)點(diǎn)替代它。情況三：被刪除節(jié)點(diǎn)沒(méi)有子節(jié)點(diǎn)。此時(shí)，直接刪除它。archTreedeleteTreeNodeTreeElementTypexSearchTreetreeTreePositiontmpNode;if(tree==NULL){//到葉節(jié)點(diǎn)了，還沒(méi)找到可以刪除的printf("notfound!\n");}elseif(x<tree->element){tree->left=deleteTreeNode(x,tree->left);}elseif(x>tree->element){tree->right=deleteTreeNode(x,tree->right);}elseif(x==tree->element){if(tree->left&&tree->right){tmpNode=findMin(tree->right);//找出右子樹中最小的tree->element=tmpNode->element;//把右子樹中最小的值給當(dāng)前樹>節(jié)點(diǎn)//把tree右子樹中最小值的節(jié)點(diǎn)刪除了,那個(gè)要?jiǎng)h除的節(jié)點(diǎn)不可能有左>兒子tree->right=deleteTreeNode(tree->element,tree->right);}else{//只有一個(gè)子節(jié)點(diǎn)，或者沒(méi)有子節(jié)點(diǎn)tmpNode=tree;if(tree->left==NULL){//0個(gè)子節(jié)點(diǎn)也包含在內(nèi)tree=tree->right;}elseif(tree->right==NULL){tree=tree->left;}free(tmpNode);}}ree}其中的findMin()方法為找出以某個(gè)節(jié)點(diǎn)為根的樹的最小節(jié)點(diǎn)，在這里可以用循環(huán)遍歷tree->left來(lái)實(shí)現(xiàn)，也可以用遞歸來(lái)實(shí)現(xiàn)，代碼如下：TreePositionfindMin(SearchTreetree){//遞歸實(shí)現(xiàn)if(tree==NULL){returnNULL;}if(tree->left!=NULL){returnfindMin(tree->left);}else{ntree}}2.對(duì)二叉排序樹進(jìn)行先根、中根和后根非遞歸遍歷1)先根遍歷先根遍歷先訪問(wèn)根，再訪問(wèn)左兒子，接著訪問(wèn)右兒子。上圖中的樹，如果用先根遍歷，順序則是A-B-E-F-C要實(shí)現(xiàn)非遞歸遍歷，必須使用循環(huán)來(lái)進(jìn)行遍歷。這就需要使每次循環(huán)時(shí)，都有一致的操作。為了一致性，先定義每次循環(huán)中的一致性操作：每次循環(huán)只處理一個(gè)節(jié)點(diǎn)，也就是打印當(dāng)前節(jié)點(diǎn)，其左節(jié)點(diǎn)要等到下次循環(huán)再打印，這時(shí)，如果當(dāng)前節(jié)點(diǎn)有左右節(jié)點(diǎn)，則需要儲(chǔ)存當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)和右節(jié)點(diǎn)，以便下次循環(huán)時(shí)取出打印，如果沒(méi)有左右節(jié)點(diǎn)，則直接進(jìn)入下次循環(huán)。在這里，有兩種數(shù)據(jù)結(jié)構(gòu)可用于儲(chǔ)存待打印節(jié)點(diǎn)，一個(gè)是隊(duì)列，一個(gè)是棧。先嘗試隊(duì)列，隊(duì)列的特性是先進(jìn)先出，我們希望在訪問(wèn)完當(dāng)前節(jié)點(diǎn)后，儲(chǔ)存當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)和右節(jié)點(diǎn)，以便下次循環(huán)進(jìn)取出進(jìn)行打印，因此，節(jié)點(diǎn)儲(chǔ)存的順序必須為先儲(chǔ)存左節(jié)點(diǎn)，再儲(chǔ)存右節(jié)點(diǎn)。以上圖的樹為例：當(dāng)用隊(duì)列時(shí)，會(huì)先訪問(wèn)A節(jié)點(diǎn)，然后儲(chǔ)存B到隊(duì)列，再儲(chǔ)存C到隊(duì)列，此時(shí)，隊(duì)列中的元素為BC。下次循環(huán)時(shí)，會(huì)把B出列，訪問(wèn)完B后，再儲(chǔ)存E和F，此時(shí)，隊(duì)列中的元素為CEF。下次循環(huán)時(shí)，會(huì)把C出列進(jìn)行訪問(wèn)。顯然，這種訪問(wèn)順序A-B-C不是正確的訪問(wèn)順序，正確的應(yīng)該是A-B-E，因此隊(duì)列并不能滿足接下來(lái)用棧進(jìn)行儲(chǔ)存嘗試。當(dāng)使用棧時(shí)，由于棧的特性為后進(jìn)先出，故在第一次循環(huán)BCBB棧進(jìn)行訪問(wèn)，然后把F入棧，再把E入棧。這時(shí)，訪問(wèn)順序?yàn)锳-B-E-F-C，因此，我們可以用棧來(lái)作為循環(huán)遍歷時(shí)的儲(chǔ)存數(shù)據(jù)結(jié)構(gòu)。此時(shí)，每輪循環(huán)的步驟就很清晰了：如果棧非空，出棧一個(gè)元素作為當(dāng)前節(jié)點(diǎn)，先訪問(wèn)或者打印當(dāng)前節(jié)點(diǎn)，接著，如果當(dāng)前節(jié)點(diǎn)有左兒子或者右兒子，則先把右兒子入棧，再把左兒子入棧然后進(jìn)入下次循環(huán)。如果當(dāng)前節(jié)點(diǎn)沒(méi)有兒子，則直接進(jìn)入下次循環(huán)。具體代碼如下：voidpreorderTraversalTreetree){Stackstack=createStack(10);push(tree,stack);while(!isStackEmpty(stack)){TreePositionnode=pop(stack);printf("%d",node->element);if(node->right!=NULL){push(node->right,stack);}if(node->left!=NULL){push(node->left,stack);}}}子。上圖的樹中，中根遍歷的順序?yàn)镈-B-F-E-A-C。在中根遍歷過(guò)程中，要訪問(wèn)當(dāng)前節(jié)點(diǎn)，首先要訪問(wèn)當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)，而如果左節(jié)點(diǎn)又有左節(jié)點(diǎn)，則會(huì)一直向左下去。比如要訪及其左邊的節(jié)點(diǎn)全部壓入棧中，此時(shí)，棧中的元素為ABD，然后開始循環(huán)遍歷。在循環(huán)中，先從棧中彈出一個(gè)節(jié)點(diǎn)，訪問(wèn)該節(jié)點(diǎn)，然后判斷該節(jié)點(diǎn)是否有右節(jié)點(diǎn)，如果有右節(jié)點(diǎn)，則把其右子樹中右節(jié)點(diǎn)開始的所有左節(jié)點(diǎn)壓入棧中，這樣，下一次循環(huán)就能訪問(wèn)到右節(jié)點(diǎn)所在子樹的最左邊節(jié)點(diǎn)了。因?yàn)橐L問(wèn)右節(jié)點(diǎn)，必須先訪問(wèn)右節(jié)點(diǎn)的左子樹中的最左B的時(shí)候，訪問(wèn)B，然后B有右節(jié)點(diǎn)E，因此，把EF都入棧，然后開始下一次循環(huán)。下一次循環(huán)開始時(shí)，就能取出F進(jìn)行訪問(wèn)了。具體代碼如/**中序遍歷voidinorderTraversal(Treetree){Stackstack=createStack(30);if(tree==NULL){printf("thetreeisNULL,can'ttraversal\n");}else{pushLeftToStack(tree,stack);while(!isStackEmpty(stack)){TreePositionnode=pop(stack);printf("%d",node->element);if(node->right){pushLeftToStack(node->right,stack);}}printf\n");}}其中的pushLeftToStack()方法從該節(jié)點(diǎn)開始，一直向左，把左節(jié)點(diǎn)全部壓入棧中，代碼staticvoidpushLeftToStack(Treetree,Stackstack){while(tree){push(tree,stack);tree=tree->left;}}3)后根非遞歸遍歷后根遍歷中，先訪問(wèn)當(dāng)前節(jié)點(diǎn)的左兒子，再訪問(wèn)右兒子，最后才訪問(wèn)當(dāng)前節(jié)點(diǎn)。在上圖的樹中，訪問(wèn)的順序?yàn)镈-F-E-B-C-A。要實(shí)現(xiàn)非遞歸遍歷，必須明確每一次循環(huán)中要進(jìn)行的操作。和中根遍歷相似，在循環(huán)開始前應(yīng)該先把根節(jié)點(diǎn)開始，一直向左的節(jié)點(diǎn)壓入棧中。然后再開始循環(huán)，循環(huán)開始時(shí)先出棧一個(gè)節(jié)點(diǎn)，如果該節(jié)點(diǎn)沒(méi)有右兒子，那么就可以直接訪問(wèn)該節(jié)點(diǎn)了，但如果該節(jié)點(diǎn)有右兒子，那么就還不能訪問(wèn)該節(jié)點(diǎn)，必須先訪問(wèn)完該節(jié)點(diǎn)的右子樹。如上圖中，先彈出D，由于D沒(méi)有右兒子，則可以直接訪問(wèn)，進(jìn)入下一次循環(huán)。但彈出B時(shí)，由于B有右兒子E，那么此時(shí)還不能訪問(wèn)B，因此要將B重新壓回棧中，然后再把EF入棧。這里的問(wèn)題在于，當(dāng)訪問(wèn)完FE后，又回把B重新出棧。如果按照剛才的做B，B又會(huì)重新壓入棧，同時(shí)EF也會(huì)再次入棧，這樣就會(huì)造成無(wú)限循環(huán)。一種解決這種無(wú)限循環(huán)的方式是：訪問(wèn)完D后，出棧B，由于B有右兒子，為了避免后面的無(wú)限循環(huán)，可以在把B重新入棧時(shí)，先用臨時(shí)變量T保存B的右兒子，然BB入棧，接著再把臨時(shí)變量T作為原B的右兒子入棧，這樣，再次彈出B時(shí)，由于B的兒子為空了，所以這次會(huì)直接訪問(wèn)B，從而避免了無(wú)限循環(huán)。但是這樣破壞了樹的結(jié)構(gòu)，顯然是不好的。因此要尋找另外的辦法來(lái)避免無(wú)限循環(huán)，現(xiàn)在的重點(diǎn)是標(biāo)識(shí)出B已經(jīng)被重新壓入過(guò)一次棧了，也就是說(shuō)B被壓了兩次棧了。如果可B了。在這里采取的做法是：創(chuàng)建多一個(gè)棧，設(shè)其為T，第一次彈出B時(shí)，由于B有右兒子。則把B壓回到原本的棧中，同時(shí)也把B壓入棧T中。這樣，每次彈出一個(gè)節(jié)點(diǎn)時(shí)，如果這個(gè)節(jié)點(diǎn)有右兒子則先和棧T中的最頂元素做下對(duì)比，如果和棧T中的最頂元素相同，則證明這個(gè)有右兒子的節(jié)點(diǎn)在之前已經(jīng)被壓入多一次棧了。因此，可以直接訪問(wèn)這個(gè)節(jié)點(diǎn)了。在上面例子中，訪問(wèn)完FE后，再次把B出棧，此時(shí)B有右兒子，故和棧T中的最頂元素做比較，發(fā)現(xiàn)棧T中的最頂元素也是B，因此證明B已經(jīng)被壓入過(guò)兩次了，故可以直/**后序遍歷voidpostorderTraversalTreetree{Stackstack=createStack(30);Stacktmp=createStack(30);//保存入棧兩次的，有右子樹的節(jié)點(diǎn)pushLeftToStacktreestackwhile(!isStackEmpty(stack)){TreePositionnode=pop(stack);if(node->right==NULL){//如果右兒子為空，則直接輸出printf("%d",node->element);}else{if(isStackEmpty(tmp)||node!=top(tmp)){push(node,stack);//再次把有右兒子的節(jié)點(diǎn)入棧push(node,tmp);//同時(shí)也把該節(jié)點(diǎn)壓入臨時(shí)棧中pushLeftToStack(node->right,stack);}else{//如果該節(jié)點(diǎn)兩次入棧了，就把它訪問(wèn)并輸出poptmp;printf("%d",node->element);}}}printfn");disposeStack(stack);disposeStack(tmp);}3.打印樹為了在終端中打印一棵樹，則需要確定在打印一個(gè)節(jié)點(diǎn)時(shí)，前面需要打印多少個(gè)空格。在這里，我們可以為每個(gè)節(jié)點(diǎn)設(shè)置一個(gè)位置。位置的設(shè)置方式如下圖：這棵樹高為3,故根節(jié)點(diǎn)的位置為=8，這個(gè)8代表在打印根節(jié)點(diǎn)時(shí)，需要在其前面打印8-1=7個(gè)空格。確定好根節(jié)點(diǎn)的位置后，就可以確定其子節(jié)點(diǎn)的位置了。從最高的層開始，設(shè)置第1層所有節(jié)點(diǎn)的深度為0,第2層所有節(jié)點(diǎn)的深度為1,依此類推。設(shè)某個(gè)節(jié)點(diǎn)pp-R/2^l。如上面的根節(jié)點(diǎn)的左兒子的位置為8-2^1=4。同理，根的右兒子的位置為8+2^1=12。第3層中的第一個(gè)節(jié)點(diǎn)的位置為4-8/2^2=4-2=2。這樣，只要知道根節(jié)點(diǎn)的位置，可以知道整棵樹的位置了。而根節(jié)點(diǎn)的位置R=2^h,其中h為樹的高度。先是獲取樹中每個(gè)節(jié)點(diǎn)的深度和整棵樹的高度的代碼，在這里，用層序遍歷樹來(lái)進(jìn)行staticinttreeHeight=-1;voidgetLegthOfTreeTreetreeQueueparentQueue=CreateQueue(TRAVERSAL_QUEUE_SIZE);//保存父節(jié)點(diǎn)的隊(duì)列QueuechildQueue=CreateQueue(TRAVERSAL_QUEUE_SIZE);//保存子節(jié)點(diǎn)的隊(duì)列intleght=0;//當(dāng)前的深度treeHeight=-1;Enqueue(tree,parentQueue);while(!IsQueueEmpty(parentQueue)){while(!IsQueueEmpty(parentQueue)){TreePositionnode=FrontAndDequeue(parentQueue);//出列node->leght=leght;if(node->left!=NULL)Enqueue(node->left,childQueue);//把子節(jié)點(diǎn)入子隊(duì)列中if(node->right!=NULL)Enqueue(node->right,childQueue);}//交換父子隊(duì)列QueuetempQueue=parentQueue;parentQueue=childQueue;childQueue=tempQueue;leght++;//每遍歷一層，深度加一treeHeight++;//樹高度加一}DisposeQueue(parentQueue);DisposeQueue(childQueue);}接下來(lái)是獲取樹中每個(gè)節(jié)點(diǎn)的位置的代碼，這里同樣使用層序遍歷來(lái)獲取每個(gè)節(jié)點(diǎn)的staticvoidgetPositionOfTreeTreetree{QueueparentQueue=CreateQueue(TRAVERSAL_QUEUE_SIZE);QueuechildQueue=CreateQueue(TRAVERSAL_QUEUE_SIZE);Enqueue(tree,parentQueue);tree->position=1<<treeHeight;inttopPosition=tree->position;while(!IsQueueEmpty(parentQueue)){while(!IsQueueEmpty(parentQueue)){TreePositionnode=FrontAndDequeue(parentQueue);if(node->left!=NULL){intleftStep=topPosition>>node->left->leght;node->left->position=node->position-leftStep;Enqueue(node->left,childQueue);}if(node->right!=NULL){intrightStep=topPosition>>node->right->leght;node->right->position=node->position+rightStep;Enqueue(node->right,childQueue);}}QueuetempQueue=parentQueue;parentQueue=childQueue;childQueue=tempQueue;}DisposeQueue(parentQueue);DisposeQueue(childQueue);}voidprintTree(Treetree){getLegthOfTreetreegetPositionOfTreetree);printfn");QueueparentQueue=CreateQueue(TRAVERSAL_QUEUE_SIZE);QueuechildQueue=CreateQueue(TRAVERSAL_QUEUE_SIZE);intprePosition=0;Enqueue(tree,parentQueue);while(!IsQueueEmpty(parentQueue)){while(!IsQueueEmpty(parentQueue)){TreePositionnode=FrontAndDequeue(parentQueue);intspaceNum=node->position-prePosition-1;printSpace(spaceNum);printf("%2d",node->element);prePosition=node->position;if(node->left!=NULL)Enqueue(node->left,childQueue);if(node->right!=NULL)Enqueue(node->right,childQueue);}prePosition=0;printf\n");QueuetempQueue=parentQueue;parentQueue=childQueue;childQueue=tempQueue;}DisposeQueue(parentQueue);DisposeQueue(childQueue);}4.對(duì)比存儲(chǔ)50個(gè)學(xué)生信息的二叉樹和數(shù)組的查找效率。二叉樹和數(shù)組的查找效率是看情況而言的，二叉樹的查找效率顯然受到插入方式的影先設(shè)50名學(xué)生的學(xué)號(hào)為0至49,二叉樹中以學(xué)生學(xué)號(hào)為比較依據(jù)。學(xué)生結(jié)構(gòu)體如下代structStu;typedefstructStu{dechar*name;}*Student;typedefStudentTreeElementType;情況一：每個(gè)學(xué)生插入二叉樹時(shí)，學(xué)號(hào)是隨機(jī)的，這樣，生成的二叉樹比較理想。數(shù)組中儲(chǔ)存的學(xué)生和插入二叉樹中的學(xué)生的順序一樣。查找學(xué)生時(shí)，數(shù)組的查找方法是一個(gè)如在二叉樹中依次插入學(xué)號(hào)為18、24、28、26、44的學(xué)生，那么數(shù)組中的第一到第在這種情況下，顯然是二叉樹的效率高，因?yàn)槎鏄渲胁檎倚枰獣r(shí)間是O(logn)的，而查找時(shí)間是O(n^2)的。下面編寫代碼測(cè)試這種情況。先編寫生成隨機(jī)學(xué)號(hào)數(shù)組的代碼，為了生成隨機(jī)的數(shù)組，可以先聲明一個(gè)50元素的數(shù)組，每個(gè)元素的初始值依次為0到49,然后遍歷數(shù)組，根據(jù)隨機(jī)產(chǎn)生的位置來(lái)交換數(shù)組中的voidgenRandArray(inta[50]){for(inti=0;i<50;i++)a[i]=i;printf("正在生成隨機(jī)數(shù)組...\n");sleep(1);srand((unsignedint)(time(NULL)));for(inti=49;i>=1;i--){intindex=rand()%i;s[i],&a[index]);//隨機(jī)交換位置}}然后用隨機(jī)的學(xué)號(hào)數(shù)組來(lái)生成學(xué)生數(shù)組，然后根據(jù)學(xué)生數(shù)組中學(xué)號(hào)的順序來(lái)生成二叉代碼：voidgenStudentArray(Studentstudents[50],inta[50]){//a為學(xué)號(hào)隨機(jī)數(shù)組char*nameArray[4]={"Tom","Jenny","Alice","Bob"};for(inti=0;i<50;i++){char*name=malloc(6);strcpy(name,nameArray[rand()%4]);students[i]=createStudent(a[i],90+(rand()%10),name);}}其中，學(xué)生的成績(jī)均為90到99分，名字為"Tom","Jenny","Alice","Bob"中的一個(gè)，學(xué)下面是根據(jù)學(xué)生數(shù)組生成二叉樹的方法代碼，該方法返回一棵和數(shù)組一致的樹：TreemakeStudentTree(Studentstudents[50]){Treetree=NULL;for(inti=0;i<50;i++){tree=insertTreeNode(students[i],tree);}tree}查找的方法是進(jìn)行N次的隨機(jī)查找，統(tǒng)計(jì)兩種結(jié)構(gòu)的查找時(shí)間。每次查找的過(guò)程如下，先用隨機(jī)函數(shù)生成五個(gè)隨機(jī)的學(xué)號(hào)，然后用分別用這個(gè)學(xué)號(hào)執(zhí)行N次查找，然后計(jì)算每個(gè)學(xué)號(hào)查找的平均值。其中查找數(shù)組中元素的代碼如下，采取的是遍歷數(shù)組來(lái)查找StudentfindStudentInArray(Studentstudents[50],intid){Studentstudent;for(inti=0;i<50;i++){if(students[i]->id==id){student=students[i];}}eturnstudent}TreePositionfind(TreeElementTypex,SearchTreetree){if(tree==NULL){returnNULL;}if(x->id<tree->element->id){returnfind(x,tree->left);}elseif(x->id>tree->element->id){returnfind(x,tree->right);}else{ntree}}#defineNUM1000000intids;for(inti=0;i<5;i++)ids[i]=rand()%50;doublearrayTimes[5];doubletreeTimes[5];clock_tstart,finish;for(inti=0;i<5;i++){intid=ids[i];start=clock();for(intj=0;j<NUM;j++){findStudentInArray(students,id);}finish=clock();arrayTimes[i]=(double)(finish-start)/CLOCKS_PER_SEC;Studentst=findStudentInArray(students,id);start=clock();for(intk=0;k<NUM;k++){find(st,randTree);}finish=clock();treeTimes[i]=(double)(finish-start)/CLOCKS_PER_SEC;}for(inti=0;i<5;i++){printf("學(xué)號(hào)%d的數(shù)組查找用了%f秒\n",ids[i],arrayTimes[i]);}doublearrTime=average(arrayTimes);printf("平均時(shí)間為%f\n",arrTime);for(inti=0;i<5;i++){printf("學(xué)號(hào)%d的二叉樹查找用了%f秒\n",ids[i],treeTimes[i]);}doubletreeTime=average(treeTimes);printf("平均時(shí)間為%f\n",treeTime);經(jīng)過(guò)幾次的測(cè)試，如下圖，發(fā)現(xiàn)數(shù)組查找的時(shí)間基本為二叉樹查找的一倍，顯然在這種這種情況下，二叉樹的查找效率比數(shù)組快?？梢钥吹?，在這種極端情況下，二叉樹的查找效率十分差，比數(shù)組查找慢一倍多?？梢钥吹?，在這種極端情況下，二叉樹的查找效率十分差，比數(shù)組查找慢一倍多。情況三：情況三：二叉樹元素插入的順序是隨機(jī)的，數(shù)組按學(xué)號(hào)升序儲(chǔ)存學(xué)生，但這次數(shù)組的查找算法不同，考慮到數(shù)組中的下標(biāo)就是學(xué)號(hào)，可以直接通過(guò)學(xué)號(hào)ID映射到數(shù)組下標(biāo)來(lái)查情況二：考慮一種極端的情況，二叉樹按照學(xué)號(hào)的升序或者降序來(lái)插入學(xué)生，為了比較，數(shù)組也是按照升序來(lái)儲(chǔ)存。這樣會(huì)使二叉樹變成一條由左節(jié)點(diǎn)或者右節(jié)點(diǎn)組成的長(zhǎng)鏈。這種情況下，二叉樹中的查找時(shí)間就是O(n^2)，和數(shù)組的遍歷查找時(shí)間處于同一個(gè)數(shù)量級(jí)。但由于二叉樹中的查找是指針操作，比數(shù)組操作慢，故二叉樹效率會(huì)低。以下為測(cè)試代碼，先生成一個(gè)50元素的Student數(shù)組，數(shù)組中元素的學(xué)號(hào)ID從0開intafor(inti=0;i<50;i++)a[i]=i;Studentstudents[50];genStudentArray(students,a);Treetree=makeStudentTree(students);testTime(students,tree);其中testTime()函數(shù)中的代碼為測(cè)試代碼，和上一種情況的代碼一樣，現(xiàn)在只關(guān)注測(cè)試時(shí)間就行了，測(cè)試的時(shí)間如下。