數(shù)據(jù)結(jié)構(gòu)-樹與二叉樹教學(xué)課件

Chapter6TreeBinarytree數(shù)據(jù)結(jié)構(gòu)-樹與二叉樹Chapter6TreeBinarytree教(學(xué)(內(nèi)(容1、樹和森林的概念2、二叉樹的定義、性質(zhì)及運(yùn)算3、二叉樹的存儲(chǔ)結(jié)構(gòu)4、遍歷二叉樹、樹、森林5、森林與二叉樹的轉(zhuǎn)換6、哈夫曼樹、哈夫曼編碼結(jié)點(diǎn)之間有分支樹型結(jié)構(gòu)(非線性結(jié)構(gòu))具有層次關(guān)系自然界:樹錦城學(xué)院例家譜計(jì)科系電子系文傳系人類社會(huì)信息工程通信微電子院系組織機(jī)構(gòu)通1班通2班通3班教(學(xué)(內(nèi)(容1、樹和森林的概念2、二叉樹的定義、性質(zhì)及運(yùn)算3、二叉樹的存儲(chǔ)結(jié)構(gòu)4、遍歷二叉樹、樹、森林5、森林與二叉樹的轉(zhuǎn)換6、哈夫曼樹、哈夫曼編碼結(jié)點(diǎn)之間有分支樹型結(jié)構(gòu)(非線性結(jié)構(gòu))具有層次關(guān)系自然界:樹錦城學(xué)院例家譜計(jì)科系電子系文傳系人類社會(huì)信息工程通信微電子院系組織機(jī)構(gòu)通1班通2班通3班樹的概念4樹的定義樹是n(n≥0)個(gè)結(jié)點(diǎn)的有限集。若n=0,稱為空樹;若n>0,則它滿足如下兩個(gè)條件√有且僅有一個(gè)稱之為根(Root)的結(jié)點(diǎn)√當(dāng)n>1,除根以外的其它結(jié)點(diǎn)分為m(m>0個(gè)互不相交的有限集T,T2灬…,Tm,其中每個(gè)集合又是一棵符合本定義的樹,并且稱為根的子樹例如TI根結(jié)點(diǎn)A只有根結(jié)點(diǎn)的樹go有13個(gè)結(jié)點(diǎn)的樹A是根;其余數(shù)據(jù)元素分成三個(gè)互不相交的子集T1={B,E,F,K,L};T2={C,G};T3={D,H,JM},T1,T2,T3都是根A的子樹,且本身也是一棵樹。0OOGGOOR={<A,B>,<A,C>,<A,D>,<B,E><B,F>,<C,G>,<D,H>,<D,D>,<D,J>,<EK>,<E,L>,<H,M>}樹結(jié)構(gòu)和線性結(jié)構(gòu)作如下對(duì)照:線性結(jié)構(gòu)樹結(jié)構(gòu)存在唯一的沒有前驅(qū)的存在唯一的沒有前驅(qū)的“首元素”“根結(jié)點(diǎn)”存在唯一的沒有后繼的存在多個(gè)沒有后繼的尾元素”“葉子”其余元素均存在唯一的其余結(jié)點(diǎn)均存在唯一的“前驅(qū)元素”和唯一的“前驅(qū)(雙親)結(jié)點(diǎn)”和“后繼元素”多個(gè)“后繼(孩子)結(jié)點(diǎn)”樹的基本術(shù)語1層2層height百⊙o-324層結(jié)點(diǎn)結(jié)點(diǎn)的度葉十子結(jié)點(diǎn)有序樹子樹之間存在確定的次序關(guān)系無序樹子樹之間不存在確定的次序關(guān)系祖父伯父父親叔父家族樹就屬于有序樹。堂兄堂姐你堂弟侄