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

1、二叉樹遍歷的實(shí)現(xiàn)與教學(xué)演示畢業(yè)論文(設(shè)計(jì)) 本科生畢業(yè)論文設(shè)計(jì)題 目: 二叉樹遍歷的實(shí)現(xiàn)與教學(xué)演示 目 錄摘要關(guān)鍵字1abstract(key words)1前言21 二叉樹的概述21.1 二叉樹的定義21.2 二叉樹的性質(zhì)31.3 二叉樹的存儲(chǔ)結(jié)構(gòu)42 二叉樹的遍歷62.1 常用的二叉樹遍歷的算法62.2二叉樹遍歷的c程序演示過程92.3 非遞歸遍歷二叉樹122.4 二叉樹遍歷算法的應(yīng)用143基于flash的二叉樹遍歷課件應(yīng)用實(shí)現(xiàn)153.1課件簡(jiǎn)介153.2結(jié)構(gòu)設(shè)計(jì)分析153.3主要功能164 教學(xué)設(shè)計(jì)18結(jié)束語(yǔ)20參考文獻(xiàn)21致 謝22二叉樹遍歷的實(shí)現(xiàn)與教學(xué)演示摘要: 所有數(shù)據(jù)結(jié)構(gòu)中,樹是

2、非常重要的一種,尤其是二叉樹的遍歷,學(xué)習(xí)者是應(yīng)該牢固掌握的。在學(xué)習(xí)了二叉樹的存儲(chǔ)結(jié)構(gòu)之后,學(xué)生開始接觸了二叉樹的遍歷。很多學(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ù)與課程整合的角度,制作flash課件應(yīng)用于教學(xué)中,提高教學(xué)質(zhì)量。從而更好的

3、進(jìn)行課堂教學(xué),使學(xué)生更清楚、更容易的理解二叉樹的遍歷過程。關(guān)鍵字: 二叉樹; 遍歷; 多媒體abstract: all 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 contact with a binary tree

4、 traversal. many students will feel more or less some confusion appears to be simple recursive algorithm, ergodicll understand the process, may not be able to clear at a glance. the main reason lies in the implementation of binary tree traversal of the more complicated process, it is not easy to und

5、erstand, students will lose interest in this, so if on for students in understanding have a certain degree of difficulty. in this paper, the binary tree traversal of the implementation process to give a visual presentation of the teaching, mainly through the form of graphics display, you can at a gl

6、ance, while on the side of presentation so that students understand and learn. information technology and also from the perspective of curriculum integration, the production of courseware used in flash teaching, improve teaching quality. in order to better classroom teaching so that students more cl

7、early and more easily understand the process of binary tree traversal. keywords: binary tree; ergodic; multimedia 前言 樹是另外一種非線性數(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)被訪問一次,而且僅被訪問一次。

8、真正理解這一運(yùn)算的實(shí)現(xiàn)及其含義有助于許多二叉樹運(yùn)算的實(shí)現(xiàn)及算法設(shè)計(jì)。然而,許多初學(xué)者開始時(shí)的學(xué)習(xí)效果不理想,原因是較難理解其內(nèi)在規(guī)律。二叉樹的遍歷方法及相應(yīng)過程如下。1 二叉樹的概述1.1 二叉樹的定義 定義: 二叉樹是nn0個(gè)結(jié)點(diǎn)的有限集,它或?yàn)榭諛鋘0,或由一個(gè)根結(jié)點(diǎn)和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構(gòu)成。圖1-1圖1-1 特點(diǎn): 每個(gè)結(jié)點(diǎn)至多有2 棵子樹即不存在度大于2的結(jié)點(diǎn)二叉樹的子樹有左、右分,且其次序不能任意顛倒。 二叉樹的五種基本形態(tài):(如圖1-2)(圖1-2)1.2 二叉樹的性質(zhì) 【性質(zhì)1】在二叉樹的第 i 層上至多有2i-1個(gè)結(jié)點(diǎn) 證明:用數(shù)學(xué)歸納法證明。 ? i

9、1時(shí),只有一個(gè)根結(jié)點(diǎn),2=10是對(duì)的。 ? 假設(shè)對(duì)所有j1ji命題成立,即第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 故命題得證 【性質(zhì)2】深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)k1 由性質(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)之和為: 【性質(zhì)3】 對(duì)于任意一棵二叉樹bt,如果度為0的結(jié)點(diǎn)個(gè)數(shù)為n0,度為2的結(jié)

10、點(diǎn)個(gè)數(shù)為n2,則n0n2+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ù)為: nn0+n1+n2(1) 再查看一下分支數(shù)。在二叉樹中,除根結(jié)點(diǎn)之外,每個(gè)結(jié)點(diǎn)都有一個(gè)從上向下的分支指向,所以,總的結(jié)點(diǎn)個(gè)數(shù)n與分支數(shù)b之間的關(guān)系為:nb+1。 又因?yàn)樵诙鏄渲?度為1的結(jié)點(diǎn)產(chǎn)生1個(gè)分支,度為2的結(jié)點(diǎn)產(chǎn)生2個(gè)分支,所以分支數(shù)b可以表示為:bn1+2n2。 將此式代入上式,得: nn1+2n2+1 (2) 用(1)式減去(2)式,并經(jīng)過調(diào)整后得到:n0n2+1。 如果一個(gè)深度為k的二叉樹擁有2k-1個(gè)結(jié)點(diǎn),則將它稱為

11、滿二叉樹。 滿二叉樹:(如圖) (圖1-3) 完全二叉樹:有一棵深度為h,具有n個(gè)結(jié)點(diǎn)的二叉樹,若將它與一棵同深度的滿二叉樹中的所有結(jié)點(diǎn)按從上到下,從左到右的順序分別進(jìn)行編號(hào),且該二叉樹中的每個(gè)結(jié)點(diǎn)分別與滿二叉樹中編號(hào)為1n的結(jié)點(diǎn)位置一一對(duì)應(yīng),則稱這棵二叉樹為完全二叉樹。 【性質(zhì)4】 具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 log2n+1。其中,log2n 的結(jié)果是不大于log2n的最大整數(shù)。 證明:假設(shè)具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為k,則根據(jù)性質(zhì)2可以得出: 2k-1-1n2k-1 將不等式兩端加1得到: 2k-1n2k 將不等式中的三項(xiàng)同取以2為底的對(duì)數(shù),并經(jīng)過化簡(jiǎn)后得到: k-1log2nk

12、 由此可以得到: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 (1in),都有:(1)如果i1,則結(jié)點(diǎn)i是這棵完全二叉樹的根,沒有雙親;否則其雙親結(jié)點(diǎn)的編號(hào)為 i/2。(2)如果2in,則結(jié)點(diǎn)i沒有左孩子;否則其左孩子結(jié)點(diǎn)的編號(hào)為2i。(3)如果2i+1n,則結(jié)點(diǎn)i沒有右孩子;否則其右孩子結(jié)點(diǎn)的編號(hào)為2i+1。 下面我們利用數(shù)學(xué)歸納法證明這個(gè)性質(zhì)。 我們首先證明(2)和(3)。 當(dāng)i1時(shí),若n3,則根的左、右孩子的編號(hào)分別是2,3;若n3,則根沒有右孩子;若n2,則根將沒有左、右孩

13、子;以上對(duì)于(2)和(3)均成立。1.3 二叉樹的存儲(chǔ)結(jié)構(gòu) 二叉樹也可以采用兩種存儲(chǔ)方式:順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。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)。(圖1-4) 在c語(yǔ)言中,這種存儲(chǔ)形式的類型定義如下所示:#define _tree_node_size 100typedef struct entrytype item_tree_node_size;/根存儲(chǔ)在下標(biāo)為1的數(shù)組單元中int n;/當(dāng)前完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)qbtree; 這種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是空間利用率

14、高、尋找孩子和雙親比較容易。下面我們給出完全二叉樹在這種存儲(chǔ)形式下的操作算法。(1)構(gòu)造一棵完全二叉樹void createbtreeqbtree *bt,entrytype item ,int nif n_tree_node_size n_tree_node_size-1;for i1; in;i+ bt-itemiitemi;bt-nn;(2)獲取給定結(jié)點(diǎn)的左孩子 int leftchildqbtree bt,int nodeif 2*nodebt.n return 0; else return 2*node;rightchildbt,node與這個(gè)操作類似,讀者可試著自行完成。(3)獲取

15、給定結(jié)點(diǎn)的雙親 int parentqbtree bt,int nodeif 1node&nodebt.n return i/2;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ì)必造成空間利用率的下降。在這種情況下,就應(yīng)該考慮使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 常見的二叉樹結(jié)點(diǎn)結(jié)構(gòu)如下所示:lchilditemrchild(圖1-5) 其中,lchild和rchild是分別指向該結(jié)點(diǎn)左孩子和右孩子的指針,item是數(shù)據(jù)元素的內(nèi)容。在c語(yǔ)言中的類型定義為:typedef

16、struct btnodeentrytype item;struct btnode *lchild,*rchlid;btnode,*btree; 下面(圖1-6)是一棵二叉樹及相應(yīng)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。(圖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)如下所示。 lchilditemrchildparent(圖1-4)2 二叉樹的遍歷2.1 常用的二叉樹遍歷的算法 在二叉樹的一些應(yīng)用中,常常要求在樹中查找具有某種特征的結(jié)點(diǎn),或者對(duì)樹種全部結(jié)點(diǎn)逐一進(jìn)行某種處理.這就提出了一個(gè)遍歷二叉樹樹的問題,即如何按一

17、定的規(guī)律和次序訪問樹中的每個(gè)結(jié)點(diǎn),使得每個(gè)結(jié)點(diǎn)被訪問一次,而且僅彼訪問一次。 所謂二叉樹的遍歷,是指按一定的次序訪問樹中的所有結(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意義上的線性序列。也就是說,遍歷操作使非線性結(jié)構(gòu)線性化。 二叉樹常用的遍歷有先序遍歷、中序遍歷、后序遍歷。所謂先序、中序、后序,區(qū)別在于訪問根結(jié)點(diǎn)的順序

18、。 這里,若t為根指針,則遍歷左右子樹時(shí),是分別遍歷以t-lchild 和t-rchild 為根指針的子樹。 visit bitree *t printf“%c”,t-data; 先序遍歷: 若二叉樹非空,則: 訪問根結(jié)點(diǎn) 先序遍歷左子樹 先序遍歷右子樹 對(duì)應(yīng)遞歸算法如下: void preorderbitree *t if t!null printf%dt,t-data; preordert-lchild; preordert-rchild; 采用先序遍歷得到的訪問結(jié)點(diǎn)序列稱為先序遍歷序列,先序遍歷序列的特點(diǎn)是:其第一個(gè)元素值為二叉樹中根結(jié)點(diǎn)的數(shù)據(jù)值。 如圖所示的二叉樹,先序遍歷序列為: e

19、 c b a j f m k z 中序遍歷: 若二叉樹非空,則: (1)中序遍歷左子樹 (2)訪問根結(jié)點(diǎn) (3)中序遍歷右子樹 對(duì)應(yīng)遞歸算法如下: void preorderbitree *t if t!null preordert-lchild; printf%dt,t-data; preordert-rchild; 采用中序遍歷得到的訪問結(jié)點(diǎn)序列稱為中序遍歷序列,中序遍歷序列的特點(diǎn)是:若已知二叉樹的根結(jié)點(diǎn)的數(shù)據(jù)值,以應(yīng)該數(shù)據(jù)值為屆,將中序遍歷序列分為兩部分,前半部分為左子樹的中序遍歷序列,后半部分為右子樹的中序遍歷序列。 如圖所示的二叉樹,中序遍歷序列為: a b c e f j k m

20、z后序遍歷:若二叉樹非空,則:(1)后序遍歷左子樹(2)后序遍歷右子樹(3)訪問根結(jié)點(diǎn)對(duì)應(yīng)遞歸算法如下:void preorderbitree *tif t!null preordert-lchild; preordert-rchild; printf%dt,t-data; 采用后序遍歷得到的訪問結(jié)點(diǎn)序列稱為后序遍歷序列,后序遍歷序列的特點(diǎn)是:其最后一個(gè)元素值為二叉樹中根結(jié)點(diǎn)的數(shù)據(jù)值。 如圖所示的二叉樹,后序遍歷序列為: a b c f k z m j e(圖2-1)2.2二叉樹遍歷的c程序演示過程 下圖是程序執(zhí)行界面,用c語(yǔ)言實(shí)現(xiàn)的二叉樹遍歷的程序。(圖2-2) 下圖是遍歷執(zhí)行的具體過程,將

21、三種遍歷各執(zhí)行一遍。(圖2-3)以下是二叉樹遍歷執(zhí)行的過程部分代碼:/*用圖形顯示創(chuàng)建好的樹*/void drawtreetree *tift!null setcolorblack; setfillstylesolid_fill,black; fillellipset-x,t-y,9,9; setcolorwhite; circlet-x,t-y,10; /*畫圓*/ sprintfstr,%c,t-data;/*將內(nèi)容轉(zhuǎn)換成字符串輸出*/ outtextxyt-x-3,t-y-2,str; ift-lchild!null/*左子樹*/ linet-x-5,t-y+12,t-lchild-x+

22、5,t-lchild-y-12; drawtreet-lchild; ift-rchild!null/*右子樹*/ linet-x+5,t-y+12,t-rchild-x-5,t-rchild-y-12; drawtreet-rchild; /*遍歷時(shí)顯示每個(gè)結(jié)點(diǎn)的過程*/void drawnodetree *t,int colorsetcoloryellow; setfillstylesolid_fill,yellow; fillellipset-x,t-y,10,10; setcolorred; sprintfstr,%c,t-data;/*將內(nèi)容轉(zhuǎn)換成字符串輸出*/ outtextxyt

23、-x-3,t-y-2,str; setcolorcolor; outtextxys.x,s.y,str; setcolorred; sprintfstr,%d,s.num;/*將遍歷次序用數(shù)字顯示在樹的結(jié)點(diǎn)上*/ outtextxyt-x-3,t-y-20,str; s.num+; sleep1;/*畫菜單的效果圖*/void drawtangle2int i;setcolor14; /*黃*/setlinestyle0,0,3; /*實(shí)線,三個(gè)像素的寬度*/line150,200,320,200;line149,199,149,400;line149,400,320,400;line320,

24、200,320,400;fori203;i398;i+ /*劃里面的深灰背景,是不斷的劃線來實(shí)現(xiàn)*/setcolor8;line151,i,318,i;delay4000;/*生成二叉樹,h表示層次,t表示橫坐標(biāo),w表示結(jié)點(diǎn)左右子樹的寬度,隨機(jī)數(shù)n確定結(jié)點(diǎn)是空或非空,如n為0,則為空*,但要限定確保結(jié)點(diǎn)數(shù)不少于三個(gè)*/tree *inittreeint h,int t,int wchar ch; int n;/*自動(dòng)建立時(shí)隨機(jī)賦值判斷是否是null的標(biāo)志*/ tree *node; nrandom5; ifn0&nodenum3/*隨機(jī)賦值時(shí)候確保自動(dòng)建立的二叉樹有三個(gè)結(jié)點(diǎn)*/ch.; els

25、e ch65+random25; ifch./*輸入空格代表null*/return null; else ifh6|nodenum26/*如果樹的層次已經(jīng)到5或者結(jié)點(diǎn)樹到達(dá)26個(gè)就自動(dòng)返回null*/ return null; nodetree*mallocsizeoftree; node-datach; node-xt;/*樹的x坐標(biāo)是傳遞過來的橫坐標(biāo)*/ node-yh*50;/*樹的y坐標(biāo)與層次大小有關(guān)*/ nodenum+; node-lchildinittreeh+1,t-w,w/2; node-rchildinittreeh+1,t+w,w/2; return node;/*前序

26、遍歷*/void preordertree *tift!null s.x+15; drawnodet,9; preordert-lchild; preordert-rchild; 2.3 非遞歸遍歷二叉樹先序非遞歸算法: 假設(shè):t是要遍歷樹的根指針,若t ! null對(duì)于非遞歸算法,引入棧模擬遞歸工作棧,初始時(shí)棧為空。問題:如何用棧來保存信息,使得在先序遍歷過左子樹后,能利用棧頂信息獲取t的右子樹的根指針?方法1:訪問t-data后,將t入棧,遍歷左子樹;遍歷完左子樹返回時(shí),棧頂元素應(yīng)為t,出棧,再先序遍歷t的右子樹。方法2:訪問t-data后,將t-rchild入棧,遍歷左子樹;遍歷完左子樹

27、返回時(shí),棧頂元素應(yīng)為t-rchild,出棧,遍歷以該指針為根的子樹。void preorderbitree t,status *visit elemtype e? initstacks; while t!null | !stackemptys while t ! null visitt-data ; pushs,t; t t-lchild; if !stackemptys pops,t; t t-rchild; ?中序非遞歸算法:思路: t是要遍歷樹的根指針,中序遍歷要求在遍歷完左子樹后,訪問根,再遍歷右子樹。問題:如何用棧來保存信息,使得在中序遍歷過左子樹后,能利用棧頂信息獲取t指針?方法:

28、先將t入棧,遍歷左子樹;遍歷完左子樹返回時(shí),棧頂元素應(yīng)為t,出棧,訪問t-data,再中序遍歷t的右子樹。 算法:void inorderbitree t, status *visit elemtype e/ 流程圖如右,當(dāng)型循環(huán) initstacks; while t!null | !stackemptys while t ! null pushs,t; t t-lchild; if !stackemptys pops, t; visitt-data; t t-rchild; 后序非遞歸算法:思路: t是要遍歷樹的根指針,后序遍歷要求在遍歷完左右子樹后,再訪問根。需要判斷根結(jié)點(diǎn)的左右子樹是否

29、均遍歷過。 可采用標(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 stackelementbitree data;char? tag;stackelemtype;算法:void postorderbitree t, status *visit elemtype e/ 流程圖如右,當(dāng)型循環(huán) initstacks; while t!null | !stackemptys while t ! null pushs,t,0;

30、t t-lchild; while !stackemptys & gettoptags1 pops, t; visitt-data; if !stackemptys settoptags, 1;? / 設(shè)置棧頂標(biāo)記 t gettoppointers; / 取棧頂保存的指針 t t-rchild; else break; 2.4 二叉樹遍歷算法的應(yīng)用 前面曾指出二叉樹的遍歷算法是二叉樹算法的基礎(chǔ),下面結(jié)合實(shí)例對(duì)此展開討論。根據(jù)所運(yùn)用的基本思想來分,可劃分為兩個(gè)層次,其一是簡(jiǎn)單、直接的應(yīng)用,其二是具有一定深度的方法的應(yīng)用。 可以證明,二叉樹的遍歷算法對(duì)樹t中每個(gè)結(jié)點(diǎn)都會(huì)執(zhí)行一次且執(zhí)行一次訪問結(jié)點(diǎn)的

31、操作。其中訪問結(jié)點(diǎn)的操作可以是多種形式及多個(gè)操作,例如輸出結(jié)點(diǎn)值。利用這一特點(diǎn),適當(dāng)修改訪問操作的內(nèi)容,便可以得到許多問題的求解算法。下面給出幾個(gè)典型問題的求解。 例:設(shè)計(jì)算法,按中序次序輸出二叉樹t中度為2的結(jié)點(diǎn)的值。 解:本算法的要求與中序遍歷算法既有相同之處,又有不同之處。相同之處是輸出次序均為中序;不同之處是此處不適輸出每個(gè)結(jié)點(diǎn)的值,而是僅輸出其中的度為2的結(jié)點(diǎn),即有條件輸出。為此,將中序遍歷算法中的訪問結(jié)點(diǎn)的操作改為條件輸出結(jié)點(diǎn)的值即可。算法如下:void inorderbnode *t ift!null inordert-lchild; ift-lchild!null&t-rchi

32、ld!null printf%dt,t-data; inordert-lchild; 例:設(shè)計(jì)算法,求二叉樹t的結(jié)點(diǎn)數(shù)。 解:本算法不是要輸出每個(gè)結(jié)點(diǎn)的值,所要求的僅是求出其中的結(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 inorderbnode *t ift!null inordert-lchild; n+; inordert-lchild; 例:設(shè)計(jì)算法求解給定二叉樹的高度。 解:由于求二叉樹的高度難以采用由遍歷

33、算法簡(jiǎn)單變化的方式來實(shí)現(xiàn),因此,需要采用本小姐所討論的方法來求解?，F(xiàn)分析如下: 若t為空時(shí),則其高度為0,求解結(jié)束。 否則,若t不為空,其高度應(yīng)是其左、右子樹高度的最大值再加1.假設(shè)其左右子樹的高度能求解出來,則算法求解容易實(shí)現(xiàn)。其左右子樹的高度的求解又可以通過遞歸調(diào)用本算法來完成。據(jù)此討論可寫出幾種形式的算法,下面給出有值函數(shù)形式的算法。 設(shè)函數(shù)int high(bnode *t)表示返回二叉樹t的高度,因此hight-lchild、hight-rchild分別代表t的左右子樹的高度,由前面的討論可得算法如下:int high(bnode *t)iftnullreturn 0;else re

34、turn hight-lchild,hight-rchild+1;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í)興趣,減少枯感,從而增強(qiáng)學(xué)習(xí)效果。 為此,筆者編寫了一個(gè)二叉樹遍歷的flash教學(xué)課件,嘗試著將自己的心得體會(huì)融入課件編寫之中,在選擇界面設(shè)計(jì)、交互方式等方面盡量多從學(xué)生的角度出發(fā),希望這樣能起到拋磚引玉的作用。3.2結(jié)構(gòu)設(shè)計(jì)分析 確定課件的總體結(jié)構(gòu):整個(gè)界面是有六個(gè)按鈕組成,其中一個(gè)是退出按鈕,其它導(dǎo)航按鈕分別代表五個(gè)教學(xué)環(huán)

35、節(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) 3.3主要功能 其中每個(gè)模塊所實(shí)現(xiàn)的功能如下: 點(diǎn)擊“新課導(dǎo)入”按鈕進(jìn)入導(dǎo)入,在本界面中展示了一副手繪九寨溝旅游風(fēng)景圖,通過圖片的變化,可發(fā)現(xiàn)與二叉樹相似,由此引出二叉樹遍歷的概念,給學(xué)生一個(gè)初步的印象。 圖(3-3) 點(diǎn)擊“新課學(xué)習(xí)”按鈕進(jìn)入本節(jié)課的新授課內(nèi)容,在此界面里主要描述了二叉樹遍歷的概念,以及本課所用到的二叉樹的模型,通過“下一頁(yè)”的按鈕,可分別對(duì)二叉樹的三種遍歷進(jìn)行講解,并可通過遍歷演示的按鈕看到直觀清晰的二叉樹遍歷過程,最后,再通過典型的例題分析對(duì)二

36、叉樹的遍歷進(jìn)一步的了解。其中在每個(gè)分界面中都有“返回”按鈕,點(diǎn)“返回”按鈕可返回到主界面。下圖是遍歷的演示制作過程。 圖(3-4) 圖(3-5) 點(diǎn)擊“鞏固練習(xí)”按鈕進(jìn)入本課的練習(xí)題,并可以看到例題分析與答案。點(diǎn)“返回”按鈕可返回到主界面。 點(diǎn)擊“本課小結(jié)”按鈕進(jìn)入本課總結(jié)界面,“返回”按鈕可返回到主界面。 點(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ì)中第五章函數(shù)中的第二、三節(jié),是本章的基礎(chǔ)。本節(jié)課主要學(xué)習(xí)認(rèn)識(shí)二叉樹,實(shí)現(xiàn)二叉樹遍歷。二、教學(xué)目標(biāo)1、知識(shí)目標(biāo): (1) 理

37、解二叉樹的性質(zhì)與結(jié)構(gòu) (2) 掌握二叉樹的三種遍歷 (3) 能獨(dú)立完成二叉樹遍歷的執(zhí)行2、情感目標(biāo): 學(xué)習(xí)完本節(jié)課,學(xué)生對(duì)于程序編寫的興趣在以前的基礎(chǔ)上有更大的加深。3、技能目標(biāo): 學(xué)完本節(jié)課后,學(xué)生應(yīng)該學(xué)會(huì)二叉樹遍歷的執(zhí)行,并且根據(jù)二叉樹與二叉樹的遍歷,能應(yīng)用的更廣泛。三、教學(xué)方法 講授法、演示法。 四、教學(xué)過程 首先大家一起回憶上節(jié)課學(xué)習(xí)的內(nèi)容,回答二叉樹的定義、基本性質(zhì)和存儲(chǔ)結(jié)構(gòu)。(一)新課導(dǎo)入 出示課件,讓同學(xué)們懂得本節(jié)課的重點(diǎn)。提問同學(xué)們有沒有去過外地旅游,然后播放課件上的旅游景點(diǎn)圖片,然后通過旅游時(shí)到每個(gè)景點(diǎn)照相留念的方式可知道,要想每個(gè)景點(diǎn)都走到,那得采取某種方式去合理安排,否則會(huì)漏掉一些景點(diǎn),這個(gè)就類似二叉樹的遍歷,引入新課。(二)新課學(xué)習(xí)1.知識(shí)的理解 逐個(gè)講解遍歷的種類和相應(yīng)的過程 (1)先序遍歷 若二叉樹為空,則結(jié)束遍歷操作;否則訪問根結(jié)點(diǎn); 先序遍歷左子樹; 先序遍歷右子樹。 (2)中序遍歷 若二叉樹為空,則結(jié)束遍歷操作;否則 中序遍歷左子樹; 訪問根結(jié)點(diǎn); (3)后序遍歷 若二叉樹為空,則結(jié)束遍歷操作;否則 后序遍歷左子樹; 后序遍歷右子樹; 訪問根結(jié)點(diǎn)。2