1、最新資料推薦實(shí) 驗(yàn) 報(bào) 告課程名稱數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題目名稱二叉樹的實(shí)現(xiàn)學(xué)生學(xué)院應(yīng)用數(shù)學(xué)學(xué)院專業(yè)班級(jí)14信安 1 班學(xué)號(hào)3114008224學(xué)生姓名阮志敏指導(dǎo)教師劉志煌2016 年 12 月9 日最新資料推薦二叉排序樹的實(shí)現(xiàn)一、內(nèi)容和要求。1) 編程實(shí)現(xiàn)二叉排序樹，包括生成、插入、刪除；2) 對(duì)二叉排序樹進(jìn)行先根、中根和后根非遞歸遍歷；3) 每次對(duì)樹的修改操作和遍歷操作的顯示結(jié)果都需要在屏幕上用樹的形狀表示出來。4) 分別用二叉排序樹和數(shù)組去存儲(chǔ)一個(gè)班（ 50 人以上）的成員信息（至少包括學(xué)號(hào)、姓名、成績(jī) 3 項(xiàng)），對(duì)比查找效率，并說明在什么情況下二叉排序樹效率高，為什么？5) 格式按照作業(yè)的要

2、求，對(duì)數(shù)據(jù)測(cè)試，分析，總結(jié)和改進(jìn)的工作要做詳細(xì)一點(diǎn)。二、解決方案和關(guān)鍵代碼1. 二叉排序樹的實(shí)現(xiàn)。1) 首先定義二叉樹的結(jié)構(gòu)體，代碼如下：struct TreeNode;typedef struct TreeNode *TreePosition;typedef struct TreeNode *SearchTree;typedef struct TreeNode *Tree;typedef int TreeElementType;struct TreeNode / 二叉樹TreeElementType element;/ 節(jié)點(diǎn)中的元素SearchTree left;/ 左兒子SearchTre

3、e right;/ 右兒子int leght;/ 節(jié)點(diǎn)的深度，用于打印int position;/ 節(jié)點(diǎn)的位置，用于打印;2) 實(shí)現(xiàn)插入和生成二叉樹節(jié)點(diǎn)的方法。在這里用到了遞歸插入的方法。SearchTree insertTreeNode(TreeElementType x,SearchTree tree) if(tree = NULL) tree = makeTree(x,NULL,NULL);/插入在該處else if(x element) tree-left = insertTreeNode(x,tree-left);else if(x tree-element) tree-right

4、= insertTreeNode(x,tree-right);/ 如果相等，什么也不做return tree;最新資料推薦當(dāng) tree = NULL 時(shí)，就是遞歸終止的條件，也是插入該節(jié)點(diǎn)的地方，在這里，用方法創(chuàng)建一個(gè)節(jié)點(diǎn)，其代碼如下：makeTree()static SearchTree makeTree(TreeElementType x,SearchTree left,SearchTree right) SearchTree node = (SearchTree)malloc(sizeof(struct TreeNode);if(node = NULL)printf(make TreeN

5、ode fail!n);else node-element = x;node-left = left;node-right = right;return node;3)實(shí)現(xiàn)二叉樹節(jié)點(diǎn)刪除的方法。刪除節(jié)點(diǎn)時(shí)有3 種情況：情況一：被刪除的節(jié)點(diǎn)同時(shí)含有左兒子和右兒子。在這種情況下， 必須找出一個(gè)合適的節(jié)點(diǎn)來替代被刪除的節(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)替代它。情況

6、三：被刪除節(jié)點(diǎn)沒有子節(jié)點(diǎn)。此時(shí)，直接刪除它。具體代碼如下,同樣使用遞歸刪除的方法：SearchTree deleteTreeNode(TreeElementType x,SearchTree tree) TreePosition tmpNode;if(tree = NULL)/ 到葉節(jié)點(diǎn)了，還沒找到可以刪除的printf(not found!n);else if(x element) tree-left = deleteTreeNode(x,tree-left);else if(x tree-element) tree-right = deleteTreeNode(x,tree-right);

7、else if(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)，或者沒有子節(jié)點(diǎn)tmpNode = tree;if(tree-left = NULL) /0個(gè)子節(jié)點(diǎn)也包含在內(nèi)最新資

8、料推薦tree = tree-right;else if(tree-right = NULL) tree = tree-left;free(tmpNode);return tree;其中的findMin() 方法為找出以某個(gè)節(jié)點(diǎn)為根的樹的最小節(jié)點(diǎn)，在這里可以用循環(huán)遍歷tree-left 來實(shí)現(xiàn)，也可以用遞歸來實(shí)現(xiàn)，代碼如下：TreePosition findMin(SearchTree tree) / 遞歸實(shí)現(xiàn)if(tree = NULL)return NULL;if(tree-left != NULL) return findMin(tree-left);else return tree;2

9、. 對(duì)二叉排序樹進(jìn)行先根、中根和后根非遞歸遍歷1) 先根遍歷先根遍歷先訪問根，再訪問左兒子，接著訪問右兒子。上圖中的樹，如果用先根遍歷，順序則是A-B-E-F-C要實(shí)現(xiàn)非遞歸遍歷，必須使用循環(huán)來進(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í)取出打印，如果沒有左右節(jié)點(diǎn)， 則直接進(jìn)入下次循環(huán)。在這里，有兩種數(shù)據(jù)結(jié)構(gòu)可用于儲(chǔ)存待打印節(jié)點(diǎn)，一個(gè)是隊(duì)列，一個(gè)是棧。先嘗試隊(duì)列， 隊(duì)列的特性是先進(jìn)先

10、出，我們希望在訪問完當(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ì)先訪問A 節(jié)點(diǎn)，然后儲(chǔ)存B 到隊(duì)列，再儲(chǔ)存 C到隊(duì)列，此時(shí)，隊(duì)列中的元素為BC。下次循環(huán)時(shí)，會(huì)把B 出列，訪問完B 后，再儲(chǔ)存 E 和F，此時(shí)，隊(duì)列中的元素為CEF。下次循環(huán)時(shí)，會(huì)把C 出列進(jìn)行訪問。顯然，這種訪問順序A-B-C不是正確的訪問順序，正確的應(yīng)該是A-B-E，因此隊(duì)列并不能滿足要求。接下來用棧進(jìn)行儲(chǔ)存嘗試。 當(dāng)使用棧時(shí)，由于棧的特性為后進(jìn)先出， 故在第一次循環(huán)時(shí)，先訪問 A，然后把 C 入棧，再把 B 入棧，

11、這時(shí)棧中的元素為CB。下次循環(huán)時(shí)，把 B 出棧進(jìn)行訪問，然后把 F 入棧，再把 E 入棧。這時(shí)，訪問順序?yàn)锳-B-E-F-C，因此，我們可以用棧來作為循環(huán)遍歷時(shí)的儲(chǔ)存數(shù)據(jù)結(jié)構(gòu)。此時(shí)，每輪循環(huán)的步驟就很清晰了： 如果棧非空，出棧一個(gè)元素作為當(dāng)前節(jié)點(diǎn)， 先訪問或者打印當(dāng)前節(jié)點(diǎn)，接著，如果當(dāng)前節(jié)點(diǎn)有左兒子或者右兒子，則先把右兒子入棧， 再把左兒子入棧然后進(jìn)入下次循環(huán)。 如果當(dāng)前節(jié)點(diǎn)沒有兒子， 則直接進(jìn)入下次循環(huán)。具體代碼如下：void preorderTraversal(Tree tree) Stack stack = createStack(10);push(tree,stack);while(!

12、isStackEmpty(stack) TreePosition node = pop(stack);printf(%d ,node-element);if(node-right != NULL) push(node-right,stack);if(node-left != NULL) push(node-left,stack);2) 中根遍歷中根遍歷中，先訪問當(dāng)前節(jié)點(diǎn)的左兒子，再訪問當(dāng)前節(jié)點(diǎn)，最后訪問右兒子。最新資料推薦上圖的樹中，中根遍歷的順序?yàn)镈-B-F-E-A-C。在中根遍歷過程中，要訪問當(dāng)前節(jié)點(diǎn)，首先要訪問當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)，而如果左節(jié)點(diǎn)又有左節(jié)點(diǎn)，則會(huì)一直向左下去。 比如要訪問A，則

13、首先要訪問B，要訪問 B 則要先訪問E。因此，在循環(huán)遍歷開始前，可以先將A 以及其左邊的節(jié)點(diǎn)全部壓入棧中，此時(shí)，棧中的元素為ABD，然后開始循環(huán)遍歷。在循環(huán)中，先從棧中彈出一個(gè)節(jié)點(diǎn)，訪問該節(jié)點(diǎn)，然后判斷該節(jié)點(diǎn)是否有右節(jié)點(diǎn)，如果有右節(jié)點(diǎn)，則把其右子樹中右節(jié)點(diǎn)開始的所有左節(jié)點(diǎn)壓入棧中，這樣，下一次循環(huán)就能訪問到右節(jié)點(diǎn)所在子樹的最左邊節(jié)點(diǎn)了。 因?yàn)橐L問右節(jié)點(diǎn)，必須先訪問右節(jié)點(diǎn)的左子樹中的最左邊的元素。比如上圖的樹中，在彈出B 的時(shí)候，訪問B，然后 B 有右節(jié)點(diǎn)E，因此，把EF 都入棧，然后開始下一次循環(huán)。下一次循環(huán)開始時(shí)，就能取出F 進(jìn)行訪問了。具體代碼如下：/* 中序遍歷*/void inord

14、erTraversal(Tree tree) Stack stack = createStack(30);if(tree = NULL) printf(the tree is NULL,cant traversaln);else pushLeftToStack(tree,stack);while(!isStackEmpty(stack) TreePosition node = pop(stack);printf(%d ,node-element);if(node-right)pushLeftToStack(node-right,stack);printf(n);最新資料推薦其中的 pushLe

15、ftToStack()方法從該節(jié)點(diǎn)開始，一直向左，把左節(jié)點(diǎn)全部壓入棧中，代碼如下：static void pushLeftToStack(Tree tree,Stack stack) while(tree) push(tree,stack);tree = tree-left;3) 后根非遞歸遍歷后根遍歷中，先訪問當(dāng)前節(jié)點(diǎn)的左兒子，再訪問右兒子， 最后才訪問當(dāng)前節(jié)點(diǎn)。在上圖的樹中， 訪問的順序?yàn)?D-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)

16、沒有右兒子，那么就可以直接訪問該節(jié)點(diǎn)了， 但如果該節(jié)點(diǎn)有右兒子，那么就還不能訪問該節(jié)點(diǎn)， 必須先訪問完該節(jié)點(diǎn)的右子樹。如上圖中，先彈出 D，由于 D 沒有右兒子，則可以直接訪問，進(jìn)入下一次循環(huán)。但彈出B 時(shí)，由于 B 有右兒子 E，那么此時(shí)還不能訪問B，因此要將 B 重新壓回棧中，然后再把EF入棧。這里的問題在于，當(dāng)訪問完FE后，又回把 B 重新出棧。如果按照剛才的做法，由于B 還是有右兒子， 這樣，B 又會(huì)重新壓入棧， 同時(shí) EF也會(huì)再次入棧， 這樣就會(huì)造成無限循環(huán)。一種解決這種無限循環(huán)的方式是：訪問完D 后，出棧 B，由于 B 有右兒子，為了避免后面的無限循環(huán)，可以在把B 重新入棧時(shí)，先用

17、臨時(shí)變量T 保存 B 的右兒子，然后設(shè)置 B 的右兒子為空，然后再把B 入棧，接著再把臨時(shí)變量T 作為原 B 的右兒子入棧，這樣，再次彈出B時(shí)，由于 B 的兒子為空了，所以這次會(huì)直接訪問B，從而避免了無限循環(huán)。但是這樣破壞了樹的結(jié)構(gòu)，顯然是不好的。因此要尋找另外的辦法來避免無限循環(huán)，現(xiàn)在的重點(diǎn)是標(biāo)識(shí)出B最新資料推薦已經(jīng)被重新壓入過一次棧了，也就是說 B 被壓了兩次棧了。 如果可以標(biāo)識(shí)出來， 則在訪問完FE 時(shí)， B 重新出棧時(shí)，由于B 已經(jīng)兩次入棧了，故可以直接訪問B 了。在這里采取的做法是：創(chuàng)建多一個(gè)棧，設(shè)其為T，第一次彈出B 時(shí)，由于 B 有右兒子。則把B 壓回到原本的棧中，同時(shí)也把 B

18、壓入棧 T 中。這樣， 每次彈出一個(gè)節(jié)點(diǎn)時(shí)， 如果這個(gè)節(jié)點(diǎn)有右兒子則先和棧T 中的最頂元素做下對(duì)比，如果和棧T 中的最頂元素相同，則證明這個(gè)有右兒子的節(jié)點(diǎn)在之前已經(jīng)被壓入多一次棧了。因此，可以直接訪問這個(gè)節(jié)點(diǎn)了。 在上面例子中， 訪問完 FE后，再次把 B 出棧，此時(shí) B 有右兒子，故和棧T 中的最頂元素做比較，發(fā)現(xiàn)棧T 中的最頂元素也是 B，因此證明 B 已經(jīng)被壓入過兩次了，故可以直接訪問 B 了，訪問完 B 后再把棧 T 中的B 出棧。具體代碼如下：/* 后序遍歷*/void postorderTraversal(Tree tree) Stack stack = createStack(3

19、0);Stack tmp = createStack(30);/ 保存入棧兩次的，有右子樹的節(jié)點(diǎn)pushLeftToStack(tree,stack);while(!isStackEmpty(stack) TreePosition node = 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í)

20、棧中pushLeftToStack(node-right,stack);else / 如果該節(jié)點(diǎn)兩次入棧了，就把它訪問并輸出pop(tmp);printf(%d ,node-element);printf(n);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)的

21、位置了。從最高的層開始，設(shè)置第1 層所有節(jié)點(diǎn)的深度為0,第 2 層所有節(jié)點(diǎn)的深度為1,依此類推。設(shè)某個(gè)節(jié)點(diǎn)是其父節(jié)點(diǎn)的左兒子，它的位置為pc, 深度為 l,父節(jié)點(diǎn)位置為pp, 根節(jié)點(diǎn)的位置為R ，則 pc =pp - R/2l 。如上面的根節(jié)點(diǎn)的左兒子的位置為8 - 21 = 4 。同理， 根的右兒子的位置為8 +21 = 12 。第 3 層中的第一個(gè)節(jié)點(diǎn)的位置為4 - 8/22 = 4 - 2 = 2。這樣，只要知道根節(jié)點(diǎn)的位置，可以知道整棵樹的位置了。而根節(jié)點(diǎn)的位置R = 2h, 其中 h 為樹的高度。下面來看具體代碼：先是獲取樹中每個(gè)節(jié)點(diǎn)的深度和整棵樹的高度的代碼，在這里，用層序遍歷樹來

22、進(jìn)行深度設(shè)置：static int treeHeight = -1;static void getLegthOfTree(Tree tree) Queue parentQueue = CreateQueue(TRAVERSAL_QUEUE_SIZE);/保存父節(jié)點(diǎn)的隊(duì)列QueuechildQueue= CreateQueue(TRAVERSAL_QUEUE_SIZE);/保存子節(jié)點(diǎn)最新資料推薦的隊(duì)列int leght = 0;/當(dāng)前的深度treeHeight = -1;Enqueue(tree, parentQueue);while(!IsQueueEmpty(parentQueue) whi

23、le(!IsQueueEmpty(parentQueue)TreePosition node = 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ì)列Queue tempQueue = parentQueue;parentQueue = childQueue;childQueue = tempQueu

24、e;leght+;/ 每遍歷一層，深度加一treeHeight+;/樹高度加一最新資料推薦DisposeQueue(parentQueue);DisposeQueue(childQueue);接下來是獲取樹中每個(gè)節(jié)點(diǎn)的位置的代碼，這里同樣使用層序遍歷來獲取每個(gè)節(jié)點(diǎn)的位置：static void getPositionOfTree(Tree tree) Queue parentQueue = CreateQueue(TRAVERSAL_QUEUE_SIZE);Queue childQueue = CreateQueue(TRAVERSAL_QUEUE_SIZE);Enqueue(tree, pa

25、rentQueue);tree-position = 1 position;while(!IsQueueEmpty(parentQueue) while(!IsQueueEmpty(parentQueue) TreePosition node = FrontAndDequeue(parentQueue);if(node-left != NULL)int leftStep = topPosition node-left-leght;最新資料推薦node-left-position = node-position - leftStep;Enqueue(node-left, childQueue);

26、if(node-right != NULL)int rightStep = topPosition node-right-leght;node-right-position = node-position + rightStep;Enqueue(node-right, childQueue);Queue tempQueue = parentQueue;parentQueue = childQueue;childQueue = tempQueue;DisposeQueue(parentQueue);DisposeQueue(childQueue);接下來是打印樹的代碼：最新資料推薦void pr

27、intTree(Tree tree) getLegthOfTree(tree);getPositionOfTree(tree);printf(n);Queue parentQueue = CreateQueue(TRAVERSAL_QUEUE_SIZE);Queue childQueue = CreateQueue(TRAVERSAL_QUEUE_SIZE);int prePosition = 0;Enqueue(tree, parentQueue);while(!IsQueueEmpty(parentQueue)while(!IsQueueEmpty(parentQueue) TreePos

28、ition node = FrontAndDequeue(parentQueue);int spaceNum = 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)

29、;Queue tempQueue = parentQueue;parentQueue = childQueue;childQueue = tempQueue;DisposeQueue(parentQueue);DisposeQueue(childQueue);最新資料推薦4. 對(duì)比存儲(chǔ) 50 個(gè)學(xué)生信息的二叉樹和數(shù)組的查找效率。二叉樹和數(shù)組的查找效率是看情況而言的，二叉樹的查找效率顯然受到插入方式的影響?？梢苑侄喾N情況。先設(shè) 50 名學(xué)生的學(xué)號(hào)為 0 至 49,二叉樹中以學(xué)生學(xué)號(hào)為比較依據(jù)。 學(xué)生結(jié)構(gòu)體如下代碼所示：struct Stu;typedef struct Stuint id;int

30、 score;char *name; *Student;typedef Student TreeElementType;情況一： 每個(gè)學(xué)生插入二叉樹時(shí)，學(xué)號(hào)是隨機(jī)的，這樣，生成的二叉樹比較理想。數(shù)組中儲(chǔ)存的學(xué)生和插入二叉樹中的學(xué)生的順序一樣。查找學(xué)生時(shí)， 數(shù)組的查找方法是一個(gè)個(gè)地遍歷來查找。如在二叉樹中依次插入學(xué)號(hào)為18、 24、28、 26、 44 的學(xué)生，那么數(shù)組中的第一到第五個(gè)元素也為學(xué)號(hào)為18、24、 28、 26、44 的學(xué)生。在這種情況下，顯然是二叉樹的效率高，因?yàn)槎鏄渲胁檎倚枰獣r(shí)間是O(logn)的，而數(shù)組的查找時(shí)間是O(n2) 的。下面編寫代碼測(cè)試這種情況。先編寫生成隨機(jī)學(xué)號(hào)

31、數(shù)組的代碼，為了生成隨機(jī)的數(shù)組，可以先聲明一個(gè)50 元素的數(shù)組，每個(gè)元素的初始值依次為0 到 49,然后遍歷數(shù)組，根據(jù)隨機(jī)產(chǎn)生的位置來交換數(shù)組中的元素位置，代碼如下：void genRandArray(int a50)for(int i = 0; i = 1; i-)int index = rand() % i;swap(&ai, &aindex);/隨機(jī)交換位置printf( 隨機(jī)數(shù)組生成成功！n);然后用隨機(jī)的學(xué)號(hào)數(shù)組來生成學(xué)生數(shù)組，然后根據(jù)學(xué)生數(shù)組中學(xué)號(hào)的順序來生成二叉樹。先是生成學(xué)生數(shù)組的代碼：void genStudentArray(Student students50, int a

32、50)/a為學(xué)號(hào)隨機(jī)數(shù)組char *nameArray4 = Tom, Jenny, Alice,Bob;for(int i = 0; i 50; i+)最新資料推薦char *name = malloc(6);strcpy(name, nameArrayrand() % 4);studentsi = createStudent(ai, 90 + (rand() % 10), name);其中，學(xué)生的成績(jī)均為90 到 99 分，名字為 Tom, Jenny, Alice,Bob 中的一個(gè)， 學(xué)號(hào)為 0 至 49。下面是根據(jù)學(xué)生數(shù)組生成二叉樹的方法代碼，該方法返回一棵和數(shù)組一致的樹：Tree m

33、akeStudentTree(Student students50) Tree tree = NULL;for(int i = 0; i 50; i+)tree = insertTreeNode(studentsi, tree);return tree;查找的方法是進(jìn)行N 次的隨機(jī)查找， 統(tǒng)計(jì)兩種結(jié)構(gòu)的查找時(shí)間。每次查找的過程如下，先用隨機(jī)函數(shù)生成五個(gè)隨機(jī)的學(xué)號(hào)，然后用分別用這個(gè)學(xué)號(hào)執(zhí)行 N 次查找，然后計(jì)算每個(gè)學(xué)號(hào)查找的平均值。其中查找數(shù)組中元素的代碼如下，采取的是遍歷數(shù)組來查找Student findStudentInArray(Student students50, int id)Stu

34、dent student;for(int i = 0; i id = id)student = studentsi;break;return student;查找二叉樹中元素的代碼如下：TreePosition find(TreeElementType x,SearchTree tree) if(tree = NULL)return NULL;if(x-id element-id) return find(x,tree-left);else if(x-id tree-element-id) return find(x,tree-right);else return tree;最新資料推薦下面是

35、測(cè)試一百萬次的代碼：#define NUM 1000000int ids5;for(int i = 0; i 5; i+)idsi = rand() % 50;double arrayTimes5;double treeTimes5;clock_t start, finish;for(int i = 0; i 5; i+)int id = idsi;start = clock();for(int j = 0; j NUM; j+)findStudentInArray(students,id);finish = clock();arrayTimesi = (double)(finish - st

36、art)/CLOCKS_PER_SEC;Student st = findStudentInArray(students, id);start = clock();for(int k = 0; k NUM; k+)find(st, randTree);finish = clock();treeTimesi = (double)(finish - start)/CLOCKS_PER_SEC;for(int i = 0; i 5; i+)printf( 學(xué)號(hào) %d 的數(shù)組查找用了%f 秒 n,idsi, arrayTimesi);double arrTime = average(arrayTime

37、s);printf( 平均時(shí)間為 %fn,arrTime);for(int i = 0; i 5; i+)printf( 學(xué)號(hào) %d 的二叉樹查找用了%f 秒 n,idsi, treeTimesi);double treeTime = average(treeTimes);printf( 平均時(shí)間為 %fn,treeTime);經(jīng)過幾次的測(cè)試， 如下圖， 發(fā)現(xiàn)數(shù)組查找的時(shí)間基本為二叉樹查找的一倍，這種情況下，二叉樹的查找效率比數(shù)組快。顯然在這種最新資料推薦最新資料推薦情況二：考慮一種極端的情況， 二叉樹按照學(xué)號(hào)的升序或者降序來插入學(xué)生，為了比較，數(shù)組也是按照升序來儲(chǔ)存。這樣會(huì)使二叉樹變成一條由

38、左節(jié)點(diǎn)或者右節(jié)點(diǎn)組成的長(zhǎng)鏈。這種情況下， 二叉樹中的查找時(shí)間就是O(n2) ，和數(shù)組的遍歷查找時(shí)間處于同一個(gè)數(shù)量級(jí)。但由于二叉樹中的查找是指針操作，比數(shù)組操作慢，故二叉樹效率會(huì)低。以下為測(cè)試代碼， 先生成一個(gè)50 元素的 Student 數(shù)組，數(shù)組中元素的學(xué)號(hào)ID 從 0 開始，遞增到 49。int a50;for(int i = 0; i 50; i+)ai = i;Student students50;genStudentArray(students, a);Tree tree = makeStudentTree(students);testTime(students, tree);其中

39、testTime() 函數(shù)中的代碼為測(cè)試代碼，和上一種情況的代碼一樣，現(xiàn)在只關(guān)注測(cè)試時(shí)間就行了，測(cè)試的時(shí)間如下?？梢钥吹剑谶@種極端情況下，二叉樹的查找效率十分差，比數(shù)組查找慢一倍多。情況三： 二叉樹元素插入的順序是隨機(jī)的， 數(shù)組按學(xué)號(hào)升序儲(chǔ)存學(xué)生， 但這次數(shù)組的查找算法不同， 考慮到數(shù)組中的下標(biāo)就是學(xué)號(hào)， 可以直接通過學(xué)號(hào) ID 映射到數(shù)組下標(biāo)來查找。如果是這樣，顯然是數(shù)組最快。但這種查找算法不太現(xiàn)實(shí)，因?yàn)楝F(xiàn)實(shí)中的學(xué)號(hào)都是很大的，最新資料推薦需要很大的數(shù)組來儲(chǔ)存。因此，為了更一般，這里用二分查找來在有序的數(shù)組中查找學(xué)生。二分查找的代碼如下：Student binSearchArray(Student students50, int id)int hight = 49;int low = 0;int min;while(low hight)min = (hi