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

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

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

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

文檔簡介

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

2、　　前言2　　1 二叉樹的概述2　　1.1 二叉樹的定義2　　1.2 二叉樹的性質(zhì)3　　1.3 二叉樹的存儲結(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)用實現(xiàn)15　　3.

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

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

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

7、合的角度，制作FLASH課件應(yīng)用于教學(xué)中，提高教學(xué)質(zhì)量。從而更好的進行課堂教學(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)的一種常用的、重要的運算，是樹的其它運算的基礎(chǔ)。從結(jié)構(gòu)上來看，在對它進行操作時，總是需要逐一對每個數(shù)據(jù)元素實施操作，這樣就存在一個操作順序問題，由此提出了二叉樹的遍歷操作。即如何按一定的規(guī)律和次序訪問樹中的每個結(jié)點，使得每個結(jié)點被訪問一次，而且僅被訪問一次。　　真正理解這一運算的實現(xiàn)及其含義有助

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

27、/當前完全二叉樹的結(jié)點個數(shù)　　}QBTree;　　這種存儲結(jié)構(gòu)的特點是空間利用率高、尋找孩子和雙親比較容易。下面我們給出完全二叉樹在這種存儲形式下的操作算法。　?。?）構(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é)點的左孩子 　　int LeftCHild(QBTree BT,int node)

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

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

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

33、造成空間利用率的下降。在這種情況下，就應(yīng)該考慮使用鏈式存儲結(jié)構(gòu)。　　常見的二叉樹結(jié)點結(jié)構(gòu)如下所示：　?。▓D1-5）　　其中，Lchild和Rchild是分別指向該結(jié)點左孩子和右孩子的指針，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)的鏈式存儲結(jié)構(gòu)。<p

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

50、t;/b>　　2.2二叉樹遍歷的C程序演示過程　　下圖是程序執(zhí)行界面，用C語言實現(xiàn)的二叉樹遍歷的程序。　　（圖2-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);　　}　　}　　}　　/*遍歷時顯示每個結(jié)點的過程*

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é)點上*/　　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); /*實線，三個像素的寬度*/　　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++) /*劃里面的深灰背景,是不斷的劃線來實現(xiàn)*/<p&

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

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

65、t;p>　　int n;/*自動建立時隨機賦值判斷是否是NULL的標志*/　　Tree *node;　　n=random(5);　　if(n==0&&nodeNUM>=3)/*隨機賦值時候確保自動建立的二叉樹有三個結(jié)點*/

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é)點樹到達26個就自動返回NULL*/　　return NULL;　　node=(Tree*)ma

68、lloc(sizeof(Tree));　　node->data=ch;　　node->x=t;/*樹的x坐標是傳遞過來的橫坐標*/　　node->y=h*50;/*樹的y坐標與層次大小有關(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對于非遞歸算法，引入棧模擬遞歸工作棧，初始時棧為空。問題：如何用棧來保存信息，使得在

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

78、問T->data，再中序遍歷T的右子樹。　　算法：void InOrder(BiTree T, Status ( *Visit ) (ElemType e)){ // 流程圖如右，當型循環(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é)點的左右子樹是否均遍歷過。　　可采用標記法，結(jié)點入棧時，配一個標志tag一同入棧(0：遍歷左子樹前的現(xiàn)場保護，1：遍歷右子樹前的現(xiàn)場保護)。　　首先將T和tag(為0)入棧，遍歷左子樹；返回后，修改棧頂tag為1，遍歷右子樹；最后訪問根結(jié)點。typedef struct stackElement{

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

84、; // 流程圖如右，當型循環(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è)置棧頂標記 T = GetTopPointer(S); // 取棧頂保存的指針

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

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

90、t;　　解：本算法的要求與中序遍歷算法既有相同之處，又有不同之處。相同之處是輸出次序均為中序；不同之處是此處不適輸出每個結(jié)點的值，而是僅輸出其中的度為2的結(jié)點，即有條件輸出。為此，將中序遍歷算法中的訪問結(jié)點的操作改為條件輸出結(jié)點的值即可。算法如下：　　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è)計算法，求二叉樹T的結(jié)點數(shù)。　　解：本算法不是要輸出每個結(jié)點的值，所要求的僅是求出其

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

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

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

96、右子樹高度的最大值再加1.假設(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)用實現(xiàn)　　3.1課件簡介　　在二叉樹教學(xué)過程中，如果能適當?shù)氖苟嗝襟w課件進行教學(xué)，這對于學(xué)生盡快掌握新的知識有很大的幫助，而且可以使教學(xué)內(nèi)容更為直觀、方便，可以大大提高學(xué)生的學(xué)習(xí)興趣，

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

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

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

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

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

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

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

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

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

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

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

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

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

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

113、歷算法既有相同之處，又有不同之處。相同之處是輸出次序均為中序；不同之處是此處不適輸出每個結(jié)點的值，而是僅輸出其中的度為2的結(jié)點，即有條件輸出。為此，將中序遍歷算法中的訪問結(jié)點的操作改為條件輸出結(jié)點的值即可。算法如下：　　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、最后對該樹進行后序遍歷。　　后序遍歷為：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、的意義。　　（五）作業(yè)　　設(shè)一棵二叉樹的中序遍歷為：BDCEAFHG，后序遍歷為：DECBHGFA。請畫出這棵二叉樹的邏輯圖，并寫出它的前序遍歷結(jié)果。　　結(jié)束語 　　本文完整的介紹了二叉樹三種遍歷

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

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

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

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

溫馨提示

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

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

文檔簡介

溫馨提示

最新文檔

評論

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

文檔簡介

溫馨提示

最新文檔

評論

免費下載