二叉樹遍歷的實(shí)現(xiàn)與教學(xué)演示畢業(yè)論文

上傳人：奔*** IP屬地：河北更新時(shí)間：2024-03-01 格式：doc 頁數(shù)：24 大?。?.33MB 人氣指數(shù)：12 舉報(bào) 版權(quán)申訴

二叉樹遍歷的實(shí)現(xiàn)與教學(xué)演示畢業(yè)論文_第1頁

已閱讀1頁，還剩23頁未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、　　本科生畢業(yè)論文(設(shè)計(jì))　　題目：二叉樹遍歷的實(shí)現(xiàn)與教學(xué)演示　　目錄　　摘要(關(guān)鍵字)1　　Abstract（Key words）1

2、　　前言2　　1 二叉樹的概述2　　1.1 二叉樹的定義2　　1.2 二叉樹的性質(zhì)3　　1.3 二叉樹的存儲(chǔ)結(jié)構(gòu)4　　2 二叉樹的遍歷6

3、　　2.1 常用的二叉樹遍歷的算法6　　2.2二叉樹遍歷的C程序演示過程9　　2.3 非遞歸遍歷二叉樹12　　2.4 二叉樹遍歷算法的應(yīng)用14　　3基于FLASH的二叉樹遍歷課件應(yīng)用實(shí)現(xiàn)15　　3.

4、1課件簡(jiǎn)介15　　3.2結(jié)構(gòu)設(shè)計(jì)分析15　　3.3主要功能16　　4 教學(xué)設(shè)計(jì)18　　結(jié)束語20　　參考文獻(xiàn)21</b

5、>　　致謝22　　二叉樹遍歷的實(shí)現(xiàn)與教學(xué)演示　　摘要: 　　所有數(shù)據(jù)結(jié)構(gòu)中，樹是非常重要的一種，尤其是二叉樹的遍歷，學(xué)習(xí)者是應(yīng)該牢固掌握的。在學(xué)習(xí)了二叉樹的存儲(chǔ)結(jié)構(gòu)之后，學(xué)生

6、開始接觸了二叉樹的遍歷。很多學(xué)生或多或少地會(huì)感到些困惑，看似簡(jiǎn)單的遞歸算法，可要理解其遍歷過程，未必能夠一目了然。其主要原因在于二叉樹的遍歷執(zhí)行過程較復(fù)雜，不容易理解，學(xué)生會(huì)會(huì)此失去興趣，因此針對(duì)如果進(jìn)行講解，學(xué)生在理解上也有一定的難度。本文對(duì)于二叉樹的遍歷執(zhí)行過程給予了直觀的教學(xué)演示，主要通過圖形的形式展示，可以一目了然，讓同學(xué)們對(duì)此不排斥，從而達(dá)預(yù)期的教學(xué)效果?？梢詮睦碚摻嵌瘸霭l(fā)，邊講解邊演示讓同學(xué)們聽懂、學(xué)會(huì)。還從信息技術(shù)與課程整

7、合的角度，制作FLASH課件應(yīng)用于教學(xué)中，提高教學(xué)質(zhì)量。從而更好的進(jìn)行課堂教學(xué)，使學(xué)生更清楚、更容易的理解二叉樹的遍歷過程。　　關(guān)鍵字：　　二叉樹; 遍歷; 多媒體　　Abstract:　　All

8、 of the data structure, the tree is a very important, especially in the binary tree traversal, learners should have a solid grasp of. In the study of the storage structure of the binary tree, the students came into conta

9、ct with a binary tree traversal. Many students will feel more or less some confusion appears to be simple recursive algorithm, Ergodic'll understand the process, may not be able to clear at a glance. The main reason

10、lies in the implementation of binary tree traversal of the mo　　Keywords： 　　Binary Tree; Ergodic; Multimedia　　前言　　樹是

11、另外一種非線性數(shù)據(jù)結(jié)構(gòu)，二叉樹就是其中一種，這種數(shù)據(jù)結(jié)構(gòu)在日常生活中是十分常見的，二叉樹的遍歷是樹結(jié)構(gòu)的一種常用的、重要的運(yùn)算，是樹的其它運(yùn)算的基礎(chǔ)。從結(jié)構(gòu)上來看，在對(duì)它進(jìn)行操作時(shí)，總是需要逐一對(duì)每個(gè)數(shù)據(jù)元素實(shí)施操作，這樣就存在一個(gè)操作順序問題，由此提出了二叉樹的遍歷操作。即如何按一定的規(guī)律和次序訪問樹中的每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)被訪問一次，而且僅被訪問一次。　　真正理解這一運(yùn)算的實(shí)現(xiàn)及其含義有助

12、于許多二叉樹運(yùn)算的實(shí)現(xiàn)及算法設(shè)計(jì)。然而，許多初學(xué)者開始時(shí)的學(xué)習(xí)效果不理想，原因是較難理解其內(nèi)在規(guī)律。二叉樹的遍歷方法及相應(yīng)過程如下。　　1 二叉樹的概述　　1.1 二叉樹的定義　　定義：二叉樹是n(n≥0)個(gè)結(jié)點(diǎn)的有限集，它或?yàn)榭諛?n=0)，或由一個(gè)根結(jié)點(diǎn)和兩棵分別稱為

13、左子樹和右子樹的互不相交的二叉樹構(gòu)成。(圖1-1)　　(圖1-1)　　特點(diǎn)：每個(gè)結(jié)點(diǎn)至多有2 棵子樹(即不存在度大于2的結(jié)點(diǎn))二叉樹的子樹有左、右分，且其次序不能任意顛倒。　　二叉樹的五種基本形態(tài)：（如圖1-2）

14、?。▓D1-2）　　1.2 二叉樹的性質(zhì)　　【性質(zhì)1】在二叉樹的第 i 層上至多有2i-1個(gè)結(jié)點(diǎn)　　證明：用數(shù)學(xué)歸納法證明。　　? ①i=1時(shí)，只有一個(gè)根結(jié)點(diǎn)，2＝10是對(duì)的。 　　? ②假設(shè)對(duì)所有j(1≤j&l

15、t;i)命題成立，即第j層上至多有2j-1 個(gè)結(jié)點(diǎn)。　　那么，第i-1層至多有2i-2個(gè)結(jié)點(diǎn)。　　又二叉樹每個(gè)結(jié)點(diǎn)的度至多為2。　　所以第i層上最大結(jié)點(diǎn)數(shù)是第i-1層的2倍，即2*2i-2 = 2i-1　　故命題得證</p&g

16、t;　　【性質(zhì)2】深度為k的二叉樹至多有2k－1個(gè)結(jié)點(diǎn)(k≥1)　　由性質(zhì)1可以得出，1至K層各層最多的結(jié)點(diǎn)個(gè)數(shù)分別為：20,21,22,23,...,2K-1。這是一個(gè)以2為比值的等比數(shù)列，前n項(xiàng)之和的計(jì)算公式為：　　其中a1為第一項(xiàng)，an為第n項(xiàng)，q為比值。可以得到，該數(shù)列前K項(xiàng)之和為：

17、　　【性質(zhì)3】對(duì)于任意一棵二叉樹BT，如果度為0的結(jié)點(diǎn)個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2，則n0=n2+1。　　證明：假設(shè)度為1的結(jié)點(diǎn)個(gè)數(shù)為n1，結(jié)點(diǎn)總數(shù)為n，B為二叉樹中的分支數(shù)。　　因?yàn)樵诙鏄渲?，所有結(jié)點(diǎn)的度均小于或等于2，所以結(jié)點(diǎn)總數(shù)為：　　n=n0+n1+n2 （1）

18、　　再查看一下分支數(shù)。在二叉樹中，除根結(jié)點(diǎn)之外，每個(gè)結(jié)點(diǎn)都有一個(gè)從上向下的分支指向，所以，總的結(jié)點(diǎn)個(gè)數(shù)n與分支數(shù)B之間的關(guān)系為：n=B+1。　　又因?yàn)樵诙鏄渲?，度?的結(jié)點(diǎn)產(chǎn)生1個(gè)分支，度為2的結(jié)點(diǎn)產(chǎn)生2個(gè)分支，所以分支數(shù)B可以表示為：B=n1+2n2。　　將此式代入上式，得：　　n=n1+2

19、n2+1 （2）　　用（1）式減去（2）式，并經(jīng)過調(diào)整后得到：n0=n2+1。　　如果一個(gè)深度為K的二叉樹擁有2K-1個(gè)結(jié)點(diǎn)，則將它稱為滿二叉樹。　　滿二叉樹：（如圖）　?。▓D1-3）&l

20、t;/p>　　完全二叉樹：有一棵深度為h，具有n個(gè)結(jié)點(diǎn)的二叉樹，若將它與一棵同深度的滿二叉樹中的所有結(jié)點(diǎn)按從上到下，從左到右的順序分別進(jìn)行編號(hào)，且該二叉樹中的每個(gè)結(jié)點(diǎn)分別與滿二叉樹中編號(hào)為1~n的結(jié)點(diǎn)位置一一對(duì)應(yīng)，則稱這棵二叉樹為完全二叉樹。　　【性質(zhì)4】具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 log2n+1。其中，log2n 的結(jié)果是不大于log2n的最大整數(shù)。<

21、/p>　　證明：假設(shè)具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為K，則根據(jù)性質(zhì)2可以得出：　　2K-1-1<n≤2K-1　　將不等式兩端加1得到：　　2K-1≤n<2K　　將不等式中的三項(xiàng)同取以2為底的對(duì)數(shù)

22、，并經(jīng)過化簡(jiǎn)后得到：　　K-1≤log2n<K　　由此可以得到：log2n =K-1。整理后得到：K= log2n+1。　　【性質(zhì)5】對(duì)于有n個(gè)結(jié)點(diǎn)的完全二叉樹中的所有結(jié)點(diǎn)按從上到下，從左到右的順序進(jìn)行編號(hào)，則對(duì)任意一個(gè)結(jié)點(diǎn)i （1≤i≤n），都有：　　（1）如果

23、i=1，則結(jié)點(diǎn)i是這棵完全二叉樹的根，沒有雙親；否則其雙親結(jié)點(diǎn)的編號(hào)為 i/2。　?。?）如果2i>n，則結(jié)點(diǎn)i沒有左孩子；否則其左孩子結(jié)點(diǎn)的編號(hào)為2i。　?。?）如果2i+1>n，則結(jié)點(diǎn)i沒有右孩子；否則其右孩子結(jié)點(diǎn)的編號(hào)為2i+1。　　下面我們利用數(shù)學(xué)歸納法證明這個(gè)性質(zhì)。&

24、lt;p>　　我們首先證明（2）和（3）。　　當(dāng)i=1時(shí)，若n≥3，則根的左、右孩子的編號(hào)分別是2，3；若n<3，則根沒有右孩子；若n<2，則根將沒有左、右孩子；以上對(duì)于（2）和（3）均成立。　　1.3 二叉樹的存儲(chǔ)結(jié)構(gòu)　　二叉樹也可以采用兩種存儲(chǔ)方式：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。</p&

25、gt;　　1、順序存儲(chǔ)結(jié)構(gòu)　　這種存儲(chǔ)結(jié)構(gòu)適用于完全二叉樹。其存儲(chǔ)形式為：用一組連續(xù)的存儲(chǔ)單元按照完全二叉樹的每個(gè)結(jié)點(diǎn)編號(hào)的順序存放結(jié)點(diǎn)內(nèi)容。下面是一棵二叉樹及其相應(yīng)的存儲(chǔ)結(jié)構(gòu)。　?。▓D1-4）　　在C語言中，這種存

26、儲(chǔ)形式的類型定義如下所示：　　#define MAX_TREE_NODE_SIZE 100　　typedef struct {　　EntryType item[MAX_TREE_NODE_SIZE]; //根存儲(chǔ)在下標(biāo)為1的數(shù)組單元中　　int n; /

27、/當(dāng)前完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)　　}QBTree;　　這種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是空間利用率高、尋找孩子和雙親比較容易。下面我們給出完全二叉樹在這種存儲(chǔ)形式下的操作算法。　　（1）構(gòu)造一棵完全二叉樹　　void CreateBTree(QBTre

28、e *BT,EntryType item[ ],int n)　　{　　if (n>=MAX_TREE_NODE_SIZE) n=MAX_TREE_NODE_SIZE-1;　　for (i=1; i<=n;i++)　　BT-

29、>item[i]=item[i];　　BT->n=n;　　}　?。?）獲取給定結(jié)點(diǎn)的左孩子 　　int LeftCHild(QBTree BT,int node)

30、　　{　　if (2*node>BT.n) return 0;　　else return 2*node;　　}　　RightChild(BT,node)與這個(gè)操作類似，讀

31、者可試著自行完成。　　（3）獲取給定結(jié)點(diǎn)的雙親 　　int Parent(QBTree BT,int node)　　{　　if (1<=node&&node<=BT.n) return i/2;</p

32、>　　else return -1;　　}　　2、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)　　在順序存儲(chǔ)結(jié)構(gòu)中，利用編號(hào)表示元素的位置及元素之間孩子或雙親的關(guān)系，因此對(duì)于非完全二叉樹，需要將空缺的位置用特定的符號(hào)填補(bǔ)，若空缺結(jié)點(diǎn)較多，勢(shì)必

33、造成空間利用率的下降。在這種情況下，就應(yīng)該考慮使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。　　常見的二叉樹結(jié)點(diǎn)結(jié)構(gòu)如下所示：　　（圖1-5）　　其中，Lchild和Rchild是分別指向該結(jié)點(diǎn)左孩子和右孩子的指針，item是數(shù)據(jù)元素的內(nèi)容。在C語言中的類型定義為：<p&g

34、t;　　typedef struct BTNode{　　EntryType item;　　struct BTNode *Lchild,*Rchlid;　　}BTNode,*BTree;　　下面（圖1-6）是一棵二叉樹及相應(yīng)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。<p

35、>　　（圖1-6）　　這種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是尋找孩子結(jié)點(diǎn)容易，雙親比較困難。因此，若需要頻繁地尋找雙親，可以給每個(gè)結(jié)點(diǎn)添加一個(gè)指向雙親結(jié)點(diǎn)的指針域，其結(jié)點(diǎn)結(jié)構(gòu)如下所示。　?。▓D1-4）　　2 二叉樹的遍歷</b

36、>　　2.1 常用的二叉樹遍歷的算法　　在二叉樹的一些應(yīng)用中，常常要求在樹中查找具有某種特征的結(jié)點(diǎn)，或者對(duì)樹種全部結(jié)點(diǎn)逐一進(jìn)行某種處理．這就提出了一個(gè)遍歷二叉樹樹的問題，即如何按一定的規(guī)律和次序訪問樹中的每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)被訪問一次，而且僅彼訪問一次。　　所謂二叉樹的遍歷，是指按一定的次序訪問樹中的所有

37、結(jié)點(diǎn)，使每個(gè)結(jié)點(diǎn)恰好被候訪問一次。其中．遍歷次序保證了二叉樹上每個(gè)結(jié)點(diǎn)均被訪問一次且僅有一次。　　遍歷是二叉樹中經(jīng)常要用到的一種操作。因?yàn)樵趯?shí)際應(yīng)用中．常常需要按一點(diǎn)順序?qū)Χ鏄渲械拿總€(gè)結(jié)點(diǎn)逐個(gè)地進(jìn)行訪問，查找具有某一特點(diǎn)的結(jié)點(diǎn)，然后對(duì)這些滿足條件的結(jié)點(diǎn)進(jìn)行處理。　　通過一次完整的遍歷，可使二叉樹中結(jié)點(diǎn)信息由非線性排列變?yōu)槟撤N意義上的線性序列。也就是說，

38、遍歷操作使非線性結(jié)構(gòu)線性化。　　二叉樹常用的遍歷有先序遍歷、中序遍歷、后序遍歷。所謂先序、中序、后序，區(qū)別在于訪問根結(jié)點(diǎn)的順序。　　這里，若T為根指針，則遍歷左右子樹時(shí)，是分別遍歷以T->lchild 和T->rchild 為根指針的子樹。　　visit( BiTree *T )

39、　　{　　printf(“%c”,T->data);　　}　　先序遍歷：　　若二叉樹非空，則：

40、;　　訪問根結(jié)點(diǎn)　　先序遍歷左子樹　　先序遍歷右子樹　　對(duì)應(yīng)遞歸算法如下：

41、void PreOrder(BiTree *T)　　{ if (T!=NULL)　　{ printf("%d\t",T->data);　　preorder(T->lchild);　　preorder(T->rchild);<

42、/p>　　}　　}　　采用先序遍歷得到的訪問結(jié)點(diǎn)序列稱為先序遍歷序列，先序遍歷序列的特點(diǎn)是：其第一個(gè)元素值為二叉樹中根結(jié)點(diǎn)的數(shù)據(jù)值。　　如圖所示的二叉樹，先序遍歷序列為: e c b a j f m k z&l

43、t;/p>　　中序遍歷：　　若二叉樹非空，則：　　（1）中序遍歷左子樹　?。?）訪問根結(jié)點(diǎn)　?。?）中序遍歷右子樹</p&g

44、t;　　對(duì)應(yīng)遞歸算法如下：　　void PreOrder(BiTree *T)　　{ if (T!=NULL)　　{ preorder(T->lchild);　　printf("%d\t&qu

45、ot;,T->data);　　preorder(T->rchild);　　}　　}　　采用中序遍歷得到的訪問結(jié)點(diǎn)序列稱為中序遍歷序列，中序遍歷序列的特點(diǎn)是：若已知二叉樹的根結(jié)點(diǎn)的數(shù)據(jù)值

46、，以應(yīng)該數(shù)據(jù)值為屆，將中序遍歷序列分為兩部分，前半部分為左子樹的中序遍歷序列，后半部分為右子樹的中序遍歷序列。　　如圖所示的二叉樹，中序遍歷序列為: a b c e f j k m z　　后序遍歷：　　若二叉樹非空，則：

47、;　?。?）后序遍歷左子樹　?。?）后序遍歷右子樹　　（3）訪問根結(jié)點(diǎn)　　對(duì)應(yīng)遞歸算法如下：　　void PreOrder(BiTree *T)<

48、;p>　　{ if (T!=NULL)　　{ preorder(T->lchild);　　preorder(T->rchild);　　printf("%d\t",T->data);　　}

49、　　}　　采用后序遍歷得到的訪問結(jié)點(diǎn)序列稱為后序遍歷序列，后序遍歷序列的特點(diǎn)是：其最后一個(gè)元素值為二叉樹中根結(jié)點(diǎn)的數(shù)據(jù)值。　　如圖所示的二叉樹，后序遍歷序列為: a b c f k z m j e　　（圖2-1）&l

50、t;/b>　　2.2二叉樹遍歷的C程序演示過程　　下圖是程序執(zhí)行界面，用C語言實(shí)現(xiàn)的二叉樹遍歷的程序。　?。▓D2-2）　　下圖是遍歷執(zhí)行的具體過程，將三種遍歷各執(zhí)行一遍。

51、;　?。▓D2-3）　　以下是二叉樹遍歷執(zhí)行的過程部分代碼：　　/*用圖形顯示創(chuàng)建好的樹*/　　void DrawTree(Tree *t)　　{　　if(t!=NULL)&

52、lt;/p>　　{　　setcolor(BLACK);　　setfillstyle(SOLID_FILL,BLACK);　　fillellipse(t->x,t->y,9,9);　　setcol

53、or(WHITE);　　circle(t->x,t->y,10); /*畫圓*/　　sprintf(str,"%c",t->data);/*將內(nèi)容轉(zhuǎn)換成字符串輸出*/　　outtextxy(t->x-3,t->y-2,str);<p&

54、gt;　　if(t->lchild!=NULL)/*左子樹*/　　{　　line(t->x-5,t->y+12,t->lchild->x+5,t->lchild->y-12);　　DrawTree(t->lchild);<

55、/p>　　}　　if(t->rchild!=NULL)/*右子樹*/　　{　　line(t->x+5,t->y+12,t->rchild->x-5,t->rchild->

56、;y-12);　　DrawTree(t->rchild);　　}　　}　　}　　/*遍歷時(shí)顯示每個(gè)結(jié)點(diǎn)的過程*

57、/　　void DrawNode(Tree *t,int color)　　{　　setcolor(YELLOW);　　setfillstyle(SOLID_FILL,YELLOW);　　fil

58、lellipse(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);<

59、p>　　setcolor(color);　　outtextxy(s.x,s.y,str);　　setcolor(RED);　　sprintf(str,"%d",s.num);/*將遍歷次序用數(shù)字顯示在樹的結(jié)點(diǎn)上*/　　outtextxy(t-&g

60、t;x-3,t->y-20,str);　　s.num++;　　sleep(1);　　}　　/*畫菜單的效果圖*/

61、;　　void drawtangle2()　　{ int i;　　setcolor(14); /*黃*/　　setlinestyle(0,0,3); /*實(shí)線，三個(gè)像素的寬度*/　　line(150,200,320,200);<

62、;/p>　　line(149,199,149,400);　　line(149,400,320,400);　　line(320,200,320,400);　　for(i=203;i<398;i++) /*劃里面的深灰背景,是不斷的劃線來實(shí)現(xiàn)*/<p&

63、gt;　　{setcolor(8);　　line(151,i,318,i);　　delay(4000);　　}　　}　　/*生成二叉樹，h表示層次，t表示

64、橫坐標(biāo)，w表示結(jié)點(diǎn)左右子樹的寬度，隨機(jī)數(shù)n確定結(jié)點(diǎn)是空或非空，如n為0，則為空*，但要限定確保結(jié)點(diǎn)數(shù)不少于三個(gè)*/　　Tree *InitTree(int h,int t,int w)　　{　　char ch;&l

65、t;p>　　int n;/*自動(dòng)建立時(shí)隨機(jī)賦值判斷是否是NULL的標(biāo)志*/　　Tree *node;　　n=random(5);　　if(n==0&&nodeNUM>=3)/*隨機(jī)賦值時(shí)候確保自動(dòng)建立的二叉樹有三個(gè)結(jié)點(diǎn)*/

66、ch='.';　　else　　ch=65+random(25);　　if(ch=='.')/*輸入空格代表NULL*/　　return NULL;<p&

67、gt;　　else　　{　　if(h==6||nodeNUM==26)/*如果樹的層次已經(jīng)到5或者結(jié)點(diǎn)樹到達(dá)26個(gè)就自動(dòng)返回NULL*/　　return NULL;　　node=(Tree*)ma

68、lloc(sizeof(Tree));　　node->data=ch;　　node->x=t;/*樹的x坐標(biāo)是傳遞過來的橫坐標(biāo)*/　　node->y=h*50;/*樹的y坐標(biāo)與層次大小有關(guān)*/　　nodeNUM++;<p&g

69、t;　　node->lchild=InitTree(h+1,t-w,w/2);　　node->rchild=InitTree(h+1,t+w,w/2);　　}　　return node;　　}</b

70、>　　/*前序遍歷*/　　void Preorder(Tree *t)　　{　　if(t!=NULL)　　{&

71、lt;/p>　　s.x+=15;　　DrawNode(t,9);　　Preorder(t->lchild);　　Preorder(t->rchild);　　}

72、;　　}　　2.3 非遞歸遍歷二叉樹　　先序非遞歸算法：　　假設(shè)：T是要遍歷樹的根指針，若T != NULL對(duì)于非遞歸算法，引入棧模擬遞歸工作棧，初始時(shí)棧為空。問題：如何用棧來保存信息，使得在

73、先序遍歷過左子樹后，能利用棧頂信息獲取T的右子樹的根指針？方法1：訪問T->data后，將T入棧，遍歷左子樹；遍歷完左子樹返回時(shí)，棧頂元素應(yīng)為T，出棧，再先序遍歷T的右子樹。方法2：訪問T->data后，將T->rchild入棧，遍歷左子樹；遍歷完左子樹返回時(shí)，棧頂元素應(yīng)為T->rchild，出棧，遍歷以該指針為根的子樹。　　void PreOrder(BiTree

74、 T,Status ( *Visit ) (ElemType e)){ InitStack(S);　　while ( T!=NULL || !StackEmpty(S)){ while ( T != NULL ){

75、; Visit(T->data) ; 　　Push(S,T); T = T->lchild; }

76、60; if( !StackEmpty(S) ){ Pop(S,T); T = T->rchild; } }}&

77、lt;p>　　中序非遞歸算法：　　思路：　　T是要遍歷樹的根指針，中序遍歷要求在遍歷完左子樹后，訪問根，再遍歷右子樹。問題：如何用棧來保存信息，使得在中序遍歷過左子樹后，能利用棧頂信息獲取T指針？方法：先將T入棧，遍歷左子樹；遍歷完左子樹返回時(shí)，棧頂元素應(yīng)為T，出棧，訪

78、問T->data，再中序遍歷T的右子樹。　　算法：void InOrder(BiTree T, Status ( *Visit ) (ElemType e)){ // 流程圖如右，當(dāng)型循環(huán) InitStack(S);

79、while ( T!=NULL || !StackEmpty(S) ){ while ( T != NULL ){ Push(S,T); T = T->lchild;

80、0; }　　if( !StackEmpty(S) ){ Pop(S, T); Visit(T->data); &

81、#160; T = T->rchild; } }}　　后序非遞歸算法：　　思路：　　T是要遍歷樹的根指針

82、，后序遍歷要求在遍歷完左右子樹后，再訪問根。需要判斷根結(jié)點(diǎn)的左右子樹是否均遍歷過。　　可采用標(biāo)記法，結(jié)點(diǎn)入棧時(shí)，配一個(gè)標(biāo)志tag一同入棧(0：遍歷左子樹前的現(xiàn)場(chǎng)保護(hù)，1：遍歷右子樹前的現(xiàn)場(chǎng)保護(hù))。　　首先將T和tag(為0)入棧，遍歷左子樹；返回后，修改棧頂tag為1，遍歷右子樹；最后訪問根結(jié)點(diǎn)。typedef struct stackElement{

83、Bitree data;char tag;}stackElemType;　　算法：void PostOrder(BiTree T, Status ( *Visit ) (ElemType e)){

84、; // 流程圖如右，當(dāng)型循環(huán) InitStack(S);　　while ( T!=NULL || !StackEmpty(S) ){ while ( T != NULL ){ Push(S,T,0);

85、0; T = T->lchild; } 　　while ( !StackEmpty(S) && GetTopTag(S)==1){

86、 Pop(S, T); Visit(T->data); }　　if ( !StackEmpty(S) ){ &#

87、160; SetTopTag(S, 1); // 設(shè)置棧頂標(biāo)記 T = GetTopPointer(S); // 取棧頂保存的指針

88、60; T = T->rchild; }else break; }}　　2.4 二叉樹遍歷算法的應(yīng)用　　前面曾指出二叉樹的遍歷算法是二叉樹算法的基礎(chǔ)，下面結(jié)合實(shí)例對(duì)此展開討論。根據(jù)所運(yùn)用的基本思想來分，可劃分為兩個(gè)層次，其一是簡(jiǎn)單、直接

89、的應(yīng)用，其二是具有一定深度的方法的應(yīng)用。　　可以證明，二叉樹的遍歷算法對(duì)樹T中每個(gè)結(jié)點(diǎn)都會(huì)執(zhí)行一次且執(zhí)行一次訪問結(jié)點(diǎn)的操作。其中訪問結(jié)點(diǎn)的操作可以是多種形式及多個(gè)操作，例如輸出結(jié)點(diǎn)值。利用這一特點(diǎn)，適當(dāng)修改訪問操作的內(nèi)容，便可以得到許多問題的求解算法。下面給出幾個(gè)典型問題的求解。　　例：設(shè)計(jì)算法，按中序次序輸出二叉樹T中度為2的結(jié)點(diǎn)的值。</p&g

90、t;　　解：本算法的要求與中序遍歷算法既有相同之處，又有不同之處。相同之處是輸出次序均為中序；不同之處是此處不適輸出每個(gè)結(jié)點(diǎn)的值，而是僅輸出其中的度為2的結(jié)點(diǎn)，即有條件輸出。為此，將中序遍歷算法中的訪問結(jié)點(diǎn)的操作改為條件輸出結(jié)點(diǎn)的值即可。算法如下：　　Void inorder(Bnode *T)　　{</b&

91、gt;　　If(T!=NULL)　　{ inorder(T->lchild);　　If(T->lchild!=NULL&&T->rchild!=NULL)　　printf("%d\t",T->data);

92、　　inorder(T->lchild);　　}　　}　　例：設(shè)計(jì)算法，求二叉樹T的結(jié)點(diǎn)數(shù)。　　解：本算法不是要輸出每個(gè)結(jié)點(diǎn)的值，所要求的僅是求出其

93、中的結(jié)點(diǎn)數(shù)。我們可適應(yīng)當(dāng)修改遍歷算法以完成要求：將某一遍歷算法中的訪問結(jié)點(diǎn)的操作改為記數(shù)操作，即將該結(jié)點(diǎn)的數(shù)目1累加到一個(gè)全局變量n中，每個(gè)結(jié)點(diǎn)都這樣做一次，即完成了結(jié)點(diǎn)數(shù)的求解。采用中序遍歷算法形式所得到的算法如下：　　Void inorder(Bnode *T)　　{

94、If(T!=NULL)　　{ inorder(T->lchild);　　n++；　　inorder(T->lchild);　　}<

95、;b>　　}　　例：設(shè)計(jì)算法求解給定二叉樹的高度。　　解：由于求二叉樹的高度難以采用由遍歷算法簡(jiǎn)單變化的方式來實(shí)現(xiàn)，因此，需要采用本小姐所討論的方法來求解?，F(xiàn)分析如下：　　若T為空時(shí)，則其高度為0，求解結(jié)束。　　否則，若T不為空，其高度應(yīng)是其左、

96、右子樹高度的最大值再加1.假設(shè)其左右子樹的高度能求解出來，則算法求解容易實(shí)現(xiàn)。其左右子樹的高度的求解又可以通過遞歸調(diào)用本算法來完成。據(jù)此討論可寫出幾種形式的算法，下面給出有值函數(shù)形式的算法。　　設(shè)函數(shù)int high（Bnode *T）表示返回二叉樹T的高度，因此high(T->lchild)、high(T->rchild)分別代表T的左右子樹的高度，由前面的討論可得算法如下：<

97、;/p>　　int high（Bnode *T）　　{If(T==NULL)return 0;　　Else　　Return max(high(T->lchild),high(T->rchild))+1;<

98、p>　　}　　3基于FLASH的二叉樹遍歷課件應(yīng)用實(shí)現(xiàn)　　3.1課件簡(jiǎn)介　　在二叉樹教學(xué)過程中，如果能適當(dāng)?shù)氖苟嗝襟w課件進(jìn)行教學(xué)，這對(duì)于學(xué)生盡快掌握新的知識(shí)有很大的幫助，而且可以使教學(xué)內(nèi)容更為直觀、方便，可以大大提高學(xué)生的學(xué)習(xí)興趣，

99、減少枯感，從而增強(qiáng)學(xué)習(xí)效果。　　為此，筆者編寫了一個(gè)二叉樹遍歷的Flash教學(xué)課件，嘗試著將自己的心得體會(huì)融入課件編寫之中，在選擇界面設(shè)計(jì)、交互方式等方面盡量多從學(xué)生的角度出發(fā)，希望這樣能起到拋磚引玉的作用。　　3.2結(jié)構(gòu)設(shè)計(jì)分析　　確定課件的總體結(jié)構(gòu)：整個(gè)界面是有六個(gè)按鈕組

100、成，其中一個(gè)是退出按鈕，其它導(dǎo)航按鈕分別代表五個(gè)教學(xué)環(huán)節(jié)，點(diǎn)擊導(dǎo)航按鈕將會(huì)進(jìn)入相應(yīng)的教學(xué)內(nèi)容。課件整體結(jié)構(gòu)如圖所示：　　圖（3-1）　　對(duì)應(yīng)的Flash課件實(shí)例界面如下：　　圖（3-2）<b

101、>　　3.3主要功能　　其中每個(gè)模塊所實(shí)現(xiàn)的功能如下：　　點(diǎn)擊“新課導(dǎo)入”按鈕進(jìn)入導(dǎo)入，在本界面中展示了一副手繪九寨溝旅游風(fēng)景圖，通過圖片的變化，可發(fā)現(xiàn)與二叉樹相似，由此引出二叉樹遍歷的概念，給學(xué)生一個(gè)初步的印象。　　圖（3-3）

102、　　點(diǎn)擊“新課學(xué)習(xí)”按鈕進(jìn)入本節(jié)課的新授課內(nèi)容，在此界面里主要描述了二叉樹遍歷的概念，以及本課所用到的二叉樹的模型，通過“下一頁”的按鈕，可分別對(duì)二叉樹的三種遍歷進(jìn)行講解，并可通過遍歷演示的按鈕看到直觀清晰的二叉樹遍歷過程，最后，再通過典型的例題分析對(duì)二叉樹的遍歷進(jìn)一步的了解。其中在每個(gè)分界面中都有“返回”按鈕，點(diǎn)“返回”按鈕可返回到主界面。下圖是遍歷的演示制作過程。<

103、;b>　　圖（3-4）　　圖（3-5）　　點(diǎn)擊“鞏固練習(xí)”按鈕進(jìn)入本課的練習(xí)題，并可以看到例題分析與答案。點(diǎn)“返回”按鈕可返回到主界面。　　點(diǎn)擊“本課小結(jié)”按鈕進(jìn)入本課總結(jié)界面，“返回”按鈕可返回到主界面。

104、　點(diǎn)擊“本課作業(yè)”按鈕進(jìn)入課后作業(yè)部分，內(nèi)容與“鞏固練習(xí)”相應(yīng)，能達(dá)到學(xué)生課后鞏固復(fù)習(xí)的作用。　　點(diǎn)擊“退出”按鈕退出此課件。　　4 教學(xué)設(shè)計(jì)　　一、課程內(nèi)容分析　　本課是《C程序設(shè)計(jì)》中第五章函

105、數(shù)中的第二、三節(jié)，是本章的基礎(chǔ)。本節(jié)課主要學(xué)習(xí)認(rèn)識(shí)二叉樹，實(shí)現(xiàn)二叉樹遍歷。　　二、教學(xué)目標(biāo)　　1、知識(shí)目標(biāo)：　?。?）理解二叉樹的性質(zhì)與結(jié)構(gòu)　?。?）掌握二叉樹的三種遍歷

106、　?。?）能獨(dú)立完成二叉樹遍歷的執(zhí)行　　2、情感目標(biāo)：　　學(xué)習(xí)完本節(jié)課，學(xué)生對(duì)于程序編寫的興趣在以前的基礎(chǔ)上有更大的加深。　　3、技能目標(biāo)：　　學(xué)完本節(jié)課后，學(xué)生應(yīng)該學(xué)會(huì)二叉

107、樹遍歷的執(zhí)行，并且根據(jù)二叉樹與二叉樹的遍歷，能應(yīng)用的更廣泛。　　三、教學(xué)方法　　講授法、演示法。　　四、教學(xué)過程　　首先大家一起回憶上節(jié)課學(xué)習(xí)的內(nèi)容，回答二叉

108、樹的定義、基本性質(zhì)和存儲(chǔ)結(jié)構(gòu)。　?。ㄒ唬┬抡n導(dǎo)入　　出示課件，讓同學(xué)們懂得本節(jié)課的重點(diǎn)。提問同學(xué)們有沒有去過外地旅游，然后播放課件上的旅游景點(diǎn)圖片，然后通過旅游時(shí)到每個(gè)景點(diǎn)照相留念的方式可知道，要想每個(gè)景點(diǎn)都走到，那得采取某種方式去合理安排，否則會(huì)漏掉一些景點(diǎn)，這個(gè)就類似二叉樹的遍歷，引入新課。

109、　?。ǘ┬抡n學(xué)習(xí)　　1.知識(shí)的理解　　逐個(gè)講解遍歷的種類和相應(yīng)的過程　?。?）先序遍歷　　若二叉樹為空，則結(jié)束遍歷操作；否則訪問根結(jié)點(diǎn)；

110、　　先序遍歷左子樹；　　先序遍歷右子樹。　　（2）中序遍歷　　若二叉樹為空，則結(jié)束遍歷操作；否則

111、　中序遍歷左子樹；　　訪問根結(jié)點(diǎn)；　　（3）后序遍歷　　若二叉樹為空，則結(jié)束遍歷操作；否則　　后序遍歷左子樹；&l

112、t;p>　　后序遍歷右子樹；　　訪問根結(jié)點(diǎn)。　　2.典型例題分析　　例：設(shè)計(jì)算法，按中序次序輸出二叉樹T中度為2的結(jié)點(diǎn)的值。　　解：本算法的要求與中序遍

113、歷算法既有相同之處，又有不同之處。相同之處是輸出次序均為中序；不同之處是此處不適輸出每個(gè)結(jié)點(diǎn)的值，而是僅輸出其中的度為2的結(jié)點(diǎn)，即有條件輸出。為此，將中序遍歷算法中的訪問結(jié)點(diǎn)的操作改為條件輸出結(jié)點(diǎn)的值即可。算法如下：　　Void inorder(Bnode *T)　　{　　I

114、f(T!=NULL)　　{ inorder(T->lchild);　　If(T->lchild!=NULL&&T->rchild!=NULL)　　printf("%d\t",T->data);　　inor

115、der(T->lchild);　　}　　}　?。ㄈ╈柟叹毩?xí)　　【例】:已知二叉樹的先序和中序序列，寫出該數(shù)的后序遍歷。<

116、p>　　先序：A B C D E F G H I J 　　中序：C D B F E A I H G J　　分析：由先序序列確定根；由中序序列確定左右子樹。　　解：1、由先序知根為A，則由中序知左子樹為CDBF, 右子樹為IHGJ，如圖：　　圖（

117、3-5）　　2、再分別在左、右子樹的序列中找出根、左子樹序列、右子樹序列。　　先序：A B C D E F G H I J 　　中序：C D B F E A I H G J　　圖（3-5）&

118、lt;p>　　3、最后對(duì)該樹進(jìn)行后序遍歷。　　后序遍歷為：D C F E B I H J G A。　?。ㄋ模┬〗Y(jié)引深　　樹是另外一種重要的非線性數(shù)據(jù)結(jié)構(gòu)，這種數(shù)據(jù)結(jié)構(gòu)，在日常生活中是十分常見的，二叉樹是一種很有用的非線性結(jié)構(gòu)，研究二叉樹的性質(zhì)以及二叉樹的遍歷具有十分重要

119、的意義。　?。ㄎ澹┳鳂I(yè)　　設(shè)一棵二叉樹的中序遍歷為：BDCEAFHG，后序遍歷為：DECBHGFA。請(qǐng)畫出這棵二叉樹的邏輯圖，并寫出它的前序遍歷結(jié)果。　　結(jié)束語 　　本文完整的介紹了二叉樹三種遍歷

120、方法的實(shí)現(xiàn)過程。這兩個(gè)算法是對(duì)相關(guān)文獻(xiàn)上的相關(guān)內(nèi)容的深一層次的展開，進(jìn)一步展示了在二叉樹這種非線性結(jié)構(gòu)上進(jìn)行數(shù)據(jù)處理的統(tǒng)一性方法。同時(shí)為了易于學(xué)生理解，加入了遍歷的直觀演示效果。為此方面內(nèi)容的教學(xué)提供了好的參考。　　參考文獻(xiàn)　　1、譚浩強(qiáng)著。c語言程序設(shè)計(jì)。清華大學(xué)出版社。2004年<p

121、>　　2、嚴(yán)尉民、吳偉民著。數(shù)據(jù)結(jié)構(gòu)。清華大學(xué)出版社。2002年　　3、唐策善、李龍澍、黃劉生編著。數(shù)據(jù)結(jié)構(gòu)——用c語言描述。高等教育出版社。2006年　　4、敖副江譯。數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)。清華大學(xué)出版社。2005年　　5、《FLASH動(dòng)畫設(shè)計(jì)制作》第一版高等教育出版社2002&l

122、t;p>　　6、項(xiàng)國(guó)雄、周勤編著，《多媒體課件設(shè)計(jì)基礎(chǔ)》，高等教育出版社，2000年　　致謝　　本文是在老師精心指導(dǎo)和大力支持下完成的。老師以其嚴(yán)謹(jǐn)求實(shí)的治學(xué)態(tài)度、高度的敬業(yè)精神、孜孜以求的工作作風(fēng)和大膽創(chuàng)新的進(jìn)取精神對(duì)我產(chǎn)生重要影響。她淵博的知識(shí)、開闊的視野和敏銳的思維給了我深深的啟迪。同時(shí)，在此

眾賞文庫> 全部分類> 畢業(yè)設(shè)計(jì)

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲(chǔ)空間，僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

二叉樹遍歷的實(shí)現(xiàn)與教學(xué)演示畢業(yè)論文

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

二叉樹遍歷的實(shí)現(xiàn)與教學(xué)演示畢業(yè)論文

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載