關(guān)于二叉樹的順序存儲(chǔ)

石俊豪

今天復(fù)習(xí)到二叉樹部分，看完輔導(dǎo)書的講義，說二叉樹的順序存儲(chǔ)就是
“用一組地址連續(xù)的存儲(chǔ)單元依次自上而下、自左至右存儲(chǔ)完全二叉樹上的結(jié)點(diǎn)元素，即將完全二叉樹上編號(hào)為i的結(jié)點(diǎn)元素存儲(chǔ)在所定義的一位數(shù)組中下標(biāo)為i-1的分量中。對(duì)于一般二叉樹，則應(yīng)將其每個(gè)結(jié)點(diǎn)與完全二叉樹上的結(jié)點(diǎn)對(duì)照，存儲(chǔ)在一位數(shù)組的響應(yīng)分量中。”
OK如果過路的高手覺得上述講義有錯(cuò)歡迎直接指出多謝。

然后后面有一道習(xí)題，
某二叉樹的結(jié)點(diǎn)采用順序存儲(chǔ)結(jié)構(gòu)如下圖所示：
0 1 2 3 4 5 6 7 8 9 10 11
E A H F 0 B 0 C D G 0 0
畫出該二叉樹
so

哪位大俠能告訴我這個(gè)G點(diǎn)該劃到哪？在此先多謝了


追加：剛才又遇到一個(gè)問題。輔導(dǎo)書上認(rèn)為“加上線索的二叉樹稱之為線索二叉樹。對(duì)二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程叫做線索化。”

當(dāng)二叉樹沒線索化的時(shí)候會(huì)必然地出現(xiàn)一些空域(二叉鏈表)，線索化就是利用這些空域來建立線索(感覺就是廢物利用了)。線索化的時(shí)候會(huì)在原來的根節(jié)點(diǎn)上再加上一個(gè)頭結(jié)點(diǎn)。如果有了這個(gè)頭結(jié)點(diǎn)的話，貌似中序和先序的線索化都不再會(huì)有空的鏈域出現(xiàn)吧。

以上觀點(diǎn)若有錯(cuò)誤也請(qǐng)直接指出。

問題：一棵左右子樹均不為空的二叉樹在前序線索化后，其中空的鏈域的個(gè)數(shù)是()
A 0   B 1  C 2  D  不確定

為什么不是A而是B？換而言之這個(gè)頭結(jié)點(diǎn)到底是加了還是沒加呢？這個(gè)空的鏈域指的什么意思？

在此再次多謝~

石俊豪

1018ji 發(fā)表于 2012-7-6 20:53
如果頭結(jié)點(diǎn)左指根結(jié)點(diǎn)右指最后結(jié)點(diǎn)！畫出來答案就是零唄！我用手機(jī)上你可以自己畫畫！我也是半吊子水平 ...

額 只要填上我說的那個(gè)逆天的頭結(jié)點(diǎn)之后 確實(shí)沒有空的了 看來還是要看題 默認(rèn)狀態(tài)貌似是不要那個(gè)頭結(jié)點(diǎn)...呵呵 多謝了

1018ji

石俊豪 發(fā)表于 2012-7-6 17:35
親 多謝你挺我 不過建議你仔細(xì)畫一下我的第一個(gè)問題 因?yàn)槲艺J(rèn)為嚴(yán)格按照標(biāo)號(hào)來畫 G點(diǎn)是沒有父節(jié)點(diǎn)的

關(guān)于 ...

如果頭結(jié)點(diǎn)左指根結(jié)點(diǎn)右指最后結(jié)點(diǎn)！畫出來答案就是零唄！我用手機(jī)上你可以自己畫畫！我也是半吊子水平

1018ji

石俊豪 發(fā)表于 2012-7-6 17:35
親 多謝你挺我 不過建議你仔細(xì)畫一下我的第一個(gè)問題 因?yàn)槲艺J(rèn)為嚴(yán)格按照標(biāo)號(hào)來畫 G點(diǎn)是沒有父節(jié)點(diǎn)的

關(guān)于 ...

第一個(gè)的確是沒有雙親結(jié)點(diǎn)！看樣我是想當(dāng)然了！第二個(gè)問題頭結(jié)點(diǎn)在我看王道書認(rèn)為這個(gè)不是必須的！這個(gè)頭結(jié)點(diǎn)只是使線索二叉樹更強(qiáng)！至于選什么你畫一個(gè)不就知道了！我感覺在沒有指明情況下頭結(jié)點(diǎn)這種東西還是不予考慮

石俊豪

1018ji 發(fā)表于 2012-7-6 16:01
那個(gè)0指的就是沒有東西 數(shù)字是值得為滿二叉樹時(shí)候的層次遍歷編號(hào) 慢慢話不就行了

空鏈域 是沒有孩子的才算 ...

親 多謝你挺我 不過建議你仔細(xì)畫一下我的第一個(gè)問題 因?yàn)槲艺J(rèn)為嚴(yán)格按照標(biāo)號(hào)來畫 G點(diǎn)是沒有父節(jié)點(diǎn)的

關(guān)于第二個(gè)問題 我想你還木有明白我的意思
我看的輔導(dǎo)書上 線索化的時(shí)候 貌似會(huì)在原來的根節(jié)點(diǎn)前加一個(gè)頭結(jié)點(diǎn) 這個(gè)頭結(jié)點(diǎn)的結(jié)構(gòu)是和樹節(jié)點(diǎn)相同的結(jié)構(gòu) 它左域指向根節(jié)點(diǎn) 而右域指向某種遍歷之后的最后一個(gè)節(jié)點(diǎn) 同樣的 某種遍歷的第一個(gè)節(jié)點(diǎn)的前驅(qū)線索會(huì)指向這個(gè)頭結(jié)點(diǎn) 而某種遍歷最后一個(gè)節(jié)點(diǎn)的后繼線索也會(huì)指向這個(gè)根節(jié)點(diǎn)

所以朋友 請(qǐng)問哪里有空的指針域？你不認(rèn)為一切指針域都安排上東西了么？

至于頭結(jié)點(diǎn)是不是必須的 我的輔導(dǎo)書寫著是要頭結(jié)點(diǎn)的 而且你給我的網(wǎng)頁我看了確實(shí)沒有 好吧必須還是不必須暫且不說 那么如果有頭結(jié)點(diǎn)我這個(gè)選什么 0么？

1018ji

http://www.tyut.edu.cn/kecheng1/site01/suanfayanshi/InorderThreadingBitree.asp


{:soso_e101:}

1018ji

那個(gè)0指的就是沒有東西 數(shù)字是值得為滿二叉樹時(shí)候的層次遍歷編號(hào) 慢慢話不就行了

空鏈域 是沒有孩子的才算空把


建立一個(gè)abc的二叉樹 a為根節(jié)點(diǎn) b左孩子 c有孩子 前序abc a沒有空鏈域 b有前有后沒有空鏈域 c只有前剩余一個(gè)空鏈域  答案不就是B了

還有頭結(jié)點(diǎn)跟順序表一樣的白 不是必須的吧{:soso_e132:}

石俊豪

防沉沙發(fā){:soso_e141:}