數學與計算機學院
課程設計說明書
課程名稱: 資料結構與演算法課程設計
課程**6014389
題目: 線索二叉樹的應用
年級/專業/班: 2010級軟體1班
學生姓名
學號: 312010
開始時間: 2011 年 12 月 9 日
完成時間: 2011 年 12 月 23 日
課程設計成績：
指導教師簽名年月日
摘要首先是對需求分析的簡要闡述，說明系統要完成的任務和相應的分析，並給出測試資料。其次是概要設計，說明所有抽象資料型別的定義、主程式的流程以及各程式模組之間的層次關係，以及adt描述。然後是詳細設計，描述實現概要設計中定義的基本功操作和所有資料型別，以及函式的功能及**實現。
再次是對系統的除錯分析說明，以及遇到的問題和解決問題的方法。然後是使用者使用說明書的闡述，然後是測試的資料和結果的分析，最後是對本次課程設計的結論。
關鍵詞：線索化；先序遍歷；中序遍歷；後續遍歷
引言 資料結構是計算機專業重要的專業基礎課程與核心課程之一，在計算機領域應用廣泛，計算機離不開資料結構。資料結構課程設計為了能使我們掌握所學習的知識並有應用到實際的設計中的能力，對於掌握這門課程的學習方法有極大的意義。本課程設計的題目為「線索二叉樹的應用」，完成將二叉樹轉化成線索二叉樹，採用前序、中序或後序線索二叉樹的操作。
本課程設計採用的程式設計環境為microsoft visual stdio 2008。
目錄 1需求分析 3
2開發及執行平台 4
3 概要設計 5
4 詳細設計 7
5 除錯分析 12
6 測試結果 13
7 結論 18
致謝 19
參考文獻 20
附錄 21
1、需求分析
為了能更熟練精準的掌握二叉樹的各種演算法和操作，同時也為了開拓視野，綜合運用所學的知識。為此，需要將二叉樹轉化成線索二叉樹，採用前序、中序或後序線索二叉樹，以實現線索樹建立、插入、刪除、恢復線索等。
1.1任務與分析
中次系統要實現對二叉樹的建立，以及線索化該二叉樹，同時實現對其先序、中序、後序線索話的並輸出結果。
1.2測試資料
表1：入的二叉樹結點序號和資料
2開發及執行平台
開發平台：microsoft visual studio 2008
執行平台：windows xp/2003/7
3 概要設計
3.1 adt描述
adt bitree；
資料關係：r＝
若d=∮為空，則r=∮,tree為空樹；
若d僅有乙個資料元素，則r=∮；
否則r=詳細描述如下：
d中存在唯一的稱之為根的節點root，它在關係h下無前驅；
1. 若d-≠∮，則存在對根以外剩餘元素的乙個劃分d1、 d2......，dm（m>0），並對任意j≠k（1≦j≦m，1≦k≦m）有dj∩dk=∮；且對任意i（1≦i≦m）唯一存在資料元素xi∈di，有二元關係∈h。
這裡描述的是從總節點到各個子樹根節點xi的邊。
2. 對應於d-的劃分，關係集h-也有唯一的劃分h1、h2......hm(m>0)，並且對任意的j≠k（1≦j≦m，1≦k≦m）有hj∩hk=∮，對任意的i（1≦i≦m），hi是di上的二元關係，則（di，）是一顆樹，且是root的子樹。
基本操作：
void creat ();//建立乙個二叉樹。
void inorder ();//中序便利。
void thtree::threpreorder ();//先序遍歷二叉樹。
void thtree::threinorder ();//中序遍歷二叉樹。
void thtree::threpostorder ();//後序遍歷二叉樹。
void thtree::destroy ();//刪除線索二叉樹。
int main();//主函式。
}3.2程式模組結構
圖2 程式模組結構
3.2.1 結構體定義
書的結構體定義如下：
struct threnode定義結點結構體
;3.3 各功能模組
新建模組: void thtree::creat ()新建二叉樹並儲存。
樹類模組:void thtree ()定義書的結點，孩子以及各成員函式。
先序遍歷模組: void thtree::threpreorder ()對樹進行先序線索遍歷。
中序遍歷模組: void thtree::threinorder ()對樹進行中序線索遍歷。
後序遍歷模組: void thtree::threpostorder()對樹進行後序線索遍歷。
刪除模組: void thtree::destroy ()：刪除所有節點。
4 詳細設計
4.1結構體定義
樹的結構體定義如下：
struct threnode定義結點結構體
;4.2 初始化
建構函式初始化變數，定義雙親結點和左右標誌域以及根結點：
void thtree::creat建立二叉樹
cout<<"\ni,x=";cin>>i>>x;
}}4.3 新建操作
void thtree::creat建立二叉樹
cout<<"\ni,x=";cin>>i>>x;
}}void thtree::threpreorder(threnode *p,threnode *pre) //先根線索化二叉樹
{if(p!=null)
{cout if(p->lch==null){p->lch=pre; p->ltag=1; pre=p; if(p->ltag==0)threpreorder(p->lch,pre); threpreorder(p->rch,pre 4.4、錄入資訊 int main () { int k;thtree root0; do{cout<<"\n\n"; cout<<"\n\n1.建立二叉樹"; cout<<"\n\n2.中序遞迴線索二叉樹"; cout<<"\n\n3.先序線索化二叉樹 "; cout<<"\n\n4.後續線索化二叉樹"; 機械製造技術基礎 學生 學號 專業 班級 指導老師 2014年4月 目錄機械製造工藝學課程設計任務書1 一.零件分析2 一 零件作用2 二 零件的工藝分析2 二 確定毛坯4 一 確定毛坯種類4 二 確定鑄件加工餘量狀4 三 工藝規程設計4 一 基面的選擇4 二 制定工藝路線5 三 確定切削用量及時間... 實驗5 樹和二叉樹 一 實驗目的 1 掌握二叉樹的結構特徵，以及各種儲存結構的特點及適用範圍。2 掌握用指標型別描述 訪問和處理二叉樹的運算。二 實驗要求 1.認真閱讀和掌握本實驗的程式。2.上機執行本程式。3.儲存和列印出程式的執行結果，並結合程式進行分析。4.按照二叉樹的操作需要，重新改寫主程式... 指導教師 2014年12月22日 目錄第1章可調直流穩壓電源的製作與除錯 2 1.1 設計任務 2 1.1.1 設計目的 2 1.1.2 設計要求及技術指標 2 1.2 總體設計方案 2 1.2.1 直流穩壓電源的基本原理 2 1.3系統分析與設計 3 1.3.1 整流 濾波電路 3 1.3.2 電...撥叉課程設計說明書
樹和二叉樹實驗任務書
課程設計說明書