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