數(shù)據(jù)結(jié)構(gòu)C二叉樹試驗(yàn)報(bào)告

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)C二叉樹試驗(yàn)報(bào)告

北京林業(yè)大學(xué)

12學(xué)年—13學(xué)年第1學(xué)期數(shù)據(jù)結(jié)構(gòu)試驗(yàn)報(bào)告書

專業(yè)：自動(dòng)化班級(jí)：11－1姓名：寧友菊學(xué)號(hào)：111044120試驗(yàn)地點(diǎn)：B2機(jī)房任課教師：孟偉

試驗(yàn)題目：二叉樹的基本操作試驗(yàn)環(huán)境：VisualC++試驗(yàn)?zāi)康模?/p>

1．把握二叉樹的定義；

2．把握二叉樹的基本操作，如建立、前序遍歷、中序遍歷和后序遍歷、結(jié)點(diǎn)個(gè)數(shù)的統(tǒng)計(jì)等；

試驗(yàn)內(nèi)容：

用遞歸的方法實(shí)現(xiàn)以下算法：

1．以二叉鏈表表示二叉樹，建立一棵二叉樹；2．輸出二叉樹的前序遍歷結(jié)果；3．輸出二叉樹的中序遍歷結(jié)果；4．輸出二叉樹的后序遍歷結(jié)果；5．統(tǒng)計(jì)二叉樹的葉結(jié)點(diǎn)個(gè)數(shù)；6．統(tǒng)計(jì)二叉樹的結(jié)點(diǎn)個(gè)數(shù)；

7．計(jì)算二叉樹的深度。

8．交換二叉樹每個(gè)結(jié)點(diǎn)的左孩子和右孩子；

實(shí)現(xiàn)方法、試驗(yàn)結(jié)果及結(jié)論分析等：

（一）實(shí)現(xiàn)方法

1.所用數(shù)據(jù)結(jié)構(gòu)的定義及其相關(guān)說(shuō)明（相關(guān)結(jié)構(gòu)體或類的定義及其含義）

試驗(yàn)采用二叉樹的數(shù)據(jù)結(jié)構(gòu)，以二叉鏈表存儲(chǔ)，主程序中采用switch函數(shù)調(diào)用各個(gè)子程序以實(shí)現(xiàn)各個(gè)功能。0終止程序，輸入錯(cuò)誤時(shí)返回主函數(shù)重新輸入。

2.自定義函數(shù)的名稱及其功能說(shuō)明（1）voidCreateBiTree以二叉鏈表表示二叉樹，建立一棵二叉樹；

（2）voidPreOrderTraverse輸出二叉樹的前序遍歷結(jié)果；

（3）voidInOrderTraverse輸出二叉樹的中序遍歷結(jié)果；（4）voidPostOrderTraverse輸出二叉樹的后序遍歷結(jié)果；（5）intLeafNodeCount統(tǒng)計(jì)二叉樹的葉結(jié)點(diǎn)個(gè)數(shù)；

（6）intNodeCount統(tǒng)計(jì)二叉樹的結(jié)點(diǎn)個(gè)數(shù)；

（7）intDepth計(jì)算二叉樹的深度。

（8）intSwap交換二叉樹每個(gè)結(jié)點(diǎn)的左孩子和右孩子；

3.主要功能算法voidPreOrderTraverse的時(shí)間繁雜度

O（n）=O（n1)O(n2)O(n3)O(n4)O(n5)O(n6)O(n7)xO(n8)O（n1)——voidCreateBiTree函數(shù)算法時(shí)間繁雜度O(n)O(n2)——voidPreOrderTraverse函數(shù)算法時(shí)間繁雜度O(n)O(n3)——voidInOrderTraverse函數(shù)算法時(shí)間繁雜度O(n)O(n4)——voidPostOrderTraverse函數(shù)算法時(shí)間繁雜度O(n)O(n5)——intLeafNodeCount函數(shù)算法時(shí)間繁雜度O(n)O(n6)——intNodeCount函數(shù)算法時(shí)間繁雜度O(n)O(n7)——intDepth函數(shù)算法時(shí)間繁雜度O(n)O(n8)——intSwap函數(shù)算法時(shí)間繁雜度O(n)

4.試驗(yàn)流程圖

（二）試驗(yàn)結(jié)果1、選擇操作一：

2、創(chuàng)立二叉樹

3、前序遍歷結(jié)果

4、中序遍歷結(jié)果

5、后序遍歷結(jié)果

6、總結(jié)點(diǎn)數(shù)

7、葉節(jié)點(diǎn)數(shù)

8、二叉樹深度

9、對(duì)換左右孩子

10、退出

11、輸入錯(cuò)誤檢測(cè)

（三）結(jié)論分析

1.問(wèn)題與解決方法在編寫程序時(shí)，遇到了一個(gè)程序保存后編譯正確卻運(yùn)行不了，之后請(qǐng)教了我們班的同學(xué)，才知道是第一個(gè)函數(shù)出了問(wèn)題，改了之后就好了。2.收獲和體會(huì)

做程序編寫時(shí)，必需要細(xì)心，有時(shí)候問(wèn)題出現(xiàn)了，可能會(huì)一直查不出來(lái)。自己也不簡(jiǎn)單發(fā)現(xiàn)。在編寫這個(gè)程序時(shí)，我就出現(xiàn)了