實(shí)現(xiàn)二叉樹(shù)中所有節(jié)點(diǎn)左右子樹(shù)的交換

1、實(shí)現(xiàn)二叉樹(shù)中所有節(jié)點(diǎn)左右子樹(shù)的交換數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告JtNGGANGSHANUNIVERSITY題目名稱：實(shí)現(xiàn)二叉樹(shù)中所有節(jié)點(diǎn)左右子樹(shù)的交換學(xué)院：信息科學(xué)與工程學(xué)院專業(yè)班級(jí)：計(jì)算機(jī)科學(xué)與技術(shù)1003班姓名：葉成功學(xué)號(hào)：12081414指導(dǎo)教師：陳國(guó)良教授李立三教授日期：2021年7月3日目錄問(wèn)題描述5二、根本要求6三、數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)71、結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)72、根本操作7四、軟件模塊結(jié)構(gòu)圖8五、程序設(shè)計(jì)思想81、程序設(shè)計(jì)根本思想82、程序設(shè)計(jì)根本思想9六、程序流程圖91、創(chuàng)立函數(shù)92、前序遍歷函數(shù)113、中序遍歷函數(shù)124、后序遍歷函數(shù)135、層序遍歷函數(shù)156、左右子樹(shù)交換函數(shù)167、二叉

2、樹(shù)打印函數(shù)188、遍歷調(diào)用函數(shù)189、菜單函數(shù)2110、主函數(shù)21七、源程序代碼24八、調(diào)t分析36九、數(shù)據(jù)測(cè)試381、主菜單界面392、建立一棵有二十個(gè)結(jié)點(diǎn)的完全二叉樹(shù)393、打印二叉樹(shù)394、遍歷二叉樹(shù)405、二叉樹(shù)左右子樹(shù)交換406、交換后打印二叉樹(shù)407、交換后二叉樹(shù)的遍歷408、退出程序41十、用戶使用手冊(cè)41十一、心得體會(huì)41一、問(wèn)題描述在計(jì)算機(jī)領(lǐng)域有著極為廣泛的應(yīng)用.在二叉樹(shù)的一些應(yīng)用中,常常要求在樹(shù)中查找具有某些特征的結(jié)點(diǎn)或者對(duì)樹(shù)中全部結(jié)點(diǎn)逐一進(jìn)行某種處理,這就提出了遍歷二叉樹(shù).根據(jù)遍歷的方向的不同,有前序遍歷、中序遍歷、后序遍歷以及層序遍歷.在本次課程設(shè)計(jì)中,要求學(xué)生通過(guò)編寫

3、程序完成對(duì)二叉樹(shù)的一些操作,比方可以構(gòu)造二叉樹(shù)、打印二叉樹(shù)、遍歷二叉樹(shù)以及對(duì)左右子樹(shù)進(jìn)行交換等等.二、根本要求要求：.構(gòu)造一顆20個(gè)節(jié)點(diǎn)的完全二叉樹(shù)或者20個(gè)節(jié)點(diǎn)以上的滿二叉樹(shù).實(shí)現(xiàn)如下步驟：(1)實(shí)現(xiàn)二叉樹(shù)的構(gòu)造過(guò)程,并打印出二叉樹(shù)(2)對(duì)該二叉樹(shù)分別用層序、前序、中序和后序四種不同的方法進(jìn)行遍歷；(3)將該二叉樹(shù)的所有左右子樹(shù)進(jìn)行交換,得到新的二叉樹(shù),并打印出該二叉樹(shù)；(4)對(duì)新獲得的二叉樹(shù)分別用層序、前序、中序和后序四種不同的方法進(jìn)行遍歷O三、數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)由數(shù)據(jù)結(jié)構(gòu)中二叉樹(shù)的定義可知,二叉樹(shù)的結(jié)點(diǎn)由一個(gè)數(shù)據(jù)元素和分別指向其左、右子樹(shù)的兩個(gè)分支構(gòu)成,所以在本程序二叉樹(shù)的構(gòu)造是采用二叉鏈表

4、的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),鏈表中的結(jié)點(diǎn)應(yīng)包含三個(gè)域：數(shù)據(jù)域和左、右孩子的指針域.這種存儲(chǔ)結(jié)構(gòu)可以方便二叉樹(shù)的建立以及遍歷.1、結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)structnode(chardata;structnode*lchild,*rchild;)2、根本操作voidCreate(BiTNode*p)初始條件：根據(jù)結(jié)點(diǎn)的結(jié)構(gòu)體構(gòu)造二叉樹(shù)；操作結(jié)果：構(gòu)造一棵二叉樹(shù).voidPreOrderTraverse(BiTreeT)初始條件：二叉樹(shù)T存在；操作結(jié)果：根據(jù)前序遍歷方法遍歷二叉樹(shù).voidInOrderTraverse(BiTreeT)初始條件：二叉樹(shù)T存在；操作結(jié)果：根據(jù)中序遍歷方法遍歷二叉樹(shù).voidPostOr

5、derTraverse(BiTreeT)初始條件：二叉樹(shù)T存在；操作結(jié)果：根據(jù)后序遍歷方法遍歷二叉樹(shù).voidLevelOrderTraverse(BiTreeT)初始條件：二叉樹(shù)T存在；操作結(jié)果：根據(jù)層序遍歷方法遍歷二叉樹(shù).voidSwapChild(BiTNode*p)初始條件：二叉樹(shù)存在且交換的結(jié)點(diǎn)有子樹(shù)；操作結(jié)果：將二叉樹(shù)左右結(jié)點(diǎn)交換.voidPaint(BiTreeT)初始條件：二叉樹(shù)T存在；操作結(jié)果：將二叉樹(shù)的結(jié)點(diǎn)打印出來(lái)四、軟件模塊結(jié)構(gòu)圖1、程序設(shè)計(jì)根本思想(1)本實(shí)驗(yàn)要求編寫一個(gè)程序?qū)崿F(xiàn)對(duì)二叉樹(shù)的各種根本操作,并以此為目的設(shè)計(jì)一個(gè)程序,完成如下功能：1 、輸入二叉樹(shù)的先序序列字

6、符,建立二叉鏈表.注意：輸入時(shí),必須參加虛結(jié)點(diǎn)以示空指針的位置；假設(shè)虛結(jié)點(diǎn)輸入時(shí)用空格字符表示.2 、打印二叉樹(shù).3 、按先序、中序、后序和層序三種不同方法遍歷二叉樹(shù).4 、交換二叉樹(shù)的所有左右子樹(shù).5 、打印二叉樹(shù),并且分別根據(jù)先序、中序、后序和層序三種不同方法遍歷二叉樹(shù).6 、在設(shè)計(jì)一個(gè)簡(jiǎn)單的菜單,分別調(diào)試上述算法.7 、編寫主程序完成各功能的調(diào)用和實(shí)現(xiàn).(2)測(cè)試數(shù)據(jù)：1、根據(jù)先序序列依次輸入字符.2 、打印二叉樹(shù)并且按先序、中序和后序遍歷二叉樹(shù)并輸出遍歷結(jié)果.3 、輸出交換二叉樹(shù)的左右子樹(shù)并且打印二叉樹(shù)并且按先序、中序和后序遍歷二叉樹(shù)并輸出遍歷結(jié)果.2、程序設(shè)計(jì)根本思想本程序含有7個(gè)函

7、數(shù)；主函數(shù)main()前序遍歷二叉樹(shù)PreOrderTraverse(T,PrintChar)中序遍歷二叉樹(shù)Inorder(T)后續(xù)遍歷二叉樹(shù)Postorder(T)層序遍歷二叉樹(shù)LevelOrderTraverse(T)打印二叉樹(shù)Paint(T)交換二叉樹(shù)所有左右子樹(shù)SwapChild(T)六、程序流程圖1、創(chuàng)立函數(shù)voidCreate(BiTNode*p)(chare;e=getchar();if(e='*')(*p)=NULL;else(if(!(*p)=(BiTree)malloc(sizeof(BiTNode)(printf("分配失敗n");ex

8、it(0);(*p)->data=e;Create(&(*p)->lchild);Create(&(*p)->rchild);2、前序遍歷函數(shù)輸出根節(jié)點(diǎn)前序遍歷專了前序遍力布于遍歷完成voidPreOrderTraverse(BiTreeT)(if(T)(printf("%c",T->data);PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);3、中序遍歷函數(shù)中序遍歷4子輸出根節(jié);點(diǎn)中序遍歷,丁子遍歷.完成公結(jié)voidInOrderTraverse(BiTre

9、eT)(if(T)(InOrderTraverse(T->lchild);printf("%c",T->data);InOrderTraverse(T->rchild);4、后序遍歷函數(shù)后序遍歷年子后序遍歷有子輸出結(jié)思二遍歷完曲結(jié)voidPostOrderTraverse(BiTreeT)(if(T)(PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);printf("%c",T->data);)5、層序遍歷'函數(shù)voidLevelOrderTra

10、verse(BiTreeT)(BiTreeQMaxLength;intfront=0,rear=0;BiTreep;/根結(jié)點(diǎn)入隊(duì)if(T)(Qrear=T;rear=(rear+1)%MaxLength;/插入結(jié)點(diǎn)為新的隊(duì)尾元素)while(front!=rear)(/隊(duì)頭元素出隊(duì)p=Qfront;front=(front+1)%MaxLength;/刪除頭結(jié)點(diǎn)printf("%c,p->data);/左孩子不為空,入隊(duì)if(p->lchild)(Qrear=p->lchild;rear=(rear+1)%MaxLength;/插入左孩子結(jié)點(diǎn)為新的隊(duì)尾元素)/右孩子

11、不為空,入隊(duì)if(p->rchild)(Qrear=p->rchild;rear=(rear+1)%MaxLength;/插入右孩子結(jié)點(diǎn)為新的隊(duì)尾元素)6、左右子樹(shù)交換函數(shù)/交換左右子樹(shù)(遞歸算法)voidSwapChild(BiTNode*p)(BiTNode*temp;if(*p)(/交換左右子樹(shù)指針temp=(*p)->lchild;(*p)->lchild=(*p)->rchild;(*p)->rchild=temp;SwapChild(&(*p)->lchild);SwapChild(&(*p)->rchild);7、二

12、叉樹(shù)打印函數(shù)/打印二叉樹(shù)(采用凹入表橫向打印)voidPaint(BiTreeT,intn)(charc;if(T)(Paint(T->rchild,n+1);printf("%*c,4*n,T->data);if(T->lchild&&T->rchild)c='<'elseif(T->rchild)c='/'elseif(T->lchild)c=''elsec=''printf("%cn",c);Paint(T->lchild,n+1)

13、;8、遍歷調(diào)用函數(shù)輸/1、心刖序遍遍歷函數(shù)(調(diào)用層序,前序,中序,后序遍歷函數(shù))voidOrderTraverse(BiTreeT)(printf("層序遍歷:");LevelOrderTraverse(T);printf("n");printf("前序遍歷:");PreOrderTraverse(T);printf("n");printf("中序遍歷:");InOrderTraverse(T);printf("n");printf("后序遍歷:");Po

14、stOrderTraverse(T);printf("n");9、菜單函數(shù)/主菜單函數(shù)顯示系統(tǒng)功能,獲取用戶輸入voidmenuint*choiceprintf"歡送使用n"printf"1.建立二叉樹(shù)前序n"printf"2.打印二叉樹(shù)n"printf"3.遍歷二叉樹(shù)層序,前序,中序,后序n"printf"4.交換左右子樹(shù)n"printf"0.退出n"printf"n"printf"你的選擇："scanf"

15、;%d",choice;getchar;/很重要,存儲(chǔ)回車,防止對(duì)后面函數(shù)的影響產(chǎn)*10、主函數(shù)產(chǎn)*主函數(shù)*/根據(jù)用戶的輸入,調(diào)用相應(yīng)的子函數(shù)main()(BiTreeT=NULL;/定義二叉樹(shù)并默認(rèn)為空intchoice;while(1)(menu(&choice);/顯示主菜單switch(choice)/根據(jù)不同選擇,實(shí)現(xiàn)相應(yīng)操作(case 1: /創(chuàng)立二叉樹(shù)(printf("輸入各元素,空子樹(shù)用'*'表示n");Create(&T);printf("創(chuàng)立成功!nn");break;case 2: /打印二

16、叉樹(shù)(if(T)(printf("打印結(jié)果:n");Paint(T,1);)elseprintf("二叉樹(shù)為空!n");printf("n");break;case 3: /遍歷二叉樹(shù)(if(T)OrderTraverse(T);elseprintf("二叉樹(shù)為空!n");printf("n");break;case 4: /交換左右子樹(shù)(SwapChild(&T);printf("交換成功!n");printf("n");break;case0:

17、exit(0);/退出default:printf("無(wú)效輸入!nn");/*七、源程序代碼/*結(jié)構(gòu)*/用到的頭文件#include<stdio.h>頭文件、宏定義和存儲(chǔ)#include<stdlib.h>隊(duì)列最大結(jié)點(diǎn)數(shù)目#defineMaxLength100定義二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉鏈表typedefstructnodechardata;structnode*lchild,*rchild;BiTNode,*BiTree;/*各功能函數(shù)的定/*義*/菜單函數(shù)*/*創(chuàng)立、遍歷、交換、打印、H創(chuàng)立二叉樹(shù)(前序)voidCreate(BiTNode*p)(c

18、hare;e=getchar();if(e='*')(*p)=NULL;else(if(!(*p)=(BiTree)malloc(sizeof(BiTNode)(printf("分配失敗n");exit(0);(*p)->data=e;Create(&(*p)->lchild);Create(&(*p)->rchild);遞歸前序遍歷voidPreOrderTraverse(BiTreeT)(if(T)(printf("%c",T->data);PreOrderTraverse(T->lchi

19、ld);PreOrderTraverse(T->rchild);)遞歸中序遍歷voidInOrderTraverse(BiTreeT)(if(T)(InOrderTraverse(T->lchild);printf("%c",T->data);InOrderTraverse(T->rchild);)遞歸后序遍歷voidPostOrderTraverse(BiTreeT)(if(T)(PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);printf("%c"

20、,T->data);)層序遍歷(利用循環(huán)隊(duì)列)voidLevelOrderTraverse(BiTreeT)(BiTreeQMaxLength;intfront=0,rear=0;BiTreep;/根結(jié)點(diǎn)入隊(duì)if(T)(Qrear=T;rear=(rear+1)%MaxLength;)while(front!=rear)(/隊(duì)頭元素出隊(duì)p=Qfront;front=(front+1)%MaxLength;printf("%c,p->data);左孩子不為空,入隊(duì)if(p->lchild)(Qrear=p->lchild;rear=(rear+1)%MaxLen

21、gth;右孩子不為空,入隊(duì)if(p->rchild)(Qrear=p->rchild;rear=(rear+1)%MaxLength;)交換左右子樹(shù)(遞歸,類似于先序遍歷)voidSwapChild(BiTNode*p)(BiTNode*temp;if(*p)(交換左右子樹(shù)指針temp=(*p)->lchild;(*p)->lchild=(*p)->rchild;(*p)->rchild=temp;SwapChild(&(*p)->lchild);SwapChild(&(*p)->rchild);)打印二叉樹(shù)(采用凹入表橫向打印)

22、voidPaint(BiTreeT,intn)(charc;if(T)(Paint(T->rchild,n+1);printf("%*c,4*n,T->data);if(T->lchild&&T->rchild)c='<'elseif(T->rchild)c='/'elseif(T->lchild)c=''elsec二;printf("%cn",c);Paint(T->lchild,n+1);)遍歷函數(shù)(調(diào)用層序,前序,中序,后序遍歷函數(shù))voidOrd

23、erTraverse(BiTreeT)printf("層序遍歷:");LevelOrderTraverse(T);printf("n");printf("前序遍歷:");PreOrderTraverse(T);printf("n");printf("中序遍歷:");InOrderTraverse(T);printf"后序遍歷:"PostOrderTraverseT;printf"n"主菜單顯示系統(tǒng)功能,獲取用戶輸入voidmenuint*choicepri

24、ntf"歡送使用n"printf"1.建立二叉樹(shù)前序n"printf"2.打印二叉樹(shù)n"printf"3.遍歷二叉樹(shù)層序,前序,中序,后序n"printf"4.交換左右子樹(shù)n"printf"0.退出n"printf"n"printf"你的選擇:"scanf"%d",choice;getchar;很重要存儲(chǔ)回車防止對(duì)后面函數(shù)的影響/*/*/根據(jù)用戶的輸入,調(diào)用相應(yīng)的子函數(shù)main()(BiTreeT=NULL;空定義二

25、叉樹(shù)并默認(rèn)為intchoice;while(1)(顯示主菜單menu(&choice);switch(choice)根據(jù)不同選擇)實(shí)現(xiàn)相應(yīng)操作(case 1: /創(chuàng)立二叉樹(shù)(printf("輸入各元素,空子樹(shù)用'*'表示n")；Create(&T);printf("創(chuàng)立成功!nn");break;case 2: /打印二叉樹(shù)(if(T)(printf("打印結(jié)果:n");Paint(T,1);elseprintf("二叉樹(shù)為空!n");printf("n");br

26、eak;case 3: 遍歷二叉樹(shù)(if(T)OrderTraverse(T);elseprintf("二叉樹(shù)為空!n");printf("n");break;case 4: 交換左右子樹(shù)(SwapChild(&T);printf("交換成功！n");printf("n");break;case0:exit(0);/退出default:printf("無(wú)效輸入!nn");)/*/八、調(diào)試分析運(yùn)行程序,例如：輸入如下列圖所示的有20個(gè)結(jié)點(diǎn)的完全二叉樹(shù)時(shí)間復(fù)雜度分析:很顯然,先序.中序.后序

27、遞歸算法的復(fù)雜度是相同的,遞歸算法非常的簡(jiǎn)單.例如先序先訪問(wèn)跟節(jié)點(diǎn),然后訪問(wèn)左節(jié)點(diǎn),再訪問(wèn)右節(jié)點(diǎn).仔細(xì)看一下遞歸程序,就會(huì)發(fā)現(xiàn),其實(shí)每次都是子樹(shù)的左子樹(shù)(Ichild),直到左子樹(shù)為空,然后開(kāi)始從遞歸的最深處返回,然后開(kāi)始恢復(fù)遞歸現(xiàn)場(chǎng),訪問(wèn)右子樹(shù).其實(shí)過(guò)程很簡(jiǎn)單：一直往左走root->lchild->lchild->lchild.->null,由于是先序遍歷,因此一遇到節(jié)點(diǎn),便需要立即訪問(wèn)；由于一直走到最左邊后,需要逐步返回到父節(jié)點(diǎn)訪問(wèn)右節(jié)點(diǎn),時(shí)間方面每個(gè)節(jié)點(diǎn)調(diào)用一次函數(shù),訪問(wèn)一次,是O(n).沒(méi)有空間開(kāi)銷,所以是0.中序.后序遞歸算法同先序一樣.時(shí)間復(fù)雜度是O(n),

28、空間復(fù)雜度是0.同理可知中序與后序也是一樣的.非遞歸層序遍歷有不一樣.層序遍歷中每次將節(jié)點(diǎn)壓入隊(duì),然后彈出,再讓左子樹(shù)入隊(duì),再讓右子樹(shù)入隊(duì),在遍歷過(guò)程中,左右子樹(shù)依次入隊(duì)出隊(duì).時(shí)間復(fù)雜度O(n),空間復(fù)雜度為00問(wèn)題一：前序遍歷、中序遍歷以及后序遍歷為遞歸算法很簡(jiǎn)單就沒(méi)什么可說(shuō)的了,而層次遍歷就需要用到隊(duì)列處理稍微復(fù)雜一點(diǎn).創(chuàng)立二叉樹(shù)時(shí),要求二叉樹(shù)內(nèi)容可以是各種形式,剛開(kāi)始編創(chuàng)立算法的時(shí)候調(diào)試總是出錯(cuò),后來(lái)經(jīng)過(guò)參考數(shù)據(jù)結(jié)構(gòu)相關(guān)資料才發(fā)現(xiàn)有一個(gè)地方少寫一行申請(qǐng)空間的代碼.問(wèn)題二：非遞歸算法在編程時(shí)都是不很順利,其中層序遍歷有點(diǎn)難,需要掌握隊(duì)列的知識(shí),但是經(jīng)過(guò)我不懈努力,最終成功的解決了這個(gè)問(wèn)題.

29、問(wèn)題三：要注意輸入必要的頭文件,比方調(diào)用malloc需要stdlib.h的頭文件,否者編譯出錯(cuò),有時(shí)不知道頭文件可以查詢書本.問(wèn)題四：在這次課程設(shè)計(jì)中其實(shí)主要問(wèn)題就是編程完成后會(huì)有很多小錯(cuò)誤.所以需要耐心調(diào)試算法的改良設(shè)想：我沒(méi)有想到更好的算法,我想到的最好的算法編出的C語(yǔ)言程序代碼只有100多行,但是可以非常成功的解決了問(wèn)題.我認(rèn)為我的算法應(yīng)該算是最簡(jiǎn)潔的算法了.九、數(shù)據(jù)測(cè)試數(shù)據(jù)測(cè)試主要是由截圖來(lái)說(shuō)明,編譯成功后,根據(jù)前序遍歷的方法輸入子樹(shù),空子樹(shù)用*表示,在本程序中輸入的是一個(gè)有二十個(gè)結(jié)點(diǎn)的二叉樹(shù),輸入ABDHP*Q*IR*S*EJT*K*CFL*M*GN*O*,那么構(gòu)成一棵擁有二十個(gè)結(jié)點(diǎn)的完全二叉樹(shù),如圖：輸入二叉樹(shù)后,分別調(diào)用打印函數(shù)、前序遍歷函數(shù)、中序遍歷函數(shù)、后序遍歷函數(shù)以及層次遍歷函數(shù),在功能實(shí)現(xiàn)后.調(diào)換二叉樹(shù)所有的左右子樹(shù),再分別調(diào)用打印函數(shù)