數(shù)據(jù)結(jié)構(gòu)-課件-ly62森林和樹(shù)

第六章樹(shù)、二叉樹(shù)和森林二、二叉樹(shù)二叉樹(shù)的遍歷前序遍歷：根左子右子中序遍歷：左子根右子后序遍歷：左子右子根層次遍歷：逐層abdcegjkhfidbajgkehcfidbjkgheifcaabcdefghijk二、二叉樹(shù)線(xiàn)索化二叉樹(shù)定義二、二叉樹(shù)線(xiàn)索化二叉樹(shù)中序線(xiàn)索化二叉樹(shù)的遍歷二叉樹(shù)的中序線(xiàn)索化二、二叉樹(shù)二叉樹(shù)應(yīng)用舉例表達(dá)式運(yùn)算樹(shù)A+(B*(C-D))/E-F*(G+H)三、森林、樹(shù)、二叉樹(shù)樹(shù)的物理結(jié)構(gòu)父鏈結(jié)構(gòu)子鏈結(jié)構(gòu)子鏈-兄弟鏈結(jié)構(gòu)三、森林、樹(shù)、二叉樹(shù)樹(shù)與森林樹(shù)=根+子樹(shù)森林三、森林、樹(shù)、二叉樹(shù)樹(shù)的二叉樹(shù)表示樹(shù)二叉樹(shù)二叉樹(shù)樹(shù)Tree=(root,T1,…,Tn)BiTree=(root,Tl,Tr)三、森林、樹(shù)、二叉樹(shù)森林與二叉樹(shù)森林二叉樹(shù)二叉樹(shù)森林Forest=(T1,…,Tn)=((root,T11,…,T1m),…Tn)BiTree=(root,Tl,Tr)四、哈夫曼樹(shù)哈夫曼樹(shù)（最優(yōu)二叉樹(shù)）葉結(jié)點(diǎn)帶權(quán)的二叉樹(shù)樹(shù)的總權(quán)值：50*2+12*3+25*4+8*2+7*3+32*3=369四、哈夫曼樹(shù)哈夫曼樹(shù)（最優(yōu)二叉樹(shù)）哈夫曼樹(shù)四、哈夫曼樹(shù)哈夫曼算法初始時(shí)，將每個(gè)葉結(jié)點(diǎn)看作一個(gè)獨(dú)立的二叉樹(shù)，葉結(jié)點(diǎn)即根結(jié)點(diǎn)；重復(fù)n-1次：選出兩棵根結(jié)點(diǎn)權(quán)值最小的二叉樹(shù)；新增一個(gè)根結(jié)點(diǎn)；將選出的兩棵二叉樹(shù)作為新增根結(jié)點(diǎn)的左子和右子；新增根結(jié)點(diǎn)的權(quán)值為選出兩棵二叉樹(shù)根結(jié)點(diǎn)的權(quán)值之和；四、哈夫曼樹(shù)哈夫曼編碼定長(zhǎng)編碼與變長(zhǎng)編碼最優(yōu)變長(zhǎng)編碼——哈夫曼編碼a:100b:110c:111d:101e:0四、哈夫曼樹(shù)哈夫曼編碼編碼構(gòu)造信息編碼信息解碼a:100b:110c:111d:101e:0發(fā)送方接收方aebaec