C語(yǔ)言綜合實(shí)驗(yàn)設(shè)計(jì)報(bào)告-數(shù)據(jù)結(jié)構(gòu)：二叉樹(shù)的遍歷.doc

此文檔收集于網(wǎng)絡(luò)，如有侵權(quán)，請(qǐng)聯(lián)系網(wǎng)站刪除C語(yǔ)言綜合實(shí)驗(yàn)設(shè)計(jì)報(bào)告 題目：數(shù)據(jù)結(jié)構(gòu)：二叉樹(shù)的遍歷 學(xué)院:化學(xué)工程學(xué)院 專業(yè):制藥工程 班級(jí):050607 學(xué)號(hào)： 姓名： 設(shè)計(jì)日期:2007年1月11日 指導(dǎo)老師： 一 選題背景數(shù)據(jù)結(jié)構(gòu)是由若干特性相同的數(shù)據(jù)元素構(gòu)成的集合，且在集合上存在一種或多種關(guān)系。由關(guān)系不同可將數(shù)據(jù)結(jié)構(gòu)分為四類：線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)、圖狀結(jié)構(gòu)和集合結(jié)構(gòu)。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)邏輯結(jié)構(gòu)在計(jì)算機(jī)中的映象，由關(guān)系的兩種映象方法可得到兩類存儲(chǔ)結(jié)構(gòu)：一類是順序存儲(chǔ)結(jié)構(gòu)，它以數(shù)據(jù)元素相對(duì)的存儲(chǔ)位置表示關(guān)系，則存儲(chǔ)結(jié)構(gòu)中只包含數(shù)據(jù)元素本身的信息；另一類是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，它以附加的指針信息（后繼元素的存儲(chǔ)地址）表示關(guān)系。數(shù)據(jù)結(jié)構(gòu)課程是離散數(shù)學(xué)的后續(xù)課程，并是操作系統(tǒng)、編譯原理、數(shù)據(jù)庫(kù)系統(tǒng)、計(jì)算機(jī)算法設(shè)計(jì)與分析、計(jì)算機(jī)網(wǎng)絡(luò)、軟件工程、人工智能等的基礎(chǔ)課程，是將來(lái)進(jìn)行大型程序設(shè)計(jì)的一個(gè)訓(xùn)練過(guò)程。二 設(shè)計(jì)思想通過(guò)調(diào)用函數(shù)的方法進(jìn)行二叉樹(shù)的遍歷，定義坐標(biāo)固定結(jié)點(diǎn)的位置。自動(dòng)建立樹(shù)和手動(dòng)建立樹(shù)的標(biāo)志,選擇：2手動(dòng),1自動(dòng)。文本模式下創(chuàng)建樹(shù)的過(guò)程，如果選擇1自動(dòng)，電腦自動(dòng)建立樹(shù)，如果選擇2手動(dòng)，需要人工手動(dòng)建立。手動(dòng)提示輸入結(jié)點(diǎn)，創(chuàng)建好樹(shù)。再用圖形顯示創(chuàng)建好的樹(shù)，進(jìn)行先序，中序，后序遍歷。遍歷時(shí)顯示每個(gè)結(jié)點(diǎn)的過(guò)程。最后關(guān)閉圖形。三 主要問(wèn)題的解決方法及技術(shù)關(guān)鍵 存在的主要問(wèn)題是在手動(dòng)創(chuàng)建樹(shù)時(shí)怎樣輸入結(jié)點(diǎn)，當(dāng)選擇“人工手動(dòng)建立”時(shí)，在提示后依次輸入26個(gè)字符或數(shù)字，每行一個(gè)。此時(shí)樹(shù)就能建立，然后用圖形顯示出來(lái)。本程序的技術(shù)關(guān)鍵是建立二叉樹(shù)和圖形顯示遍歷的過(guò)程，分別用到Tree *CreatTree(),Void DrawTree(Tree *t)等函數(shù)。遍歷結(jié)束后，圖形關(guān)閉。四 流程圖開(kāi)始主函數(shù)文本模式下創(chuàng)建樹(shù)選擇常量2常量1Printf()Root=InitTree()調(diào)用函數(shù)Tree*InitTree()圖形顯示創(chuàng)建的樹(shù)前序遍歷 中序遍歷遍歷時(shí)顯示結(jié)點(diǎn)的過(guò)程后序遍歷圖形初始化圖形關(guān)閉END五 程序清單/*tree2.c二叉樹(shù)演示*/#include #include #include #include #include typedef struct TREE char data;/*樹(shù)的結(jié)點(diǎn)數(shù)據(jù)*/ struct TREE *lchild; struct TREE *rchild; int x;/*樹(shù)的x坐標(biāo)*/ int y;/*樹(shù)的y坐標(biāo)*/Tree;struct OUTPUT int x;/*三種遍歷的x坐標(biāo)*/ int y;/*三種遍歷的y坐標(biāo)*/ int num;s;int nodeNUM=0;/*統(tǒng)計(jì)當(dāng)前的結(jié)點(diǎn)數(shù)字,最多26個(gè)*/char way;/*自動(dòng)建立樹(shù)和手動(dòng)建立樹(shù)的標(biāo)志,2手動(dòng),1自動(dòng)*/char str3;/*顯示結(jié)點(diǎn)數(shù)據(jù)的字符串*/void Init();/*圖形初始化*/void Close();/*圖形關(guān)閉*/Tree *CreatTree();/*文本模式下創(chuàng)建樹(shù)的過(guò)程*/Tree *InitTree(int h,int t,int w);/*創(chuàng)建樹(shù),h層次,t橫坐標(biāo),w樹(shù)之間的寬度,n樹(shù)的建立方式*/void DrawTree(Tree *t);/*用圖形顯示創(chuàng)建好的樹(shù)*/void Preorder(Tree *t);/*前序遍歷*/void Midorder(Tree *t);/*中序遍歷*/void Posorder(Tree *t);/*后序遍歷*/void DrawNode(Tree *t,int color);/*遍歷時(shí)顯示每個(gè)結(jié)點(diǎn)的過(guò)程*/void ClrScr();/*清空樹(shù)的區(qū)域*/void main() Tree *root; randomize(); root=CreatTree();/*創(chuàng)建樹(shù)*/ Init(); DrawTree(root);/*每次遍歷前顯示白色的樹(shù)*/ sleep(1); s.x=100;s.y=300;s.num=1;/*每次遍歷前設(shè)置顯示遍歷順序顯示的x,y坐標(biāo)*/ Preorder(root);/*前序遍歷*/ getch(); ClrScr(); DrawTree(root); sleep(1); s.x=100; s.y=350; s.num=1; Midorder(root);/*中序遍歷*/ getch(); ClrScr(); DrawTree(root); sleep(1); s.x=100; s.y=400; s.num=1; Posorder(root);/*后序遍歷*/ Close();/*清空樹(shù)的區(qū)域*/void ClrScr() setcolor(BLACK); setfillstyle(SOLID_FILL,BLACK); bar(0,20,640,280);/*文本模式下創(chuàng)建樹(shù)的過(guò)程*/Tree *CreatTree() Tree *root; clrscr(); printf(please input nn); printf(1.computer creatn); printf(2.people creatn); way=getch();/*輸入創(chuàng)建樹(shù)的方法,1電腦自動(dòng)建立,2人工手動(dòng)建立*/ if(way!=2) way=1;/*其他數(shù)字默認(rèn)自動(dòng)建立*/ if(way=2)/*手動(dòng)建立提示輸入結(jié)點(diǎn)*/ printf(Please creat the treen); root=InitTree(1,320,150); system(pause); return root;/*生成二叉樹(shù)，h表示層次，t表示橫坐標(biāo)，w表示結(jié)點(diǎn)左右子樹(shù)的寬度，隨機(jī)數(shù)n確定結(jié)點(diǎn)是空或非空，如n為0，則為空*，但要限定確保結(jié)點(diǎn)數(shù)不少于三個(gè)*/Tree *InitTree(int h,int t,int w) char ch; int n;/*自動(dòng)建立時(shí)隨機(jī)賦值判斷是否是NULL的標(biāo)志*/ Tree *node; if(way=2)/*手動(dòng)建立需要自己輸入*/ scanf(%c,&ch); else/*自動(dòng)建立的賦值*/ n=random(5); if(n=0&nodeNUM=3)/*隨機(jī)賦值時(shí)候確保自動(dòng)建立的二叉樹(shù)有三個(gè)結(jié)點(diǎn)*/ ch=.; else ch=65+random(25); if(ch=.)/*輸入空格代表NULL*/ return NULL; else if(h=6|nodeNUM=26)/*如果樹(shù)的層次已經(jīng)到5或者結(jié)點(diǎn)樹(shù)到達(dá)26個(gè)就自動(dòng)返回NULL*/ return NULL; node=(Tree*)malloc(sizeof(Tree); node-data=ch; node-x=t;/*樹(shù)的x坐標(biāo)是傳遞過(guò)來(lái)的橫坐標(biāo)*/ node-y=h*50;/*樹(shù)的y坐標(biāo)與層次大小有關(guān)*/ nodeNUM+; node-lchild=InitTree(h+1,t-w,w/2); node-rchild=InitTree(h+1,t+w,w/2); return node;/*用圖形顯示創(chuàng)建好的樹(shù)*/void DrawTree(Tree *t) if(t!=NULL) setcolor(BLACK); setfillstyle(SOLID_FILL,BLACK); fillellipse(t-x,t-y,9,9); setcolor(WHITE); circle(t-x,t-y,10); /*畫圓*/ sprintf(str,%c,t-data);/*將內(nèi)容轉(zhuǎn)換成字符串輸出*/ outtextxy(t-x-3,t-y-2,str); if(t-lchild!=NULL)/*左子樹(shù)*/ line(t-x-5,t-y+12,t-lchild-x+5,t-lchild-y-12); DrawTree(t-lchild); if(t-rchild!=NULL)/*右子樹(shù)*/ line(t-x+5,t-y+12,t-rchild-x-5,t-rchild-y-12); DrawTree(t-rchild); /*遍歷時(shí)顯示每個(gè)結(jié)點(diǎn)的過(guò)程*/void DrawNode(Tree *t,int color) setcolor(YELLOW); setfillstyle(SOLID_FILL,YELLOW); fillellipse(t-x,t-y,10,10); setcolor(RED); sprintf(str,%c,t-data);/*將內(nèi)容轉(zhuǎn)換成字符串輸出*/ outtextxy(t-x-3,t-y-2,str); setcolor(color); outtextxy(s.x,s.y,str); setcolor(RED); sprintf(str,%d,s.num);/*將遍歷次序用數(shù)字顯示在樹(shù)的結(jié)點(diǎn)上*/ outtextxy(t-x-3,t-y-20,str); s.num+; sleep(1);/*前序遍歷*/void Preorder(Tree *t) if(t!=NULL) s.x+=15; DrawNode(t,GREEN); Preorder(t-lchild); Preorder(t-rchild); /*中序遍歷*/void Midorder(Tree *t) if(t!=NULL) Midorder(t-lchild); s.x+=15; DrawNode(t,YELLOW); Midorder(t-rchild); /*后序遍歷*/void Posorder(Tree *t) if(t!=NULL) Posorder(t-lchild); Posorder(t-rchild); s.x+=15; DrawNode(t,BLUE); /*圖形初始化*/void Init() int gd=DETECT,gm; initgraph(&gd,&gm,c:tc); cleardevice(); setcolor(YELLOW); outtextxy(250,10,anykey to continue); setcolor(RED); outtextxy(20,300,preorder); outtextxy(20,350,midorder); outtextxy(20,400,posorder); getch(