《數(shù)據(jù)結(jié)構(gòu)》教案PAGEPAGE1《數(shù)據(jù)結(jié)構(gòu)》教案【】授課時間1026第14次課授課章節(jié)6.2.3二叉樹的存儲結(jié)構(gòu)6.3.1遍歷二叉樹任課教師及職稱鄭志華教學(xué)方法與手段多媒體課時安排2《數(shù)據(jù)結(jié)構(gòu)》（C語言版）嚴(yán)蔚敏著，清華大學(xué)出版社教學(xué)目的與要求：6.2.3二叉樹的存儲結(jié)構(gòu)6.3.1遍歷二叉樹教學(xué)重點(diǎn)，難點(diǎn)：1.二叉樹的存儲結(jié)構(gòu)2.二叉樹的遍歷教學(xué)內(nèi)容：6.2.3二叉樹的存儲結(jié)構(gòu)一、二叉樹的順序存儲用一組連續(xù)的存儲單元存儲二叉樹的結(jié)點(diǎn)。#defineMaxsize100//二叉樹的最大結(jié)點(diǎn)數(shù)typedefTElemTypeSqBiTree[Maxsize];//0號單元存儲根結(jié)點(diǎn)SqBiTreebt;1.滿二叉樹的存儲2.一般二叉樹的存儲二、二叉樹的鏈?zhǔn)酱鎯Ρ硎?.二叉鏈表的表示及結(jié)點(diǎn)結(jié)構(gòu)“訪問”的含義可以很廣，如：輸出結(jié)點(diǎn)的信息等“遍歷”是任何類型均有的操作，對線性結(jié)構(gòu)而言，只有一條搜索路徑(因?yàn)槊總€結(jié)點(diǎn)均只有一個后繼)，故不需要另加討論。而二叉樹是非線性結(jié)構(gòu)，每個結(jié)點(diǎn)有兩個后繼，則存在如何遍歷即按什么樣的搜索路徑遍歷的問題。二、遍歷算法?DLR前序的遍歷算法若二叉樹為空樹，則空操作；否則，（1）訪問根結(jié)點(diǎn)；（2）先序遍歷左子樹；（3）先序遍歷右子樹。LDR中序的遍歷算法若二叉樹為空樹，則空操作；否則，（1）中序遍歷左子樹；（2）訪問根結(jié)點(diǎn)；（3）中序遍歷右子樹。LRD后序的遍歷算法若二叉樹為空樹，則空操作；否則，（1）中序遍歷左子樹；（2）訪問根結(jié)點(diǎn)；（3）中序遍歷右子樹。三、算法的遞歸描述voidPreorder(BiTreeT）{//先序遍歷二叉樹if(T！=NULL){visit(T->data);//訪問結(jié)點(diǎn)Preorder(T->lchild);//遍歷左子樹Preorder(T->rchild);//遍歷右子樹}}例如圖所示的二叉樹表達(dá)式(a+b*(c-d)-e/f)前序遍歷生成二叉樹算法CreateBiTree(BiTree*T){charch;ch=getchar()if(ch=='')T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T–>data=ch;CreateBiTree(T–>lchild);CreateBiTree(T–>rchild);}returnOK;}復(fù)習(xí)思考題、作業(yè)題：1.假設(shè)一棵二叉樹的先序序列為EBADCFHGIKJ，中序序列為ABCDEFGHIJK，請畫出該二叉樹。2．已知二叉樹有50個葉子結(jié)點(diǎn)，則該二叉樹的總結(jié)點(diǎn)數(shù)至少應(yīng)有多少個？3．

給出滿足下列條件的所有二叉樹：①

前序和后序相同；②

中序和后序相同；③

前序和后序相同4．n個結(jié)點(diǎn)的K叉樹，若用具有k個child域的等長鏈結(jié)點(diǎn)存儲樹的一個結(jié)點(diǎn)，則空的Child域有多少個？5．畫出與下列已知序列對應(yīng)的樹Ｔ：樹的先根次序訪問序列為GFKDAIEBCHJ；樹的后根次序訪問序列為DIAEKFCJHBG。下次課預(yù)習(xí)要點(diǎn)線索二叉樹實(shí)施情況及教學(xué)效果分析按預(yù)定計劃順利進(jìn)行，效果良好學(xué)院審核意見