1、 中 北 大 學課程設計說明書學 院、系：軟件學院專 業(yè)：軟件工程班 級：15140X04學 生 姓 名：張航學 號：1514040423設 計 題 目：線索二叉樹的應用 起 迄 日 期: 2016年12月16日2016年12月29日指 導 教 師:付東來日期: 2016年12月29日1 設計目的 數據結構課程主要介紹最常用的數據結構，闡明各種數據結構內在的邏輯關系，討論其在計算機中的存儲表示，以及在其上進行各種運算時的實現算法，并對算法的效率進行簡單的分析和討論。進行數據結構課程設計要達到以下目的：n 了解并掌握數據結構與算法的設計方法，具備初步的獨立分析和設計能力；n 初步掌握軟件開發(fā)過程

2、的問題分析、系統設計、程序編碼、測試等基本方法和技能；n 提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力；訓練用系統的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā)，培養(yǎng)軟件工作者所應具備的科學的工作方法和作風。2 任務概述設計內容： （1）建立線索二叉樹，實現插入、刪除操作。 （2）線索二叉樹的遍歷（本程序中使用中序遍歷方法）設計要求： 實現線索樹建立、插入、刪除、恢復線索任務分析：該任務是關于線索二叉樹的運算，其中的基本運算應基于二叉樹，但又有所不同，首先應了解問題有：（1）線索二叉樹如何建立：是通過二叉樹來實現線索化，還是直接進行線索化的輸入。若由二叉樹建立而來，該二叉樹應如何輸入，對具體

3、的二叉樹應該使初次使用者明白使用的格式。（2）該程序重點內容是有關二叉樹的插入、刪除和查找前驅后繼，在進行具體操作時，該如何實現查找到相應結點，線索應該如何改變才能不破壞線索二叉樹的結構。重點在于插入刪除是分清楚插入刪除位置的雙親結點與被插入刪除的結點的孩子關系。3 模塊劃分（1）定義數據結構模塊：typedef struct BiThrNodeElemType data;struct BiThrNode *lchild,*rchild;int LTag,RTag; BiThrNode,*BiThrTree;（2）功能函數：二叉樹的建立函數：void CreateBiTree(BiThrTre

4、e &T)詢二叉樹深度函數：int Depth(BiThrTree T)帶頭結點的二叉樹中序線索化函數：void InOrderThreading(BiThrTree &Thrt,BiThrTree T)以結點T為根的子樹中序線索化：void InThreading(BiThrTree &T)中序遍歷函數：void InOrderTraverse_Thr(BiThrTree Thrt)查找某結點函數：BiThrTree Search(BiThrTree T,ElemType key)查找某結點函數：BiThrTree SearchPre(BiThrTree point,

5、BiThrTree child) 插入函數：Status InsertTree(BiThrTree T)刪除函數：Status DeleteTree(BiThrTree T)主函數：main()整體結構圖： 開 始 創(chuàng)建二叉樹 線索化二叉樹 Main( )打印二叉樹插入結點刪除結點4 主要函數說明及其N-S圖4.1詳細設計思想建立二叉樹（即指在內存中建立二叉樹的存儲結構），建立一個二叉鏈表，需按某種順序一次輸入二叉樹中的結點，且輸入順序必須隱含結點間的邏輯結構信息。對于一般的二叉樹，需添加虛結點，使其成為完全二叉樹。二叉樹的中序線索化算法與中序遍歷算法類似。只需要將遍歷算法中訪問結點的操作具體

6、化為建立正在訪問的結點與其非空中序前趨結點間線索。該算法應附設一個指針pre始終指向剛剛訪問過的結點（pre的初值應為NULL），而指針p指示當前正在訪問的結點。結點*pre是結點*p的前趨，而*p是*pre的后繼。結點插入算法：由線索二叉樹的定義易知插入的節(jié)點定是個葉子節(jié)點，需注意線索的修改，可分為兩種情況：（1）：插入的節(jié)點t是右兒子，t的中序后繼是其父親的中序后繼，中序前驅是其父親。（2）：插入的節(jié)點t是左兒子，t的中序前驅是其父親的中序前驅，中序后繼是其父親。結點刪除算法：刪除的情況與搜索二叉樹的刪除的類似（1）：刪除的節(jié)點p是葉子節(jié)點，直接刪除，修改其父親的線索。（2）：刪除的節(jié)點p

7、有一個兒子，p有一個左兒子，以p為根的左子樹中的具有最大值節(jié)點的t中序后繼是p的中序后繼，中序前驅不變；p有一個右兒子，以p為根的右子中的具有最小值節(jié)點t中序前驅是p的中序前驅，中序后繼不變。（3）：刪除的節(jié)點p有二個兒子，轉化為葉子節(jié)點或只有一個兒子節(jié)點的刪除。4.2各功能函數流程圖圖4.1 ：創(chuàng)建二叉樹圖4.2 ：查詢二叉樹深度圖4.3 ：中序線索化二叉樹圖4.4 ：中序遍歷輸出二叉樹圖4.5 ：查詢結點圖4.6 ：查詢結點的雙親結點圖4.7 ：插入結點圖4.8 ：刪除結點5 程序運行數據及其結果1_按中序輸入一課二叉樹，建樹并實現線索化2_建樹完成后進入主菜單，可執(zhí)行相應插入、刪除、打印

8、操作3_選擇操作1，以中序遍歷輸出線索二叉樹4_選擇操作2，在線索二叉樹中插入新結點5_選擇操作3，刪除二叉樹中的結點6 課程設計心得通過這次做課程設計，發(fā)現了學習中的很多問題，平時學習的東西在做起來時有很大的困難，獨立構思一個程序很難，不僅僅是要實現某個功能，而且還要把這些功能結合起來，成為一個能良好運行的程序，需要對錯誤輸入提示，需要排除debug，需要設計每個使用界面等等。剛開始的時候是先寫了一部分代碼，后來就發(fā)覺應該先把函數的功能需要弄清楚，整理出一個大框架。再此基礎上完善程序的功能。這次的線索二叉樹的插入和刪除課本上沒有相應的內容，為了完成課設，在網絡上一直翻看別人的博客，先看明白思

9、想，在盡量看懂人家的代碼。最后是借鑒了別人的思想，自己畫圖，才把代碼實現出來。其間廢了好大的力氣。而且雖說是實現了，但函數的語句還是顯得有些亂，自己為了看懂還加了一大堆注釋。不便于和同學交流。一直以來，覺得自己數據結構學的還行，起碼概念那些都能理解，知道說了些什么，也大致知道怎么個原理，考完試也感覺良好，但是一到課程設計，看的題目挺簡單，二叉樹，可是一去上手做了去無從下手，一點都不會，只會紙上談兵，我也知道變成這東西是需要多實踐的，但沒想到真的坐到那兒去編時，卻怎么也下不了手，于是很失落的回宿舍查閱書籍以及上網百度資料，仔細的參讀了很長時間后，自己不停的磨合，終于完成個大概，不可避免調試中又出

10、些問題，經過好幾遍的查錯，一點一點的改，最終終于完成現在的程序。 通過這段時間的課程設計，我認識到數據結構是一門比較難的課程，但同時有時一門基礎切極為重要的課程。需要多花時間上機練習。這次的程序訓練培養(yǎng)了我實際分析問題、編程和動手能力，使我掌握了程序設計的基本技能，提高了我適應實際，實踐編程的能力。 總的來說，這次課程設計讓我獲益匪淺，對數據結構也有了進一步的理解和認識。附錄：#include<stdio.h> #include<stdlib.h>#include<math.h>#include<windows.h>/windows自帶函數庫：S

11、leep()函數 #define ERROR 0#define OK 1typedef char ElemType;/二叉樹結點數據域可隨時修改數據類型 typedef int Status;typedef struct BiThrNode/二叉樹的存儲結構 ElemType data;struct BiThrNode *lchild,*rchild;int LTag,RTag;BiThrNode,*BiThrTree;/BiThrTree用來聲明指針類型變量 static BiThrTree pre = (BiThrTree)malloc(sizeof(BiThrNode);void Cre

12、ateBiTree(BiThrTree &T)/前序創(chuàng)建 char ch;ch = getchar();if(ch = '#') T = NULL;elseT = (BiThrTree)malloc(sizeof(BiThrNode);T->data = ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);void InThreading(BiThrTree &T)/以T為根節(jié)點的二叉樹線索化 if(T)InThreading(T->lchild);if(!(T->lchild)T-

13、>LTag = 1;T->lchild = pre;else T->LTag = 0;if(!(pre->rchild)/pre被定義為全局變量 pre->RTag = 1;pre->rchild = T;else T->RTag = 0;pre = T;InThreading(T->rchild);void InOrderThreading(BiThrTree &Thrt,BiThrTree T)/帶頭結點的二叉樹中序線索化 Thrt = (BiThrTree)malloc(sizeof(BiThrNode);Thrt->LTag

14、 = 0;Thrt->RTag = 1;Thrt->rchild = Thrt;if(!T) Thrt->lchild = Thrt;elseThrt->lchild = T;pre = Thrt;InThreading(T);pre->rchild = Thrt;pre->RTag = 1;Thrt->rchild = pre; void InOrderTraverse_Thr(BiThrTree Thrt)/中序遍歷線索二叉樹 BiThrTree p = (BiThrTree)malloc(sizeof(BiThrNode);p = Thrt-&g

15、t;lchild;printf("二叉樹中序遍歷結果為："); while(p!=Thrt)while(p->LTag=0) p = p->lchild;printf(" -> %c",p->data);while(p->RTag=1&&p->rchild!=Thrt)p = p->rchild;printf(" -> %c",p->data);p = p->rchild;puts("");/回車換行 BiThrTree Search(Bi

16、ThrTree T,ElemType key)/查找data = key 的結點 ,并返回該節(jié)點的指針地址 BiThrTree p = (BiThrTree)malloc(sizeof(BiThrNode);p = T->lchild;while(p!=T)while(p->LTag=0) p = p->lchild;if(p->data=key) return p;while(p->RTag =1&&p->rchild!=T)p = p->rchild;if(p->data=key) return p;p = p->rch

17、ild;return NULL;BiThrTree SearchPre(BiThrTree point,BiThrTree child) / 查找以point為根，child的雙親結點 BiThrTree p1,p2;if(point!=NULL)if(point->LTag!=1&&point->lchild=child)|(point->RTag!=1&&point->rchild=child) return point;/找到則返回elseif(point->LTag!=1) p1=SearchPre(point->lc

18、hild,child); if(p1!=NULL) return p1; if(point->RTag!=1) p2=SearchPre(point->rchild,child); if(p2!=NULL) return p2; return NULL; else return NULL; Status InsertTree(BiThrTree T)/線索二叉樹的插入函數 BiThrTree p = (BiThrTree)malloc(sizeof(BiThrNode);/新結點，要插入的結點 BiThrTree t ;/要插入結點的父母結點 ElemType key;int n

19、= 1,temp = 0;while(temp=0)n = 1;t = NULL;InOrderTraverse_Thr(T);/遍歷輸出線索二叉樹 printf("請輸入新結點的值：");scanf("%c",&(p->data);getchar(); printf("請問新結點的父母結點為：");scanf("%c",&key);getchar();printf("請問新結點是%c結點的左孩子or右孩子：(0-左,1-右)",key);while(1)/循環(huán)執(zhí)行 sca

20、nf("%d",&n);getchar(); if(n=0|n=1) break;puts("輸入的值應為0或1，請重新輸入！");t = Search(T,key);if(!t) puts("輸入的父母結點不存在于樹中，查找失?。?quot;); elseif(n = 0)/插入左子樹 p->RTag = 1;p->rchild = t;/父母結點的前驅p->LTag = t->LTag;p->lchild = t->lchild; t->LTag = 0;t->lchild = p;t

21、 = p;if(p->LTag=0)/找到p的左子樹的最右結點，改為自己前驅 p = p->lchild;while(p->RTag = 0)p = p->rchild;p->rchild = t;else/插入右子樹 p->LTag = 1;p->lchild = t;p->RTag = t->RTag;p->rchild = t->rchild;t->RTag = 0;t->rchild = p;t = p;if(p->RTag=0)p = p->rchild;while(p->LTag = 0

22、)p = p->lchild;p->lchild = t;printf("繼續(xù) 插入結點請按 0 返回主界面 請按1：");while(1)scanf("%d",&temp);getchar(); if(temp = 1) break;else if(temp = 0) break;else puts("輸入錯誤，應輸入0-繼續(xù)插入 1-主界面：");return OK;Status DeleteTree(BiThrTree T)/線索二叉樹的刪除函數 BiThrTree t,pre,save;/pre_待刪結點的

23、雙親，屏蔽了全局變量pre save_保留要刪除的結點，用以free(save); ElemType key;int n = -1,temp = 0;/temp 用來判斷是否循環(huán)，繼續(xù)使用刪除結點函數 while(temp = 0) InOrderTraverse_Thr(T);/遍歷輸出 printf("請輸入要刪除的結點：");scanf("%c",&key);getchar();t = Search(T,key);/在頭結點為T的樹中找到key結點的位置 if(!t) puts("所要刪除的結點不存在！");elsepr

24、e = SearchPre(T,t);save = t;if(t->LTag=1&&t->RTag=1)/要刪除的結點沒有孩子 if(pre->lchild=t)pre->LTag = t->LTag;pre->lchild = t->lchild;else if(pre->rchild=t)pre->RTag = t->RTag;pre->rchild = t->rchild;else puts("查找雙親結點可能有誤1");else if(t->LTag=1&&

25、t->RTag=0)/要刪除的結點僅有右孩子 if(pre->lchild=t)/被刪結點是雙親的左孩子 pre->lchild = t->rchild;pre = t;t = t->rchild;while(t->LTag=0) t = t->lchild;t->lchild = pre->lchild;else if(pre->rchild=t)/被刪結點是雙親的右結點 pre->rchild = t->rchild;t = t->rchild;while(t->LTag=0) t = t->lchi

26、ld;t->lchild = pre;else puts("查找雙親結點可能有誤2");else if(t->LTag=0&&t->RTag=1)/要刪除的結點僅有左孩子 if(pre->lchild=t)/被刪結點是雙親的左孩子pre->lchild = t->lchild;pre = t;pre = pre->lchild;/修改pre為待刪結點的左孩子 while(pre->RTag=0) pre = pre->rchild;pre->rchild = t->rchild;else if

27、(pre->rchild=t)/被刪結點是雙親的右孩子pre->rchild = t->lchild;pre = t;pre = pre->lchild;while(pre->RTag) pre = pre->rchild;pre->rchild = t->rchild;else puts("查找雙親結點可能有誤3");else/要刪除的結點有兩個孩子 if(pre->lchild=t)pre->lchild = t->lchild;/被刪除結點的左樹作為根節(jié)點 pre = t->lchild;/開始查

28、找t的前驅while(pre->RTag=0) pre = pre->rchild;pre->RTag = 0;pre->rchild = t->rchild;t = t->rchild;/開始查找t的后繼while(t->LTag=0) t = t->lchild;t->LTag = 1;t->lchild = pre; else if(pre->rchild=t)pre->rchild = t->lchild;pre = t->lchild;/開始查找t的前驅while(pre->RTag=0) pr

29、e = pre->rchild;pre->RTag = 0;pre->rchild = t->rchild;t = t->rchild;/開始查找t的后繼while(t->LTag=0) t = t->lchild;t->LTag = 1;t->lchild = pre; else puts("查找雙親結點可能有誤4");free(save);printf("繼續(xù)刪除結點 請按 0 返回主界面 請按1：");while(1)scanf("%d",&temp);getchar(); if(temp = 1) break;else if(temp = 0) break;else puts("輸入錯