《《大數(shù)據(jù)結(jié)構(gòu)》課程實(shí)驗(yàn)報告材料》由會員分享，可在線閱讀，更多相關(guān)《《大數(shù)據(jù)結(jié)構(gòu)》課程實(shí)驗(yàn)報告材料（39頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、word4 實(shí)驗(yàn)一 基于二叉鏈表的二叉樹的實(shí)現(xiàn)4.1 問題描述基于二叉鏈表和隊(duì)列與其堆棧存儲結(jié)構(gòu)，實(shí)現(xiàn)二叉鏈表的二叉樹的對數(shù)據(jù)進(jìn)展各種必要的操作。4.2 系統(tǒng)設(shè)計1提供20個功能，分別是：1.2.2二叉鏈表的結(jié)構(gòu)試一堆棧和隊(duì)列的形式進(jìn)展儲存的分別是：1.2.3在程序中所定義的數(shù)據(jù)結(jié)構(gòu)有：2.3 系統(tǒng)實(shí)現(xiàn)InitTree功能初始二叉鏈表，傳入的是頭結(jié)點(diǎn)地址。申請一個存儲空間，并用頭結(jié)點(diǎn)中的首結(jié)點(diǎn)指針指向該空間首地址，相應(yīng)的 時間復(fù)雜度為1。具體實(shí)現(xiàn)如下：DestroyTree功能銷毀頭結(jié)點(diǎn)中首結(jié)點(diǎn)址針指向的線性存儲空間，傳入的是頭結(jié)點(diǎn)地址。具體實(shí)現(xiàn)如下：與DestroyBiTree類似但是又有不

2、同，ClearBiTree并不銷毀物理空間，而是修改邏輯關(guān)系值：與DestroyBiTree類似但是又有不同，ClearBiTree并不銷毀物理空間，而是修改邏輯關(guān)系值判空功能，判斷表是否為空表。時間復(fù)雜度為1，因?yàn)橹恍枧袛嘁淮尉涂梢灾朗欠駷榭?。?shí)現(xiàn)如下：求二叉鏈表深度的功能，由于創(chuàng)建過程中已經(jīng)把表長信息包含在頭結(jié)點(diǎn)中，所以直接調(diào)用并顯示即可1.3.7Root(BiTree T)功能獲取二叉鏈表的根節(jié)點(diǎn)的元素，通過遍歷二叉鏈表中的元素，來逐個判斷，時間復(fù)雜度為n。1.3.8Value(BiTree T,TElemType e)功能求指定元素的前一個元素的內(nèi)容，傳入頭結(jié)點(diǎn)值、包含指定元素信息的

3、一個臨時表結(jié)點(diǎn)值、存儲前一個元素的表結(jié)點(diǎn)地址。主要思路是遞歸算法。時間復(fù)雜度為O(n)。具體實(shí)現(xiàn)如下：求指定元素的后一個元素的內(nèi)容，傳入頭結(jié)點(diǎn)值、包含指定元素信息的一個臨時表結(jié)點(diǎn)值、存儲前一個元素的表結(jié)點(diǎn)地址。找到后，把新的數(shù)據(jù)值賦給所找到的節(jié)點(diǎn)。時間復(fù)雜度為O(n)。具體實(shí)現(xiàn)如下：Parent功能找雙親節(jié)點(diǎn)，找到后輸出查找左孩子，利用遞歸的算法，與遍歷的時間復(fù)雜度為一樣O(n)查找右孩子，利用遞歸的算法，與遍歷的時間復(fù)雜度為一樣O(n)查找節(jié)點(diǎn)的左邊的堂兄弟的，找到后輸出該節(jié)點(diǎn)的數(shù)據(jù)查找節(jié)點(diǎn)的右邊的堂兄弟的，找到后輸出該節(jié)點(diǎn)的數(shù)據(jù)函數(shù)在二叉鏈表中插入新的節(jié)點(diǎn)刪除指定編號的數(shù)據(jù)元素，傳入頭結(jié)點(diǎn)

4、地址、編號i、表結(jié)點(diǎn)類型結(jié)構(gòu)體地址來返回被刪除元素內(nèi)容。執(zhí)行前先判斷傳入的編號是否在可尋找X圍內(nèi)。執(zhí)行刪除操作之后，進(jìn)展“移位運(yùn)算。時間復(fù)雜度仍為O(n)。如下：前序遍歷二叉鏈表中的數(shù)據(jù)，采用先遍歷左孩子，再訪問根節(jié)點(diǎn)，后訪問右孩子的思想來實(shí)現(xiàn)前序遍歷的算法的。中序遍歷的函數(shù)，對二叉鏈表的數(shù)據(jù)進(jìn)展訪問，并且利用PreOrderTraverse函數(shù)采用后續(xù)遍歷的思想，利用先序遍歷的函數(shù)進(jìn)展完全遍歷二叉鏈表中的數(shù)據(jù)，并進(jìn)展輸出的定位節(jié)點(diǎn)的函數(shù)，在需要查找二叉鏈表二叉樹的節(jié)點(diǎn)的時候，可以直接調(diào)用該函數(shù)，進(jìn)展處理，相應(yīng)的代碼如下1.3.21FILE * fileOpen功能讀取功能，通過fscanf實(shí)

5、現(xiàn)格式化讀取，同時結(jié)合CreateList函數(shù)實(shí)現(xiàn)順序1.3.22BiTNode * Create(FILE *fp)功能把二叉鏈表二叉樹的數(shù)據(jù)寫入到文件中去效率分析在上面介紹各功能時已經(jīng)提到時間復(fù)雜度的計算了，這里再簡單分析一下。具有同數(shù)量級復(fù)雜度的功能在實(shí)現(xiàn)方法上一般近似。比如InOrderTraverse，PostOrderTraverse，BiTreeDepth，LevelOrderTraverse它們都是基于PreOrderTraverse來設(shè)計的，所以效率都是O(n)；而Root，Value，Assign，Parent，LeftChild，RightChild，LeftSiblin

6、gRightSibling，InsertChild，DeleteChild是基于VisitPoint，平均效率為O(n)； InitTree DestroyBiTree所需信息，所以效率為O(1)；CreateBiTreeClearBiTreeBiTreeEmpty都要對二叉鏈表，平均效率為O(n)。實(shí)驗(yàn)總結(jié)與評價我做了這個實(shí)驗(yàn)發(fā)現(xiàn)自己的編程能力很不好，自己的腦袋中有相應(yīng)的想法和主意，但是因?yàn)樽约旱木幊棠芰懿缓靡簿蛯?shí)現(xiàn)不了自己的想法。 二叉鏈表的二叉樹的時候，實(shí)現(xiàn)二叉鏈表線性的對我來說還可以實(shí)現(xiàn)，因?yàn)榫€性的所用到方法和技術(shù)，在學(xué)習(xí)十字鏈表的時候練習(xí)的比擬少，實(shí)現(xiàn)起來難度是很大。特別是有了教師

7、給的框架以后，我們要做的任務(wù)就是向里面填我們自己寫的函數(shù)，在填寫的過程中，我深深的感受到了，認(rèn)真的重要性，因?yàn)槲以趯懞谜{(diào)試的中發(fā)現(xiàn)了很多，因?yàn)樽约旱牟恍⌒暮驮谇么a的過程中的不認(rèn)真而造成的很不應(yīng)該的錯誤，這些錯誤也給自己在調(diào)試的過程中也造成了很大的麻煩，因?yàn)槭遣徽J(rèn)真而犯的錯誤，因此調(diào)試的過程中也很不好發(fā)現(xiàn)。對我來說，因?yàn)槲业腃語言的功底很不好，運(yùn)用指針和鏈表的能力還沒有能達(dá)到運(yùn)用自如，理解深刻的地步，所以在順序鏈表的鏈表的實(shí)現(xiàn)中，對我來說是一個很大的挑戰(zhàn)，我有很多不會的地方通過自己看書，問室友和上網(wǎng)查詢，一點(diǎn)一點(diǎn)的寫了出來，肯定現(xiàn)在還是會有很多的問題，但是這也是我一直在努力把它做的更好，在調(diào)試

8、的中出現(xiàn)了很多的BUG，自己一個個的慢慢的消除掉了，做出了，現(xiàn)在的程序。 如果問自己的體會，那一定是希望我自己以后多多的動手，把以前C語言的書好好再復(fù)習(xí)一遍，還有就是把現(xiàn)在正在學(xué)習(xí)的數(shù)據(jù)結(jié)構(gòu)的書上各個程序，自己要一個個的敲一遍，練習(xí)一下自己的熟悉程度?？偟膩碚f，我對這次的實(shí)驗(yàn)是很有感觸的。因?yàn)?，這次實(shí)驗(yàn)讓我認(rèn)識到了，自己的編程能力的低下，如果自己再不下一下功夫的話，那么數(shù)據(jù)結(jié)構(gòu)的考試自己就十分的危險了。因此，我要加緊復(fù)習(xí)C語言的知識和數(shù)據(jù)結(jié)構(gòu)學(xué)過的內(nèi)容，爭取自己能在接下來的學(xué)習(xí)中能有些進(jìn)步。附錄：參考書數(shù)據(jù)結(jié)構(gòu)C語言版嚴(yán)蔚敏 吳偉民編著 C語言程序設(shè)計 曹計昌，李開編著實(shí)驗(yàn)心得體會對于這兩次的

9、實(shí)驗(yàn)，我自己的體會是很深刻的，也是記憶深刻的。因?yàn)?，正是因?yàn)檫@兩次的實(shí)驗(yàn)深深地讓我認(rèn)識到了自己的水平是多么的低下，以前，自己還有點(diǎn)夜郎自大的認(rèn)為，自己對所學(xué)的東西，自己掌握的還差不多了呢。但是，經(jīng)過這次的實(shí)驗(yàn)，我真的是清楚的發(fā)現(xiàn)自己對所學(xué)的知識的掌握還差的很多，自己還有很多的功課要補(bǔ)。第一，以前無論是學(xué)習(xí)C語言還是數(shù)據(jù)結(jié)構(gòu)，我的方法是拿著書本看，還有就是拿著練習(xí)本寫一寫，而自己家上機(jī)的實(shí)踐的時間是非常少的，因?yàn)槲腋杏X上機(jī)得到的結(jié)構(gòu)一定會和自己想的和寫的一樣呢，顯然，我是錯誤的，因?yàn)樵谶@次的實(shí)驗(yàn)里我就發(fā)現(xiàn)，即使是書上一模一樣的代碼，在機(jī)子上也是有很大 的可能出錯的，更不用說是自己寫的了，在寫線性

10、表，線性鏈表和二叉鏈表的時候，我出現(xiàn)了用書上的代碼不能用的情況，而且是非常嚴(yán)重的錯誤。有些聲明和指針的問題會出現(xiàn)很大的不同。我的體會是，從現(xiàn)在起，重視上機(jī)的過程，多書上的程序一定要在機(jī)子上跑一下，然后再分析一下，出現(xiàn)這種結(jié)果的原因和整個程序的流程。第二，就是實(shí)驗(yàn)的 時候的規(guī)X的問題，由于，自己寫代碼沒有很好的習(xí)慣和規(guī)如此，于是，在自己寫好的程序出現(xiàn)錯誤后自己不能夠很快的 找到出現(xiàn)錯誤的位置，比如，對全局變量聲明的時候，全局變量的位置問題，在結(jié)構(gòu)和聯(lián)合聲明指針的時候，指針的形式和指針的命名的形式問題，這些錯誤都有在自己的實(shí)驗(yàn)的過程中出現(xiàn)，而且，也給自己帶來了很大的麻煩。我的體會是，以后再寫程序的

11、時候一定遵守一定的規(guī)如此和習(xí)慣，例如關(guān)鍵詞的命名習(xí)慣，指針的使用形式和結(jié)構(gòu)聯(lián)合中的一些形式的問題，應(yīng)該遵循一定的規(guī)如此和習(xí)慣，因?yàn)椋挥羞@樣的自己在寫好的調(diào)試和檢查的過程中才不會走那么多 的彎路，才會把做事的速度提高上去。 最后，就是自己的一些心得體會對這次的實(shí)驗(yàn)。做什么事情都要認(rèn)真對待，無論事情的大小，因?yàn)橹挥羞@樣自己才會養(yǎng)成認(rèn)真做事的習(xí)慣，這次的數(shù)據(jù)結(jié)構(gòu)的實(shí)驗(yàn)讓我深深的意識到了這一點(diǎn)。附錄：實(shí)驗(yàn)三代碼：#include #include #include #include#include #define LIST_INIT_SIZE 100#define LISTINCREMENT 10#

12、define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASTABLE -1#define OVERFLOW -2#define MAX_TREE_SIZE 100typedef int Status;typedef int TElemType; /數(shù)據(jù)元素類型定義,注意這里是整型的，可以使chartypedef TElemType SqBiTreeMAX_TREE_SIZE;SqBiTree bt;typedef structTElemType *base;TElemType *top;int stacksize;

13、SqStack;Status InitStack(SqStack*S);Status Pop(SqStack*S,TElemType e);Status Push(SqStack*S,TElemType e);Status StackEmpty(SqStack*S);/全局變量的聲明char *m_pCharBuf = NULL;int m_nList100;int m_nCount = 0;char* openFileOnlyRead(char * fileName);void writeQuickSortResult(char *pResult);char* openFileOnlyRea

14、d(char * fileName) int nLen = 0; FILE *pFile = fopen(fileName, r); /打開文件 fseek(pFile, 0, SEEK_END); /文件指針移到文件尾 nLen = ftell(pFile); /得到當(dāng)前指針位置, 即是文件的長度 rewind(pFile); /文件指針恢復(fù)到文件頭位置 /動態(tài)申請空間, 為保存字符串結(jié)尾標(biāo)志0, 多申請一個字符的空間 m_pCharBuf = (char*)malloc(sizeof(char)* nLen + 1); if (!m_pCharBuf) perror(內(nèi)存不夠!n); ex

15、it(0); /讀取文件內(nèi)容/讀取的長度和源文件長度有可能有出入，這里自動調(diào)整 nLen nLen = fread(m_pCharBuf, sizeof(char), nLen, pFile); m_pCharBufnLen = 0; /添加字符串結(jié)尾標(biāo)志 /printf(%sn, pchBuf); /把讀取的內(nèi)容輸出到屏幕 fclose(pFile); /關(guān)閉文件 /free(pchBuf); /釋放空間 return m_pCharBuf;/寫入排序完成后的結(jié)果void writeQuickSortResult(char *pResult) FILE *pFile = fopen(Quic

16、kSortResult.txt, w); /打開文件 fputs(pResult, pFile); /寫入數(shù)據(jù) fclose(pFile); /關(guān)閉文件typedef struct BiTNodeTElemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;typedef BiTree QElemType;typedef struct QNode QElemType data; struct QNode *next;QNode,*QueuePtr;typedef struct LinkQueue QueuePtr front,rea

17、r;LinkQueue;void InitTree(BiTree*T);void DestroyBiTree(BiTree *T);void CreateBiTree(BiTree *T);Status ClearBiTree(BiTree T);Status BiTreeEmpty(BiTree T);Status BiTreeDepth(BiTree T);Status Root(BiTree T);Status Value(BiTree T,TElemType e);Status Assign(BiTree T,TElemType e,int value);Status Parent(B

18、iTree T,TElemType e);Status LeftChild(BiTree T,TElemType e);Status RightChild(BiTree T,TElemType e);Status LeftSibling(BiTree T,TElemType e);Status RightSibling(BiTree T,TElemType e);Status InsertChild(BiTree T,int LR,BiTree C);Status DeleteChild(BiTree T,int LR);Status PreOrderTraverse(BiTree T,Sta

19、tus(*Visit)(TElemType e);Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e);Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType e);Status LevelOrderTraverse(BiTree T,Status(*Visit)(TElemType e);Status Visit(TElemType e);BiTree Point(BiTree T,TElemType s); /返回二叉樹中指向元素值為s的結(jié)點(diǎn)的指針void Ini

20、tQueue(LinkQueue Q);/構(gòu)造一個空隊(duì)列Status QueueEmpty(LinkQueue Q);/判斷隊(duì)列是否為空void EnQueue(LinkQueue Q,QElemType e);/插入元素為新的隊(duì)尾元素Status DeQueue(LinkQueue Q,QElemType e);/刪除隊(duì)頭元素BiTNode * Create(FILE *fp);FILE * fileOpen();void main(void) int i; /文件內(nèi)容讀取出來 char *pText = openFileOnlyRead(resource.txt); printf(%snn

21、, pText); BiTree T; FILE *p; TElemType e; int n; int value; int op=1; while(op)system(cls); printf(nn);printf( Menu for Linear Table On Sequence Structure n);printf(-n);printf( 1. InitTree 11. LeftChildn);printf( 2. DestroyBiTree 12. RightChildn);printf( 3. CreateBiTree 13. LeftSiblingn);printf( 4.

22、ClearBiTree 14. RightSiblingn);printf( 5. BiTreeEmpty 15. InsertChildn);printf( 6. BiTreeDepth 16. DeleteChildn);printf( 7. Root 17. PreOrderTraversen);printf( 8. Value 18. InOrderTraversen);printf( 9. Assign 19. PostOrderTraversen);printf( 10. Parent 20. LevelOrderTraversen);printf( 0. Exitn);print

23、f(-n); printf( 請選擇你的操作020:);scanf(%d,&op); switch(op) case 1: InitTree(&T); BiTNode * Create(p); FILE * fileOpen(); if(!(T)=NULL) printf(n-二叉樹初始化成功！n);else printf(二叉樹創(chuàng)建失?。); getchar();getchar(); break; case 2: printf(是否要銷毀二叉樹！(1為是，0是否)n); scanf(%d,&n); if(n=1) DestroyBiTree(&T); else return 0; if(T

24、!=NULL) printf(n-二叉樹成功銷毀實(shí)現(xiàn)！n); else printf(n-DestroyList功能待實(shí)現(xiàn)); getchar();getchar(); break; case 3: /InitTree(&T); printf(Please input the char:e=n); scanf(%d,&e); CreateBiTree(T); if(T)!=NULL) printf(n-CreateBiTree功能實(shí)現(xiàn)！n); else printf(n-CreateBiTree功能待實(shí)現(xiàn)！n); getchar();getchar(); break; case 4: Clea

25、rBiTree(T); if(T) printf(n-ClearBiTree功能待實(shí)現(xiàn)！n); else printf(n-ClearBiTree功能實(shí)現(xiàn)！n);0- getchar();getchar(); break; case 5: BiTreeEmpty(T); if(T) printf(n-BiTreeEmpty功能實(shí)現(xiàn)！n); else printf(n-BiTreeEmpty功能待實(shí)現(xiàn)！n); getchar();getchar(); break; case 6: BiTreeDepth(T); if(T) printf(n-BiTreeDepth功能實(shí)現(xiàn)！n); else pr

26、intf(n-BiTreeDepth功能待實(shí)現(xiàn)！n); getchar();getchar(); break; case 7: Root(T); if(T) printf(n-Root功能實(shí)現(xiàn)！n); else printf(n-Root功能待實(shí)現(xiàn)！n); getchar();getchar(); break; case 8: printf(Please input the node of you want:e=n); scanf(%c,&e); Value(T,e); if(T=NULL) printf(n-Value功能實(shí)現(xiàn)！n); else printf(n-Value功能待實(shí)現(xiàn)！n);

27、 getchar();getchar(); break; case 9: printf(Please input the node and number of you want:e=nvalue=n); scanf(%c%d,&e,&value); Assign(T,e,value); if(T=NULL) printf(n-Assign功能實(shí)現(xiàn)！n); else printf(n-Assign功能待實(shí)現(xiàn)！n); getchar();getchar(); break; case 10: printf(Please input the node of you want:e=n); scanf(%

28、c,&e); Parent(T,e); if(T=NULL) printf(n-Parent功能實(shí)現(xiàn)！n); else printf(n-Parent功能待實(shí)現(xiàn)！n); getchar();getchar(); break; case 11: printf(Please input the node of you want:e=n); scanf(%c,&e); LeftChild(T,e); if(T!=NULL) printf(n-LeftChild功能實(shí)現(xiàn)！n); else printf(n-LeftChild功能待實(shí)現(xiàn)n); getchar();getchar(); break; ca

29、se 12: printf(Please input the node of you want:e=n); scanf(%c,&e); RightChild(T,e); if(T!=NULL) printf(n-RightChild功能實(shí)現(xiàn)n); else printf(n-RightChild功能待實(shí)現(xiàn)！n); getchar();getchar(); break; case 13: printf(Please input the node of you want:e=n); scanf(%c,&e); LeftSibling(T,e); if(T!=NULL) printf(n-LeftS

30、ibling功能實(shí)現(xiàn)！n); else printf(n-LeftSibling功能待實(shí)現(xiàn)n); getchar();getchar(); break; case 14: printf(Please input the node of you want:e=n); scanf(%c,&e); RightSibling(T,e); if(T!=NULL) printf(n-LeftSibling功能實(shí)現(xiàn)！n); else printf(n-LeftSibling功能待實(shí)現(xiàn)！n); getchar();getchar(); break; case 15: /printf(Please input

31、the node of you want:p,e,LR and C=n); / scanf(%c,&e); / InsertChild(T,P,LR,C); printf(線性表是空表！n); getchar();getchar(); break; case 16: printf(線性表是空表！n); getchar();getchar(); break; case 17: printf(線性表是空表！n); getchar();getchar(); break; case 18: printf(線性表是空表！n); getchar();getchar(); break; case 19: p

32、rintf(Please input the node of you want:e=n); scanf(%c,&e); PostOrderTraverse(T,e); if(T!=NULL) printf(功能實(shí)現(xiàn)了！n);elseprintf(功能待實(shí)現(xiàn)了！n); getchar();getchar(); break; case 20: printf(線性表是空表！n); getchar();getchar(); break; case 0: break;/end of switch /end of while char result1000 = QuickSortResult: ; for

33、(i = 0; i data=NULL;return OK; void DestroyBiTree(BiTree *T) if(T!=NULL) DestroyBiTree(*T)-lchild); DestroyBiTree(*T)-rchild); free(T); T=NULL; return OK; void CreateBiTree(BiTree *T) /* 算法6.4:按先序次序輸入二叉樹中結(jié)點(diǎn)的值可為字符型或整型，在主程中 */ /* 定義，構(gòu)造二叉鏈表表示的二叉樹T。變量Nil表示空子樹。有改動 */ TElemType ch; #ifdef CHAR scanf(%c,&c

34、h); #endif #ifdef INT scanf(%d,&ch); #endif if(ch= ) /* 空 */ *T=NULL; else *T=(BiTree)malloc(sizeof(BiTNode); if(!*T) exit(OVERFLOW); (*T)-data=ch; /* 生成根結(jié)點(diǎn) */ CreateBiTree(&(*T)-lchild); /* 構(gòu)造左子樹 */ CreateBiTree(&(*T)-rchild); /* 構(gòu)造右子樹 */ Status ClearBiTree(BiTree T) BiTree pl,pr; if(T=NULL) return

35、 ; if(T) pl=T-lchild; pr=T-rchild; T-lchild=NULL; T-rchild=NULL; free(T); T=NULL; ClearBiTree(pl); ClearBiTree(pr); return OK;Status BiTreeEmpty(BiTree T) if(T=NULL) return TRUE; else return FALSE;Status BiTreeDepth(BiTree T) int lchildHigh,rchildHigh; if(T=NULL)return 0; else lchildHigh=BiTreeDepth

36、(T-lchild); rchildHigh=BiTreeDepth(T-rchild); return lchildHighrchildHigh ? (lchildHigh+1):(rchildHigh+1);Status Root(BiTree T) if(T=NULL)return ERROR; printf(%c,T-data); Root(T-lchild); Root(T-rchild); return OK;Status Value(BiTree T,TElemType e) if(T=NULL)return ERROR; else if(T-data=e)return (T-d

37、ata); Value(T-lchild,e); Value(T-rchild,e); return OK; Status Assign(BiTree T,TElemType e,int value) if(T=NULL)return ERROR; if(T-data=e) T-data=value; else Assign(T-lchild,e,value); Assign(T-rchild,e,value); return OK;Status Parent(BiTree T,TElemType e) if(T=NULL)return ERROR; if(T-data=e) if(T-lch

38、ild | T-rchild) return (T-data); else Parent(T-lchild,e); Parent(T-rchild,e); return OK;Status LeftChild(BiTree T,TElemType e) if(T=NULL) return; if(T-data=e) if(!(T-lchild) printf(%c,T-lchild); else return NULL; else T-lchild; LeftChild(T-lchild,e); T-rchild; LeftChild(T-rchild,e); return OK;Status

39、 RightChild(BiTree T,TElemType e)if(T=NULL) return; if(T-data=e) if(!(T-rchild) printf(%c,T-rchild); else return NULL; else T-lchild; RightChild(T-lchild,e); T-rchild; RightChild(T-rchild,e); return OK;Status LeftSibling(BiTree T,TElemType e) /返回左兄弟 TElemType a; BiTree p; if(T) a=Parent(T,e);/a為e的雙親

40、 if(a!=NULL) p=Point(T,a);/p指向結(jié)點(diǎn)a的指針 if(p-lchild&p-rchild&p-rchild-data=e)/p存在左右孩子而且右孩子是e return p-lchild-data; return NULL;Status RightSibling(BiTree T,TElemType e)TElemType a; BiTree p; if(T) a=Parent(T,e);/a為e的雙親 if(a!=NULL) p=Point(T,a);/p為指向結(jié)點(diǎn)的a的指針 if(p-lchild&p-rchild&p-lchild-data=e) return p

41、-lchild-data; return NULL;Status InsertChild(BiTree T,int LR,BiTree C) if(T) if(LR=0) C-rchild=T-lchild; T-lchild=C; else C-rchild=T-rchild;/T指結(jié)點(diǎn)的原有右子樹成為C的右子樹 T-rchild=C; return OK; return ERROR;Status DeleteChild(BiTree T,int LR) if(T) if(LR=0)DestroyBiTree(T-lchild);else DestroyBiTree(T-rchild);re

42、turn OK;return ERROR;Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e) Status PrintElement(TElemType e) printf(e); return OK; if(T) if(Visit(T-data) if(PreOrderTraverse(T-lchild,Visit) if(PreOrderTraverse(T-rchild,Visit) return OK; return ERROR; else return OK; /PreOrderTraaverseStatus In

43、OrderTraverse(BiTree T,Status(*Visit)(TElemType e) Status PrintElement(TElemType e) printf(e); return OK; if(T) if(PreOrderTraverse(T-lchild,Visit) if(Vist(T-data); if(PreOrderTraverse(T-rchild,Visit) return OK; return ERROR; else return OK; /InOrderTraverseStatus PostOrderTraverse(BiTree T,Status(*

44、Visit)(TElemType e) Status PrintElement(TElemType e) printf(e); return OK; if(T) if(PreOrderTraverse(T-lchild,Visit) if(PreOrderTraverse(T-rchild,Visit) if(Vist(T-data) return OK; return ERROR; else return OK; /PostOrderTraverseStatus LevelOrderTraverse(BiTree T,Status(*Visit)(TElemType e) BiTree p,

45、newNode; Status PrintElement(TElemType e) printf(e); return OK; if(T) if(p=T-lchild) newNode=(BiTree)malloc(sizeof(BiTNode); newNode-data=e; newNode-rchild=NULL; newNode-lchild=p; T-lchild=newNode; else return ERROR; else return ERROR; return OK;/LevelOrderTraverse/Status Visit(TElemType e)/ printf(

46、%c,e);/BiTree Point(BiTree T,TElemType s)/返回二叉樹T中指向元素值為S的結(jié)點(diǎn)指針 LinkQueue q; QElemType a; if(T) InitQueue(q);/初始化隊(duì)列 EnQueue(q,T);/根指針入隊(duì) while(!QueueEmpty(q)/隊(duì)不空 DeQueue(q,a);/出隊(duì)，隊(duì)列元素賦給e if(a-data=s)/a所指結(jié)點(diǎn)為的值為s return a; if(a-lchild)/有左孩子 EnQueue(q,a-lchild);/入隊(duì)左孩子 if(a-rchild)/有右孩子 EnQueue(q,a-rchild)

47、;/入隊(duì)右孩子 return NULL;void InitQueue(LinkQueue Q)/初始化一個隊(duì)列 Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode); if(!Q.front)/生成頭結(jié)點(diǎn)失敗 exit(OVERFLOW); Q.front-next=NULL; Status QueueEmpty(LinkQueue Q) /判斷隊(duì)列是否為空 if(Q.front-next=NULL) return TRUE; else return FALSE; void EnQueue(LinkQueue Q,QElemType e) /插入元素e為隊(duì)

48、列Q的新的隊(duì)尾元素 QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode); /動態(tài)生成新結(jié)點(diǎn) if(!p) exit(OVERFLOW); p-data=e;/將e的值賦給新結(jié)點(diǎn) p-next=NULL;/新結(jié)點(diǎn)的指針為空 Q.rear-next=p;/原隊(duì)尾結(jié)點(diǎn)的指針域?yàn)橹赶蛐陆Y(jié)點(diǎn) Q.rear=p;/尾指針指向新結(jié)點(diǎn) Status DeQueue(LinkQueue Q,QElemType e) /假如隊(duì)列不為空，刪除Q的隊(duì)頭元素，用e返回其值 QueuePtr p; if(Q.front=Q.rear)/隊(duì)列為空 return ERROR; p=Q.f

49、ront-next;/p指向隊(duì)頭結(jié)點(diǎn) e=p-data;/隊(duì)頭元素賦給e Q.front-next=p-next;/頭結(jié)點(diǎn)指向下一個結(jié)點(diǎn) if(Q.rear=p)/如果刪除的隊(duì)尾結(jié)點(diǎn) Q.rear=Q.front;/修改隊(duì)尾指針指向頭結(jié)點(diǎn) free(p); return OK; FILE * fileOpen() FILE *fp; fp = fopen(test.txt, r); assert(fp != NULL); return fp;BiTNode * Create(FILE *fp) char ch; BiTNode * bt = NULL; if (ch = fgetc(fp) = EOF) return NULL; if (# != ch) bt = (BiTNode *)malloc(sizeof(BiTNode); bt-data = ch; bt-lchild = Create(fp); bt-rchild = Create(fp); return bt;Status InitStack(SqStack*S)S-base=(TElemType*)malloc(MAX_TREE_SIZE*sizeof(TElemType);if(!(S-base)exit(OVERFLOW);