第一章1.1數(shù)據(jù)構(gòu)造課程設(shè)計規(guī)定。1.1.1數(shù)據(jù)構(gòu)造課程設(shè)計問題描述。從鍵盤讀入一組數(shù)據(jù)，建立二叉排序樹并對其進行查找、遍歷、格式化打印等有關(guān)操作。1.1.2數(shù)據(jù)構(gòu)造課程設(shè)計基本規(guī)定。建立二叉排序樹并對其進行查找，包括成功和不成功兩種狀況，并給出查找長度。1.2.1數(shù)據(jù)構(gòu)造課程設(shè)計測試數(shù)據(jù)。由學生根據(jù)軟件工程的測試技術(shù)自己確定。注意測試邊界數(shù)據(jù)。1.2.2數(shù)據(jù)構(gòu)造課程設(shè)計的選作內(nèi)容。實現(xiàn)二叉排序樹的插入、刪除操作。第二章2.1數(shù)據(jù)構(gòu)造課程設(shè)計的算法思想。為了實現(xiàn)任務(wù)書的幾種規(guī)定，本次課程設(shè)計的算法思想重要包括如下三部分。2.1.1主菜單設(shè)計。為了以便對二叉排序樹的基本操作，設(shè)計一種包括多種菜單項選擇項的主菜單以實現(xiàn)對二叉排序樹的各個操作。本系統(tǒng)的主菜單界面如圖1所示。圖1.二叉排序樹操作的主菜單2.1.2存儲構(gòu)造的設(shè)計。本程序重要采用二叉樹構(gòu)造類型來表達二叉排序樹。其中二叉樹節(jié)點由1個表達關(guān)鍵字的key表達，尚有指向該左孩子和右孩子的指針，通過key<p->key的if語句來判斷，其中p表達二叉排序樹。2.2.1系統(tǒng)功能的設(shè)計。本程序設(shè)置了5個子功能菜單，其設(shè)計如下。（1)建立二叉排序樹。重要通過BstreeCreate()函數(shù)來實現(xiàn)。根據(jù)系統(tǒng)提醒，輸入節(jié)點的關(guān)鍵字，二叉樹上面的各個元素，并以-1作為結(jié)束的標識符。（2)往二叉樹當中插入數(shù)據(jù)。重要通過BstreeInsert(y)函數(shù)實現(xiàn)。While語句對二叉樹狀態(tài)的判斷，通過key<p->key，以及key==p->key，對二叉樹的左右之樹進行定義，其中p表達二叉排序樹，每次只可以插入一種新的數(shù)據(jù)，不能插入已經(jīng)存在的元素。（3)二叉樹當中查找某數(shù)據(jù)。重要通過BstreeSearch()函數(shù)實現(xiàn)。每次進行查詢，成功則顯示“查詢到該節(jié)點”，不成功則“顯示查詢不到該節(jié)點，通過if語句對結(jié)點在二叉樹當中左右子樹進行判斷。（4)遍歷該二叉排序樹。重要通過voidTraverse()函數(shù)實現(xiàn)。遍歷二叉排序樹可以顯示該二叉排序樹的所有節(jié)點信息。假如一開始沒有發(fā)明二叉樹，還會提醒你先創(chuàng)立樹在進行遍歷。（5)刪除二叉排序樹當中某個數(shù)據(jù)。重要通過BstreeDelete()函數(shù)實現(xiàn)?？梢詫Χ媾判驑渲胁恍枰墓?jié)點進行刪除，通過對輸入關(guān)鍵字的查找進行刪除的操作，重要運用了隊列的知識，頭尾指針的定義來查找有關(guān)的數(shù)據(jù)。（6）樹狀打印二叉排序樹。重要通過voidTranslevelPrint(Bstreebt)函數(shù)實現(xiàn)。通過隊列當中的頭尾指針定義到樹的結(jié)點以及結(jié)點所在的層次。從而確定打印之后結(jié)點應當?shù)降奈恢谩hile語句重要對結(jié)點深度進行橫向控制，使打印圖形比較美觀。從而樹狀輸出你定義的二叉排序樹。第三章3.1模塊劃分。3.1.1主程序與子程序之間的對應關(guān)系。本程序重要分為兩部分：主程序模塊以及二叉樹各個操作模塊。主程序模塊——————>二叉樹各個操作模塊圖2.本設(shè)計當中主程序與子程序之間的重要調(diào)用關(guān)系注釋：(1) BstreeCreate()；//創(chuàng)立二叉排序樹(2)BstreeInsert(Bstreetree,intkey)；//插入(3)BstreeSearch(Bstreetree,intkey)；//查找(4)voidTraverse(Bstreetree)；//遍歷(5)BstreeDelete(Bstreetree,intkey)；//刪除信息（6）voidTranslevelPrint(Bstreebt)；//樹狀打印輸出3.1.2子程序的詳細設(shè)計如下：（1）BstreeCreate二叉排序樹的創(chuàng)立函數(shù)，重要用來創(chuàng)立二叉樹進而進行操作。BstreeCreate(){intkey; Bstreetree=NULL;//初始化空樹 scanf("%d",&key); while(key!=0)//假如二叉排序樹非空 { tree=Insert(tree,key);//插入根節(jié)點 scanf("%d",&key); } returntree;}//初始化創(chuàng)立二叉排序樹（2）BstreeInsert(Bstreetree,intkey)二叉排序樹的插入函數(shù)，重要用來對二叉樹插入某個元素的操作。BstreeInsert(Bstreetree,intkey){ Bstreep=tree;//二叉樹用P表達 Bstrees,f; while(p!=NULL)//判斷二叉排序樹與否為空 { f=p; if(key==p->key)returntree; if(key<p->key)p=p->lchild; elsep=p->rchild;//判斷是二叉排序樹的左孩子還是右孩子 } s=(Bstree)malloc(sizeof(Bstnode)); s->key=key; s->lchild=NULL; s->rchild=NULL; if(tree==NULL)returns;//新節(jié)點為二叉排序樹的根 if(key<f->key)f->lchild=s; elsef->rchild=s; returntree;}//往二叉樹當中插入數(shù)據(jù)（3）BstreeSearch(Bstreetree,intkey)二叉排序樹的查詢函數(shù)，重要用來對二叉樹當中的元素進行查詢。BstreeSearch(Bstreetree,intkey){ Bstreep=tree;intflag=0;while(p!=NULL) { if(p->key==key)//假如二叉樹當中存在所要尋找的結(jié)點 { printf("查詢到該節(jié)點！"); flag=1; return(p); break; } if(key<p->key)p=p->lchild;//往二叉樹左孩子處查找 elsep=p->rchild;//往二叉樹右孩子處查找 } if(flag==0) { printf("查詢不到關(guān)鍵字為%d的節(jié)點！",key); //returnNULL; }}//查找二叉樹當中某個元素與否存在（4）voidTraverse(Bstreetree)二叉排序樹的遍歷函數(shù)，重要用來對二叉排序樹的遍歷。inti=1;//防止遞歸時多次輸出做得標志voidTraverse(Bstreetree){ if(tree==NULL&&i)//假如樹為空不存在 { printf("請先創(chuàng)立二叉樹，在進行遍歷操作!"); return; } if(tree) { i=0; Traverse(tree->lchild);//遍歷二叉樹的左孩子 printf("%4d",tree->key); Traverse(tree->rchild);//遍歷二叉樹的右孩子 }}//遍歷二叉排序樹（5）BstreeDelete(Bstreetree,intkey)二叉排序樹的刪除函數(shù)，重要用來對二叉排序樹當中某個元素進行刪除。BstreeDelete(Bstreetree,intkey){ Bstreep=tree;Bstreef,s,q;f=NULL; while(p) {//查找關(guān)鍵字為key的節(jié)點 if(p->key==key)break; f=p; if(p->key>key)p=p->lchild; elsep=p->rchild; } if(p==NULL)returntree; if((p->lchild==NULL)||(p->rchild==NULL))//假如二叉排序樹的左右孩子一方為空 { if(f==NULL) if(p->lchild==NULL)tree=p->rchild;//假如左孩子為空，則查找右孩子 elsetree=p->lchild; elseif(p->lchild==NULL) if(f->lchild==p)f->lchild=p->rchild; elsef->rchild=p->rchild; elseif(f->lchild==p)f->lchild=p->lchild; elsef->lchild=p->lchild; free(p); } else{ q=p;s=p->lchild; while(s->rchild) { q=s;s=s->rchild; } if(q==p)q->lchild=s->lchild; p->key=s->key; free(s); }//查找到所要刪除的元素 returntree;}//刪除二叉樹當中某一種數(shù)據(jù)（6）voidTranslevelPrint(Bstreebt)二叉排序樹的打印函數(shù)，重要用來對二叉排序樹進行樹狀打印輸出。voidTranslevelPrint(Bstreebt) {//本算法實現(xiàn)二叉樹的按層打印 structnode { Bstreevec[MAXLEN]; //寄存樹結(jié)點 intlayer[MAXLEN]; //結(jié)點所在的層 intlocate[MAXLEN]; //打印結(jié)點的位置 intfront,rear; }q; //定義隊列q inti,j=1,k=0,nLocate; q.front=0;q.rear=0; //初始化隊列q隊頭，隊尾 printf(""); q.vec[q.rear]=bt; //將二叉樹根結(jié)點如隊列 q.layer[q.rear]=1; q.locate[q.rear]=20; q.rear=q.rear+1; while(q.front<q.rear) { bt=q.vec[q.front]; i=q.layer[q.front]; nLocate=q.locate[q.front]; if(j<i) //進層打印時換行 { printf("\n\n\t");printf("\n\n"); j=j+1;k=0; while(k<nLocate) { printf("");k++; } } while(k<(nLocate+3))//運用結(jié)點深度控制橫向位置 { printf("");k++; } printf("%d",bt->key); q.front=q.front+1; if(bt->lchild!=NULL)//寄存在左子樹，將左子樹根結(jié)點如隊列 { q.vec[q.rear]=bt->lchild; q.layer[q.rear]=i+1; q.locate[q.rear]=(int)(nLocate-pow(2,NLAYER-i)); q.rear=q.rear+1; } if(bt->rchild!=NULL)//寄存右子樹，將右子樹根結(jié)點入隊列 { q.vec[q.rear]=bt->rchild; q.layer[q.rear]=i+1; q.locate[q.rear]=(int)(nLocate+pow(2,NLAYER-i)); q.rear=q.rear+1; } }//樹狀打印輸出二叉排序樹第四章4.1數(shù)據(jù)構(gòu)造4.1.1數(shù)據(jù)類型定義對二叉排序樹的存儲類型定義如下：typedefstructBstnode{ intkey; structBstnode*lchild,*rchild;}Bstnode,*Bstree;4.1.2詳細問題得數(shù)據(jù)類型定義。(1)/*創(chuàng)立二叉排序樹*/BstreeCreate(){intkey;Bstreetree=NULL;}returntree;(2)/*往二叉樹當中插入數(shù)據(jù)*/BstreeInsert(Bstreetree,intkey){ Bstreep=tree;//二叉樹用P表達 Bstrees,f;}returntree(3)/*查找二叉樹當中某個元素與否存在*/BstreeSearch(Bstreetree,intkey){ Bstreep=tree;intflag=0;}returntree(4)/*刪除二叉樹當中某一種數(shù)據(jù)*/BstreeDelete(Bstreetree,intkey){ Bstreep=tree;Bstreef,s,q;}returntree(5)/*打印二叉排序樹*/structnode { Bstreevec[MAXLEN]; //寄存樹結(jié)點 intlayer[MAXLEN]; //結(jié)點所在的層 intlocate[MAXLEN]; //打印結(jié)點的位置 intfront,rear; }q; returntree4.2源程序的清單（*****見匯報附頁）第五章5.1測試數(shù)據(jù)及其狀況。創(chuàng)立二叉排序樹18，19,10,4,23,29,1,14對編寫好的程序進行測試與否到達了課程設(shè)計的規(guī)定。5.1.1二叉樹的創(chuàng)立。圖1：按照屏幕提醒輸入18，19,10,4,23,29,1,14創(chuàng)立二叉排序樹，以0結(jié)束。圖2：往二叉樹當中插入5。圖3二叉樹當中找到結(jié)點5.圖4.對二叉樹進行遍歷。圖5.刪除二叉樹當中5這個元素。圖6.樹狀打印輸出二叉排序樹。通過試驗成果可以發(fā)現(xiàn)，測試成果符合課程設(shè)計匯報書的規(guī)定，到達了試驗的預期目的。從鍵盤讀入一組數(shù)據(jù)，建立二叉排序樹并對其進行查找、遍歷、格式化打印等有關(guān)操作。建立二叉排序樹并對其進行查找，包括成功和不成功兩種狀況，并給出查找長度。還能實現(xiàn)二叉排序樹的插入、刪除操作。課程設(shè)計圓滿完畢！第六章6.1總結(jié)和體會。通過查閱資料以及請假同學之后，可以通過C語言程序的編寫對從鍵盤輸入的一組數(shù)據(jù)，建立二叉排序樹并對其進行查找、遍歷、格式化打印等操作，查找過程當中還能進行判斷，包括成功不成功兩種狀況，并給出其長度，還完畢了二叉樹的插入，刪除等選作內(nèi)容。通過typedefstructBstnode函數(shù)，可以對二叉樹進行存儲類型的定義。以及/*創(chuàng)立二叉排序樹*/BstreeCreate()；/*插入數(shù)據(jù)*/BstreeInsert(Bstreetree,intkey)；/*二叉樹當中查找數(shù)據(jù)*/BstreeSearch(Bstreetree,intkey)；/*遍歷二叉排序樹素*/voidTraverse(Bstreetree)；/*刪除二叉排序樹當中的數(shù)據(jù)*/BstreeDelete(Bstreetree,intkey)；/*樹狀打印輸出二叉排序樹voidTranslevelPrint(Bstreebt)；等函數(shù)的應用。多次運用到了隊列的頭尾指針的知識，也有助于這以便內(nèi)容得掌握。懂得了各個操作的編程的構(gòu)成要素。通過這次的試驗，我認識到：理論與實際結(jié)合的重要性。在實際操作時，常常碰到過某些問題，程序語句的不規(guī)范，語句語法的錯誤啊，自己看不懂，更無法處理。不過，通過自己不停的思索，嘗試著去處理代碼中出現(xiàn)的問題。雖然開始很困難，但在老師和同學的協(xié)助下，我逐漸的熟悉了許多操作，為后繼工作的順利進行做了準備。也許，我們可以說，編一種程僅僅是開始，調(diào)試和運行相比之下更難。實踐中收獲的遠比想象的多。通過這次試驗通過VisualC++這個平臺，也愈加激發(fā)了我們對于數(shù)據(jù)構(gòu)造這門課程的學習愛好。未來在數(shù)據(jù)構(gòu)造的學習上面我們也將愈加深入的去探索爭取獲得更多的進步！附錄：數(shù)據(jù)構(gòu)造課程設(shè)計源程序#include<malloc.h>#include<stdio.h>#include<stdlib.h>#include<malloc.h>#include<math.h>#defineMAXLEN100#defineNLAYER3typedefstructBstnode{ intkey; structBstnode*lchild,*rchild;}Bstnode,*Bstree;//二叉樹的數(shù)據(jù)構(gòu)造BstreeCreate();//創(chuàng)立二叉排序樹BstreeInsert(Bstreetree,intkey);//插入數(shù)據(jù)BstreeSearch(Bstreetree,intkey);//查找數(shù)據(jù)voidTraverse(Bstreetree);//遍歷二叉樹BstreeDelete(Bstreetree,intkey);//刪除數(shù)據(jù)voidTranslevelPrint(Bstreebt);//樹狀打印BstreeCreate(){intkey; Bstreetree=NULL;//初始化空樹 scanf("%d",&key);//假如二叉排序樹非空 while(key!=0) { tree=Insert(tree,key);//插入節(jié)點 scanf("%d",&key); } returntree;}//創(chuàng)立二叉排序樹 while(p!=NULL)//判斷二叉排序樹與否為空 { f=p; if(key==p->key)returntree; if(key<p->key)p=p->lchild; elsep=p->rchild;//判斷是二叉排序樹的左孩子還是右孩子 } s=(Bstree)malloc(sizeof(Bstnode)); s->key=key; s->lchild=NULL; s->rchild=NULL; if(tree==NULL)returns;//新節(jié)點為二叉排序樹的根 if(key<f->key)f->lchild=s; elsef->rchild=s; returntree;}//往二叉樹當中插入數(shù)據(jù)BstreeSearch(Bstreetree,intkey){ Bstreep=tree;intflag=0;while(p!=NULL) { if(p->key==key)//假如二叉樹當中存在所要尋找的結(jié)點 { printf("查詢到該節(jié)點！"); flag=1; return(p); break; } if(key<p->key)p=p->lchild;//往二叉樹左孩子處查找 elsep=p->rchild;//往二叉樹右孩子處查找 } if(flag==0) { printf("查詢不到關(guān)鍵字為%d的節(jié)點！",key); //returnNULL; }}//查找二叉樹當中某個元素與否存在inti=1;//防止遞歸時多次輸出做得標志voidTraverse(Bstreetree){ if(tree==NULL&&i)//假如樹為空不存在 { printf("請先創(chuàng)立二叉樹，在進行遍歷操作!"); return; } if(tree) { i=0; Traverse(tree->lchild);//遍歷二叉樹的左孩子 printf("%4d",tree->key); Traverse(tree->rchild);//遍歷二叉樹的右孩子 }}//遍歷二叉排序樹BstreeDelete(Bstreetree,intkey){ Bstreep=tree;Bstreef,s,q;f=NULL; while(p) {//查找關(guān)鍵字為key的節(jié)點 if(p->key==key)break; f=p; if(p->key>key)p=p->lchild; elsep=p->rchild; } if(p==NULL)returntree; if((p->lchild==NULL)||(p->rchild==NULL))//假如二叉排序樹的左右孩子一方為空 { if(f==NULL) if(p->lchild==NULL)tree=p->rchild;//假如左孩子為空，則查找右孩子 elsetree=p->lchild; elseif(p->lchild==NULL) if(f->lchild==p)f->lchild=p->rchild; elsef->rchild=p->rchild; elseif(f->lchild==p)f->lchild=p->lchild; elsef->lchild=p->lchild; free(p); } else{ q=p;s=p->lchild; while(s->rchild) { q=s;s=s->rchild; } if(q==p)q->lchild=s->lchild; p->key=s->key; free(s); }//查找到所要刪除的元素 returntree;}//刪除二叉樹當中某一種數(shù)據(jù)voidTranslevelPrint(Bstreebt) {//本算法實現(xiàn)二叉樹的按層打印 structnode { Bstreevec[MAXLEN]; //寄存樹結(jié)點 intlayer[MAXLEN]; //結(jié)點所在的層 intlocate[MAXLEN]; //打印結(jié)點的位置 intfront,rear; }q; //定義隊列q inti,j=1,k=0,nLocate; q.front=0;q.rear=0; //初始化隊列q隊頭，隊尾 printf(""); q.vec[q.rear]=bt; //將二叉樹根結(jié)點如隊列 q.layer[q.rear]=1; q.locate[q.rear]=20; q.rear=q.rear+1; while(q.front<q.rear) { bt=q.vec[q.front]; i=q.layer[q.front]; nLocate=q.locate[q.front]; if(j<i) //進層打印時換行 { printf("\n\n\t");printf("\n\n"); j=j+1;k=0; while(k<nLocate) { printf("");k++; } } while(k<(nLocate+3))//運用結(jié)點深度控制橫向位置 { printf("");k++; } printf("%d",bt->key); q.front=q.front+1; if(bt->lchild!=NULL)//寄存在左子樹，將左子樹根結(jié)點如隊列 { q.vec[q.rear]=bt->lchild; q.layer[q.rear]=i+1; q.locate[q.rear]=(int)(nLocate-pow(2,NLAYER-i)); q.rear=q.rear+1; } if(bt->rchild!=NULL)//寄存右子樹，將右子樹根結(jié)點入隊列 { q.vec[q.rear]=bt->rchild; q.layer[q.rear]=i+1; q.locate[q.rear]=(int)(nLocate+pow(2,NLAYER-i)); q.rear=q.rear+1; } }//樹狀打印輸出二叉排序樹voidmain(){ Bstreetree,p; intkey1,key2,key3; intselect,flag; printf("———————斯樂兵的二叉排序樹———————\n"); printf("菜單\n"); printf("1.創(chuàng)立二叉排序樹\n"