本模塊主要內(nèi)容1、樹與二叉樹的邏輯模型；2、二叉樹的基本性質(zhì)；3、二叉樹的存儲結(jié)構(gòu)；4、二叉樹的遍歷以及算法實現(xiàn)；層次結(jié)構(gòu)-樹與二叉樹5、樹、森林與二叉樹的；6、哈夫曼樹及應(yīng)用。二叉樹的順序存儲結(jié)構(gòu)；順序存儲的特點。本節(jié)目錄：本節(jié)內(nèi)容：二叉樹的存儲結(jié)構(gòu)；二叉樹的存儲結(jié)構(gòu)

順序存儲結(jié)構(gòu):用一組地址連續(xù)的存儲單元存儲結(jié)點。ACBEFABECF順序存儲結(jié)構(gòu)?存在的問題：結(jié)點間的關(guān)系？12345二叉樹的存儲結(jié)構(gòu)

順序存儲結(jié)構(gòu):用一組地址連續(xù)的存儲單元存儲結(jié)點。ACBEFABECF順序存儲結(jié)構(gòu)存在的問題：結(jié)點間的關(guān)系？12345二叉樹的存儲結(jié)構(gòu)ABECF

順序存儲結(jié)構(gòu):將二叉樹補充為完全二叉樹，按照完全二叉樹的結(jié)構(gòu)進行存儲。ABCDEFGHIKAEBCHDGIFK12437691085二叉樹的存儲結(jié)構(gòu)順序存儲12345678910順序存儲結(jié)構(gòu)：用一組地址連續(xù)的存儲單元，依次自上而下、自左至右存儲完全二叉樹上的結(jié)點元素。ACBEFABE^C順序存儲結(jié)構(gòu)結(jié)點父子關(guān)系，簡單地由序列號決定。F二叉樹的存儲結(jié)構(gòu)123456abcd^^順序存儲eaebcd順序存儲結(jié)構(gòu)：將二叉樹還原為完全二叉樹的形態(tài)，進行順序存儲。1234567二叉樹的存儲結(jié)構(gòu)ABCDE137654982ABCD13111012EABC∧∧D∧∧∧∧∧∧E12345678910111213造成空間嚴(yán)重浪費！二叉樹的存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)數(shù)據(jù)1^3∧7^15∧31編號1…3…7…15…31二叉樹的存儲結(jié)構(gòu)順序存儲結(jié)…最浪費空間的樹小結(jié)：順序存儲結(jié)構(gòu)的基本思想；順序存儲結(jié)構(gòu)的特點；本節(jié)內(nèi)容：順序存儲結(jié)構(gòu)的實現(xiàn)方法二叉樹的存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)的基本原理；鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點。本節(jié)目錄：本節(jié)內(nèi)容：二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)；二叉樹的存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)：設(shè)計不同的結(jié)點結(jié)構(gòu)來存儲結(jié)點元素以及元素間的關(guān)系。ABCDELCBA鏈表DE^線性表L:

datanext結(jié)點結(jié)構(gòu)指明后繼結(jié)點，結(jié)點間的關(guān)系二叉樹的存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)：設(shè)計不同的結(jié)點結(jié)構(gòu)來存儲結(jié)點元素以及元素間的關(guān)系。ACBEF

datalchildrchild

A

B

E

C

F結(jié)點結(jié)構(gòu)二叉樹二叉鏈表存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)中結(jié)點的定義：struct

BitNode{

intdata;/*結(jié)點數(shù)據(jù)*/

struct

BitNodelchild;*rchild/*左右孩子指針*/}*LinkBitTree;

H

E

D

F

G

I

ACBFCBDGIHEA二叉樹二叉鏈表存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)

存儲結(jié)構(gòu)特點：N個結(jié)點的二叉樹有n+1空指針閾。指明后繼結(jié)點，結(jié)點間的關(guān)系

H

E

D

F

G

M

A