武漢軟件工程職業(yè)學(xué)院數(shù)據(jù)結(jié)構(gòu)講義第14講-2叉樹(shù)、樹(shù)和森林(編輯修改稿)
2025-07-26 14:39 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 右孩子的次序是嚴(yán)格區(qū)分的。所以在討論二叉樹(shù)和一般樹(shù)之間的轉(zhuǎn)換時(shí)，為不引起混淆，就約定按樹(shù)上現(xiàn)有結(jié)點(diǎn)次序進(jìn)行轉(zhuǎn)換。1． 一般樹(shù)轉(zhuǎn)換為二叉樹(shù)將一般樹(shù)轉(zhuǎn)化為二叉樹(shù)的思路，主要根據(jù)樹(shù)的孩子－兄弟存儲(chǔ)方式而來(lái)，具體步驟為：（1） 加線。在各兄弟結(jié)點(diǎn)之間用虛線相連?？衫斫鉃槊總€(gè)結(jié)點(diǎn)的兄弟指針指向它的一個(gè)兄弟。（2） 抹線。對(duì)每個(gè)結(jié)點(diǎn)僅保留它與其最左孩子的連線，抹去該結(jié)點(diǎn)與其它孩子之間的連線?？衫斫鉃槊總€(gè)結(jié)點(diǎn)僅有一個(gè)孩子指針，讓它指向自己的第一個(gè)孩子。（3） 旋轉(zhuǎn)。把虛線改為實(shí)線從水平方向向下旋轉(zhuǎn)45176。，成右斜下方向。原書(shū)中實(shí)線成左斜下方向。這樣就形成一棵二叉樹(shù)。由于二叉樹(shù)中各結(jié)點(diǎn)的右孩子都是原一樹(shù)數(shù)中該結(jié)點(diǎn)的兄弟，而一般樹(shù)的根結(jié)點(diǎn)又沒(méi)有兄弟結(jié)點(diǎn)，因此所生成的二叉樹(shù)的根結(jié)點(diǎn)沒(méi)有右子樹(shù)。在所生成的二叉樹(shù)中某一結(jié)點(diǎn)的左孩子仍是原來(lái)樹(shù)中該結(jié)點(diǎn)的長(zhǎng)子，并且是它的最左孩子。圖4－5－3是一個(gè)由一般樹(shù)轉(zhuǎn)為二叉樹(shù)的實(shí)例。AB CDE FGHBAB CDE FGHAB CDE FGHAHE CDFG(a)(b
高考資料相關(guān)推薦
鄂ICP備17016276號(hào)-1