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