第6章實(shí)驗(yàn)-二叉樹的建立與遍歷-教案

《第6章實(shí)驗(yàn)-二叉樹的建立與遍歷-教案》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、湖北第二師范學(xué)院計(jì)算機(jī)學(xué)院2012至　2013學(xué)年第　1學(xué)期　　《數(shù)據(jù)結(jié)構(gòu)》　　課程教案　課程編碼：B0310008課程類別：專業(yè)基礎(chǔ)學(xué)分：_3.5_總學(xué)時(shí)/周學(xué)時(shí)：68/5上課學(xué)時(shí)：54實(shí)驗(yàn)學(xué)時(shí)：18開課時(shí)間：2012年9月4日第1周至第17周　　　　授課年級(jí)、專業(yè)、班級(jí)：2011級(jí)、計(jì)算機(jī)科學(xué)與技術(shù)(嵌入式)、11計(jì)科4使用教材：《數(shù)據(jù)結(jié)構(gòu)－－C語言描述》（第二版）授課教師與職稱：　　　魯靜講師______________周次第周時(shí)間年月日第節(jié)授課方式（請(qǐng)打√）理論課□討論課□實(shí)驗(yàn)課√習(xí)題課□其他□課時(shí)安排2授課

2、題目（教學(xué)章、節(jié)或主題）：第6章樹和二叉樹。主題：二叉樹的建立與遍歷（實(shí)驗(yàn)課）。教學(xué)目的、要求（分掌握、熟悉、了解三個(gè)層次）：熟練掌握二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)，以及二叉樹建立的基本算法。熟悉二叉樹前序、中序、后序遍歷的遞歸與非遞歸算法。了解二叉樹的層次遍歷算法。教學(xué)重點(diǎn)及難點(diǎn)：重點(diǎn)：二叉樹前序、中序、后序遍歷的遞歸與非遞歸算法。難點(diǎn)：二叉樹遍歷的遞歸算法。教學(xué)基本內(nèi)容方法及手段教學(xué)內(nèi)容及板書綱要：儀器介紹：WindowsXP操作系統(tǒng)、VC++6.0編譯環(huán)境。第6章樹和二叉樹實(shí)驗(yàn)一、二叉樹的建立1.實(shí)驗(yàn)?zāi)康牧私舛鏄涞?/p>

3、結(jié)構(gòu)特點(diǎn)及有關(guān)概念，掌握二叉樹建立的基本算法2.實(shí)驗(yàn)內(nèi)容依序輸入元素值，以鏈表方式建立二叉樹，并輸出節(jié)點(diǎn)內(nèi)容3.實(shí)驗(yàn)要點(diǎn)及說明先依序輸入元素值，并存入數(shù)組nodelist中，再用函數(shù)insert_node一一插入二叉樹的節(jié)點(diǎn)建立成二叉樹，節(jié)點(diǎn)的建立是將左子針指向左子樹，右子針指向右子樹。最后用print_btree輸出節(jié)點(diǎn)內(nèi)容。4.二叉樹結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)typedefstructbnode{intdata;//結(jié)點(diǎn)數(shù)據(jù)類型structbnode*lchild,*rchild;//定義左、右孩子為指針型}btree;5.

4、相關(guān)操作btree*insert_node(btree*root,intnode)//插入二叉樹的節(jié)點(diǎn)btree*create_btree(intdata[],intlen)//建立二叉樹voidprint_btree(btree*root)//打印二叉樹二、二叉樹的前序遍歷1.實(shí)驗(yàn)?zāi)康牧私馇靶虮闅v二叉樹的概念，掌握前序遍歷二叉樹的算法2.實(shí)驗(yàn)內(nèi)容以鏈表方式建立二叉樹，并以前序遍歷二叉樹的方式輸出節(jié)點(diǎn)內(nèi)容3.實(shí)驗(yàn)要點(diǎn)及說明先輸入元素值建立二叉樹，然后前序遍歷該二叉樹。前序遍歷的規(guī)則是根結(jié)點(diǎn)最先遍歷，其次左子樹，最后右

5、子樹。4.參考程序voidpreorder1(bitree*root)//前序非遞歸遍歷二叉樹{bitree*p,*s[100];inttop=0;//top為棧頂指針p=root;while((p!=NULL)

6、

7、(top>0)){while(p!=NULL){printf（"%d",p->data）;只給學(xué)生定義存儲(chǔ)結(jié)構(gòu)，要求學(xué)生完成二叉樹的建立。結(jié)合理論課知識(shí)，講解程序，幫助學(xué)生理解遞歸遍歷的算法。s[++top]=p;p=p->lchild;}p=s[top--];p=p->rchild;}}三、二叉樹的中序

8、遍歷1.實(shí)驗(yàn)?zāi)康牧私庵行虮闅v二叉樹的概念，掌握中序遍歷二叉樹的算法2.實(shí)驗(yàn)內(nèi)容以鏈表方式建立二叉樹，并以中序遍歷二叉樹的方式輸出節(jié)點(diǎn)內(nèi)容3.實(shí)驗(yàn)要點(diǎn)及說明先輸入元素值建立成二叉樹。中序遍歷的規(guī)則是先遍歷左子樹，其次根結(jié)點(diǎn)，最后遍歷右子樹，本程序是遞歸算法。4.參考程序voidinorder(btree*root)//中序遞歸遍歷二叉樹{if(root!=NULL){inorder(root->lchild);printf("%d",root->data);inorder(root->rchild);}}四、二叉樹的后

9、序遍歷1.實(shí)驗(yàn)?zāi)康牧私夂笮虮闅v二叉樹的概念，掌握后序遍歷二叉樹的算法。2.實(shí)驗(yàn)內(nèi)容以鏈表方式建立二叉樹，并以后序遍歷二叉樹的方式輸出節(jié)點(diǎn)內(nèi)容。3.實(shí)驗(yàn)要點(diǎn)及說明先輸入元素值，建立成二叉樹。后序遍歷的規(guī)則是先遍歷左子樹，其次遍歷右子樹，最后訪問根結(jié)點(diǎn)，本程序是遞歸算法。4.參考程序voidpostorder(btree*root)//后序遞歸遍歷二叉樹{if(root!=NULL){postorder(root->lchild);postorder(root->rchild);printf("%d",root->dat

10、a);}}結(jié)合理論課知識(shí)，講解程序，幫助學(xué)生理解遞歸遍歷的算法。本程序要求學(xué)生模仿二叉樹的前序、中序遍歷算法，自行完成。實(shí)驗(yàn)后記：（通過提問，幫助同學(xué)回顧本次課的主要內(nèi)容。）1．通過比較二叉樹遍歷的遞歸與非遞歸算法，深入理解遞歸的思想，思考為什么可以使用遞歸算法？2．靈活運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹的其它操作，如查找共同祖先，在符合條件的位置插入或者