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

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

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

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

文檔簡介

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

2、　　前言2　　1 二叉樹的概述2　　1.1 二叉樹的定義2　　1.2 二叉樹的性質3　　1.3 二叉樹的存儲結構4　　2 二叉樹的遍歷6

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

4、1課件簡介15　　3.2結構設計分析15　　3.3主要功能16　　4 教學設計18　　結束語20　　參考文獻21</b

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

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

7、合的角度，制作FLASH課件應用于教學中，提高教學質量。從而更好的進行課堂教學，使學生更清楚、更容易的理解二叉樹的遍歷過程。　　關鍵字：　　二叉樹; 遍歷; 多媒體　　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ù)結構，二叉樹就是其中一種，這種數(shù)據(jù)結構在日常生活中是十分常見的，二叉樹的遍歷是樹結構的一種常用的、重要的運算，是樹的其它運算的基礎。從結構上來看，在對它進行操作時，總是需要逐一對每個數(shù)據(jù)元素實施操作，這樣就存在一個操作順序問題，由此提出了二叉樹的遍歷操作。即如何按一定的規(guī)律和次序訪問樹中的每個結點，使得每個結點被訪問一次，而且僅被訪問一次。　　真正理解這一運算的實現(xiàn)及其含義有助

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

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

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

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

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

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

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

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

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

21、/p>　　證明：假設具有n個結點的完全二叉樹的深度為K，則根據(jù)性質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。　　【性質5】對于有n個結點的完全二叉樹中的所有結點按從上到下，從左到右的順序進行編號，則對任意一個結點i （1≤i≤n），都有：　?。?）如果

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

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

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

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

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

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

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

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

33、造成空間利用率的下降。在這種情況下，就應該考慮使用鏈式存儲結構。　　常見的二叉樹結點結構如下所示：　?。▓D1-5）　　其中，Lchild和Rchild是分別指向該結點左孩子和右孩子的指針，item是數(shù)據(jù)元素的內(nèi)容。在C語言中的類型定義為：<p&g

34、t;　　typedef struct BTNode{　　EntryType item;　　struct BTNode *Lchild,*Rchlid;　　}BTNode,*BTree;　　下面（圖1-6）是一棵二叉樹及相應的鏈式存儲結構。<p

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

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

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

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

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

40、;　　訪問根結點　　先序遍歷左子樹　　先序遍歷右子樹　　對應遞歸算法如下：

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

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

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

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

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

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

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

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

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

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

51、;　　（圖2-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)容轉換成字符串輸出*/　　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);　　}　　}　　}　　/*遍歷時顯示每個結點的過程*

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)容轉換成字符串輸出*/　　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ù)字顯示在樹的結點上*/　　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表示結點左右子樹的寬度，隨機數(shù)n確定結點是空或非空，如n為0，則為空*，但要限定確保結點數(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)/*隨機賦值時候確保自動建立的二叉樹有三個結點*/

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

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

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

73、先序遍歷過左子樹后，能利用棧頂信息獲取T的右子樹的根指針？方法1：訪問T->data后，將T入棧，遍歷左子樹；遍歷完左子樹返回時，棧頂元素應為T，出棧，再先序遍歷T的右子樹。方法2：訪問T->data后，將T->rchild入棧，遍歷左子樹；遍歷完左子樹返回時，棧頂元素應為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入棧，遍歷左子樹；遍歷完左子樹返回時，棧頂元素應為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、，后序遍歷要求在遍歷完左右子樹后，再訪問根。需要判斷根結點的左右子樹是否均遍歷過。　　可采用標記法，結點入棧時，配一個標志tag一同入棧(0：遍歷左子樹前的現(xiàn)場保護，1：遍歷右子樹前的現(xiàn)場保護)。　　首先將T和tag(為0)入棧，遍歷左子樹；返回后，修改棧頂tag為1，遍歷右子樹；最后訪問根結點。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); // 設置棧頂標記 T = GetTopPointer(S); // 取棧頂保存的指針

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

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

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

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

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

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

96、右子樹高度的最大值再加1.假設其左右子樹的高度能求解出來，則算法求解容易實現(xiàn)。其左右子樹的高度的求解又可以通過遞歸調用本算法來完成。據(jù)此討論可寫出幾種形式的算法，下面給出有值函數(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的二叉樹遍歷課件應用實現(xiàn)　　3.1課件簡介　　在二叉樹教學過程中，如果能適當?shù)氖苟嗝襟w課件進行教學，這對于學生盡快掌握新的知識有很大的幫助，而且可以使教學內(nèi)容更為直觀、方便，可以大大提高學生的學習興趣，

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

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

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

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

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

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

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

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

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

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

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

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

111、　中序遍歷左子樹；　　訪問根結點；　?。?）后序遍歷　　若二叉樹為空，則結束遍歷操作；否則　　后序遍歷左子樹；&l

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

113、歷算法既有相同之處，又有不同之處。相同之處是輸出次序均為中序；不同之處是此處不適輸出每個結點的值，而是僅輸出其中的度為2的結點，即有條件輸出。為此，將中序遍歷算法中的訪問結點的操作改為條件輸出結點的值即可。算法如下：　　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);　　}　　}　?。ㄈ╈柟叹毩?lt;/b>　　【例】:已知二叉樹的先序和中序序列，寫出該數(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。　　（四）小結引深　　樹是另外一種重要的非線性數(shù)據(jù)結構，這種數(shù)據(jù)結構，在日常生活中是十分常見的，二叉樹是一種很有用的非線性結構，研究二叉樹的性質以及二叉樹的遍歷具有十分重要

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

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

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

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

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

溫馨提示

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

偷窥国产在线91,亚洲无线国产观看原创,日本精品aⅴ一区二区三区,久久九九兔免费精品6

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

文檔簡介

溫馨提示

最新文檔

評論

偷窥国产在线91,亚洲无线国产观看原创,日本精品aⅴ一区二区三区,久久九九兔免费精品6

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

文檔簡介

溫馨提示

最新文檔

評論

免費下載