北航計(jì)算機(jī)軟件技術(shù)基礎(chǔ)實(shí)驗(yàn)報(bào)告計(jì)軟實(shí)驗(yàn)報(bào)告2——二叉樹

1、實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱 二叉樹 班 級(jí) 學(xué) 號(hào) 姓 名 成 績 實(shí)驗(yàn)概述： 【實(shí)驗(yàn)?zāi)康募耙蟆?1. 實(shí)驗(yàn)?zāi)康恼莆斩鏄涞拇鎯?chǔ)結(jié)構(gòu)2. 實(shí)驗(yàn)內(nèi)容1對(duì)給定二叉樹用鏈?zhǔn)芥準(zhǔn)酱鎯?chǔ)結(jié)構(gòu)；利用隊(duì)列與棧對(duì)二叉樹進(jìn)行運(yùn)算。2按層次輸出所有結(jié)點(diǎn)。3輸出所有葉子結(jié)點(diǎn)。4將所有左右子樹值交換。3. 實(shí)驗(yàn)步驟和要求1分別編制實(shí)驗(yàn)內(nèi)容中題2、3、4的三個(gè)子程序。2以上圖所示的二叉樹為例編制主程序，實(shí)現(xiàn)下述功能，并運(yùn)行這個(gè)程序。（1）輸入二叉樹用鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)；（2）調(diào)用題2的子程序，并輸出結(jié)果；（3）調(diào)用題3的子程序，并輸出結(jié)果；（4）調(diào)用題4的子程序，并輸出結(jié)果；3自行設(shè)計(jì)一棵二叉樹，重復(fù)步驟2。4整理程序清單與所有結(jié)果，

2、并寫出實(shí)驗(yàn)報(bào)告。4.實(shí)驗(yàn)原理（1）二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 二叉樹的每一個(gè)結(jié)點(diǎn)i有三個(gè)域：值域V（i），左鏈域L（i），右鏈域R（i）。我們分別用三個(gè)一維數(shù)組表示它們，并用頭指針HBT指向二叉樹的根結(jié)點(diǎn)。具體存儲(chǔ)方案由讀者自行考慮。（2）按層次輸出所有結(jié)點(diǎn)為了達(dá)到按層次掃描結(jié)點(diǎn)的目的，需要設(shè)置一個(gè)容量足夠大的循環(huán)隊(duì)列（可以用一個(gè)首尾相接的一維數(shù)組模擬）。初始時(shí)，將根結(jié)點(diǎn)序號(hào)入隊(duì)。然后每次從隊(duì)列中退出一個(gè)結(jié)點(diǎn)序號(hào)，將此結(jié)點(diǎn)的值及左右鏈指針輸出，且依次將此結(jié)點(diǎn)的左右鏈指針入隊(duì)。這個(gè)過程一直進(jìn)行到隊(duì)列空為止。設(shè)循環(huán)隊(duì)列數(shù)組為cq（1：m），其頭尾指針分別為front與rear，則按層次輸出所有結(jié)點(diǎn)的算法

3、如下：IF HBT = 0 THEN RETURN “ THIS TREE IS EMPTY”Front ßm, rearß mADD ( cq, HBT, front, rear )WHILE front rear DODEL ( cq , i, front ,rear )OUTPUT ( L( i ) , V( i ) ,R ( i )IF L( i )0 THEN ADD (cq , L( i ), front, rear)IF R( i )0 THEN ADD (cq , R( i ), front, rear)RETURN在這個(gè)算法中的ADD和DEL分別為入隊(duì)和退

4、隊(duì)運(yùn)算的兩個(gè)過程,其算法(不考慮溢出情況)如下：ADD （ cq，i，front，rear） rearrear + 1 IF rear = m + 1 THEN rear 1 cq （rear） iRETURNDEL (cq, i, front, rear ) front front + 1 IF front = m+ 1 THEN font1 icq (front )RETURN（3）輸出所有葉子結(jié)點(diǎn) 葉子結(jié)點(diǎn)的左右指針域均為零。因此，為了輸出所有葉子結(jié)點(diǎn)，需要設(shè)置一個(gè)容量足夠大的棧S（ 可以用一個(gè)一維數(shù)組模擬它，棧底在數(shù)組的第一個(gè)元素處）。具體過程是：從根結(jié)點(diǎn)開始掃描二叉樹，如果掃描的當(dāng)前

5、結(jié)點(diǎn)的左右均為零，則輸出次葉子結(jié)點(diǎn)；否則將非零的右指針和左指針值推入堆棧。然后從棧中退出一個(gè)結(jié)點(diǎn)序號(hào)重新進(jìn)行這個(gè)過程，直至棧空為止。其算法如下： IF HBT = 0 THEN RETURN “THIS TREE IS EMTPY ” top 0 PUSH （ S，HBT，top） WHILE top 0 DOPOP（S，i，top）IF （L（i）=0） and （R（i）=0）THEN OUTPUT V（i）ELSE IF R（i）0 THEN PUSH （S，R（i），top） IF L（i）0 THEN PUSH （S，L（i），top） RETURN其中PUSH 和POP分別為入棧和

6、退棧的過程，其算法由讀者自行考慮。（4）將所有左右子樹值交換這個(gè)問題的處理和輸出所有葉子結(jié)點(diǎn)的問題很類似，只要將非葉子結(jié)點(diǎn)的左右指針交換即可，其算法如下： IF HBT = 0 THEN RETURN “THIS TREE IS EMPTY”top 0PUSH （S，HBT，top）WHILE top0 DO POP（S，i，top）IF （L（i）0）or （R（i）0） THEN L（i）R（i）IF L（i）0 THEN PUSH （S，L（i），top）IF R（i）0 THEN PUSH （S，R（i），top） RETURN 【實(shí)驗(yàn)環(huán)境】（使用的軟硬件） 處理器 英特爾 Core

7、i5-4200M 2.50GHz 雙核 內(nèi)存 4 GB ( 記憶科技 DDR3L 1600MHz )操作系統(tǒng) Windows 10 專業(yè)版 64位 ( DirectX 12 )編譯環(huán)境 Dev-C+ 5.6.1編譯語言 C 實(shí)驗(yàn)內(nèi)容：【實(shí)驗(yàn)方案設(shè)計(jì)】1. 利用一個(gè)一維數(shù)組data來存放數(shù)據(jù)，用兩個(gè)一維數(shù)組leftChild和rightChild來模擬二叉樹的左右鏈域。創(chuàng)建鏈表的方法為左結(jié)點(diǎn)地址為2*i+1，右結(jié)點(diǎn)地址為2*i+2。2.用隊(duì)列結(jié)構(gòu)來實(shí)現(xiàn)按層次輸出各結(jié)點(diǎn)。先創(chuàng)建一個(gè)包含數(shù)據(jù)區(qū)域、頭指針、尾指針。然后將根結(jié)點(diǎn)加入隊(duì)列。每次先彈出隊(duì)頭元素，判斷左右子樹是否為空，如果不為空則加入隊(duì)列，直

8、到頭尾指針重合。3.用棧結(jié)構(gòu)來實(shí)現(xiàn)查找并輸出葉子結(jié)點(diǎn)。先創(chuàng)建一個(gè)包含數(shù)據(jù)區(qū)域、頂部指針的棧，將根結(jié)點(diǎn)入棧。每次彈出棧頂元素，并判斷左右子樹的值。如果頭元素中存放的結(jié)點(diǎn)的左/右子樹不為空,則入棧，直到棧頂指針為空。4. 用棧結(jié)構(gòu)來實(shí)現(xiàn)查找并交換子樹的值。先創(chuàng)建一個(gè)包含數(shù)據(jù)區(qū)域、頂部指針的棧，將根結(jié)點(diǎn)入棧。每次彈出棧頂元素，并交換棧頂元素指向的結(jié)點(diǎn)的左右子樹指針。如果頭元素中存放的結(jié)點(diǎn)的左/右子樹不為空,則入棧，直到棧頂指針為空。5.整理實(shí)驗(yàn)結(jié)果，寫出實(shí)驗(yàn)報(bào)告【實(shí)驗(yàn)過程】（實(shí)驗(yàn)步驟、記錄、數(shù)據(jù)、分析）實(shí)驗(yàn)一：源代碼：/*實(shí)驗(yàn)內(nèi)容:1:對(duì)給定二叉樹用鏈?zhǔn)芥準(zhǔn)酱鎯?chǔ)結(jié)構(gòu),利用隊(duì)列與棧對(duì)二叉樹進(jìn)行運(yùn)算。2

9、:按層次輸出所有結(jié)點(diǎn)。3:輸出所有葉子結(jié)點(diǎn)。4:將所有左右子樹值交換。*/#include<stdio.h>#include<stdlib.h>#define MAXSIZE 31/定義二叉樹結(jié)構(gòu)體,用一維數(shù)組模擬數(shù)據(jù)域,用兩個(gè)一維數(shù)組模擬左、右鏈域typedef struct BinaryTreeint dataMAXSIZE;int leftChildMAXSIZE;int rightChildMAXSIZE;int head;BTree;int main()/聲明及調(diào)用相關(guān)函數(shù)struct BinaryTree initBinaryTree(struct Bina

10、ryTree);struct BinaryTree createBinaryTree(struct BinaryTree);void levelOrder(struct BinaryTree);void leafNode(struct BinaryTree);void exchangeBranch(struct BinaryTree);printf("Exercise 1n");BTree bt;bt = initBinaryTree(bt);bt = createBinaryTree(bt);printf("A binary tree has been crea

11、ted!nnn");printf("Exercise 2n");levelOrder(bt);printf("Exercise 3n");leafNode(bt);printf("Exercise 4n");exchangeBranch(bt);return 0;/實(shí)驗(yàn)1:初始化二叉樹struct BinaryTree initBinaryTree(struct BinaryTree bt)int i;/數(shù)據(jù)域認(rèn)為0為空,左右鏈域認(rèn)為-1為空for (i = 0; i<MAXSIZE; i+)bt.datai = 0;

12、bt.leftChildi = -1;bt.rightChildi = -1;bt.head = -1;return bt;/創(chuàng)建含有數(shù)據(jù)的二叉樹struct BinaryTree createBinaryTree(struct BinaryTree bt)int i;printf("Please enter all nodes:n");/將數(shù)據(jù)放入數(shù)據(jù)域for (i = 0; i<MAXSIZE; i+)scanf("%d", &bt.datai);/形成鏈?zhǔn)酱鎯?chǔ)for (i = 0; i < (MAXSIZE - 1) / 2;

13、i+)if (bt.data2 * i + 1 != 0)bt.leftChildi = 2 * i + 1;if (bt.data2 * i + 2 != 0)bt.rightChildi = 2 * i + 2;bt.head = 0;return bt;/實(shí)驗(yàn)2:按層次輸出各節(jié)點(diǎn)void levelOrder(struct BinaryTree bt)/創(chuàng)建一個(gè)空隊(duì)列,包含存放二叉樹結(jié)點(diǎn)地址的一維數(shù)組和頭尾指針int queueMAXSIZE;int front = -1, rear = -1, i = bt.head;int addQueue(intMAXSIZE, int, int)

14、;int delQueue(int);/判定二叉樹是否為空if (i = -1)printf("This tree is empty!Please create one!");/根結(jié)點(diǎn)入隊(duì)rear = addQueue(queue, i, rear);printf("All existed nodes are as follows:n");/當(dāng)隊(duì)列不為空時(shí)(隊(duì)列不滿的前提下)while (front != rear)/頭元素出隊(duì),并將其中地址值賦給ifront = delQueue(front);i = queuefront;printf("%

15、d ", bt.datai);/如果頭元素中存放的結(jié)點(diǎn)的左/右子樹不為空,則入隊(duì)if (bt.leftChildi != -1)rear = addQueue(queue, bt.leftChildi, rear);if (bt.rightChildi != -1)rear = addQueue(queue, bt.rightChildi, rear);printf("nnn");/元素入隊(duì)int addQueue(int queueMAXSIZE, int i, int rear)rear+;/循環(huán)隊(duì)列指針處理方法if (rear = MAXSIZE) rear

16、 = 0;queuerear = i;return rear;/元素出隊(duì)int delQueue(int front)front+;/循環(huán)隊(duì)列指針處理方法if (front = MAXSIZE) front = 0;return front;/實(shí)驗(yàn)3:查找所有葉子結(jié)點(diǎn)void leafNode(struct BinaryTree bt)/新建一個(gè)空棧,包含存放二叉樹結(jié)點(diǎn)地址的一維數(shù)組和棧頂指針int stackMAXSIZE;int top = -1, i = bt.head;int pushStack(struct BinaryTree, intMAXSIZE, int, int);int

17、popStack(int);/判定二叉樹是否為空if (i = -1)printf("This tree is empty!Please create one!");/根結(jié)點(diǎn)入棧top = pushStack(bt, stack, top, i);printf("All leaf nodes are as follows:n");while (top != -1)/棧頂元素出棧top = popStack(top);/取出存放的地址值i = stacktop + 1;/判斷是否為葉子結(jié)點(diǎn)if (bt.leftChildi = -1 &&

18、bt.rightChildi = -1)printf("%d ", bt.datai);/如果頭元素中存放的結(jié)點(diǎn)的左/右子樹不為空,則入棧elseif (bt.rightChildi != -1)top = pushStack(bt, stack, top, bt.rightChildi);if (bt.leftChildi != -1)top = pushStack(bt, stack, top, bt.leftChildi);printf("nnn");/入棧操作int pushStack(struct BinaryTree bt, int stac

19、kMAXSIZE, int top, int i)top+;stacktop = i;return top;/出棧操作int popStack(int top)top-;return top;/實(shí)驗(yàn)4:交換左右子樹的值void exchangeBranch(struct BinaryTree bt)/新建一個(gè)空棧,包含存放二叉樹結(jié)點(diǎn)地址的一維數(shù)組和棧頂指針int stackMAXSIZE;int top = -1, i = bt.head, temp;/判定二叉樹是否為空if (i = -1)printf("This tree is empty!Please create one!&

20、quot;);/根結(jié)點(diǎn)入棧top = pushStack(bt, stack, top, i);printf("All branches have been changed!n");printf("The results are as follows:n");while (top != -1)/棧頂元素出棧top = popStack(top);/取出存放的地址值i = stacktop + 1;/判斷存放的結(jié)點(diǎn)的左右子樹是否均不為空,是則入棧if (bt.leftChildi != -1 && bt.rightChildi != -1)

21、top = pushStack(bt, stack, top, bt.rightChildi);top = pushStack(bt, stack, top, bt.leftChildi);/將所有非葉子結(jié)點(diǎn)的左右子樹指針交換temp = bt.leftChildi;bt.leftChildi = bt.rightChildi;bt.rightChildi = temp;/層次遍歷輸出交換后的二叉樹levelOrder(bt);運(yùn)行結(jié)果：（從鍵盤輸入 15 98 6 20 10 45 0 30 40 0 0 0 60 0 0 0 0 0 0 0 0 0 0 0 0 70 0 0 0 0 0）實(shí)驗(yàn)二：自行設(shè)計(jì)的二叉樹如下運(yùn)行結(jié)果：（從鍵盤輸入 24 30 6 5 17 63 4 0 26 1 0 0 0 31 10 0 0 16 27 0 0 0 0 0 0 0 0 50 0 13 9）【結(jié)論】（結(jié)果）1.實(shí)驗(yàn)1中利用一個(gè)一維數(shù)組data來存放數(shù)據(jù)，用兩個(gè)一維數(shù)組leftChild和rightChild來模擬二叉樹的左右鏈域。經(jīng)查閱資料后發(fā)現(xiàn)實(shí)際上創(chuàng)建二叉樹結(jié)構(gòu)多用指針形成鏈表的形式，用指針的好處在于使用靈活，不必事先指定大小2.實(shí)驗(yàn)2用隊(duì)列結(jié)構(gòu)來實(shí)現(xiàn)按