關于二叉樹的順序存儲

石俊豪 · 發表于 2012-7-2 17:33

本帖最后由石俊豪于 2012-7-2 20:07 編輯

今天復習到二叉樹部分，看完輔導書的講義，說二叉樹的順序存儲就是
“用一組地址連續的存儲單元依次自上而下、自左至右存儲完全二叉樹上的結點元素，即將完全二叉樹上編號為i的結點元素存儲在所定義的一位數組中下標為i-1的分量中。對于一般二叉樹，則應將其每個結點與完全二叉樹上的結點對照，存儲在一位數組的響應分量中。”
OK如果過路的高手覺得上述講義有錯歡迎直接指出多謝。

然后后面有一道習題，
某二叉樹的結點采用順序存儲結構如下圖所示：
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點該劃到哪？在此先多謝了

追加：剛才又遇到一個問題。輔導書上認為“加上線索的二叉樹稱之為線索二叉樹。對二叉樹以某種次序遍歷使其變為線索二叉樹的過程叫做線索化。”

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

以上觀點若有錯誤也請直接指出。

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

為什么不是A而是B？換而言之這個頭結點到底是加了還是沒加呢？這個空的鏈域指的什么意思？

在此再次多謝~

石俊豪 · 發表于 2012-7-2 20:08

防沉沙發{:soso_e141:}

1018ji · 發表于 2012-7-6 16:01

那個0指的就是沒有東西數字是值得為滿二叉樹時候的層次遍歷編號慢慢話不就行了

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

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

還有頭結點跟順序表一樣的白不是必須的吧{:soso_e132:}

1018ji · 發表于 2012-7-6 16:15

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

{:soso_e101:}

石俊豪 · 發表于 2012-7-6 17:35

本帖最后由石俊豪于 2012-7-6 17:40 編輯

1018ji 發表于 2012-7-6 16:01
那個0指的就是沒有東西數字是值得為滿二叉樹時候的層次遍歷編號慢慢話不就行了

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

親多謝你挺我不過建議你仔細畫一下我的第一個問題因為我認為嚴格按照標號來畫 G點是沒有父節點的

關于第二個問題我想你還木有明白我的意思
我看的輔導書上線索化的時候貌似會在原來的根節點前加一個頭結點這個頭結點的結構是和樹節點相同的結構它左域指向根節點而右域指向某種遍歷之后的最后一個節點同樣的某種遍歷的第一個節點的前驅線索會指向這個頭結點而某種遍歷最后一個節點的后繼線索也會指向這個根節點

所以朋友請問哪里有空的指針域？你不認為一切指針域都安排上東西了么？

至于頭結點是不是必須的我的輔導書寫著是要頭結點的而且你給我的網頁我看了確實沒有好吧必須還是不必須暫且不說那么如果有頭結點我這個選什么 0么？

1018ji · 發表于 2012-7-6 20:50

石俊豪發表于 2012-7-6 17:35
親多謝你挺我不過建議你仔細畫一下我的第一個問題因為我認為嚴格按照標號來畫 G點是沒有父節點的

關于 ...

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

1018ji · 發表于 2012-7-6 20:53

石俊豪發表于 2012-7-6 17:35
親多謝你挺我不過建議你仔細畫一下我的第一個問題因為我認為嚴格按照標號來畫 G點是沒有父節點的

關于 ...

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

石俊豪 · 發表于 2012-7-7 13:02

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

額只要填上我說的那個逆天的頭結點之后確實沒有空的了看來還是要看題默認狀態貌似是不要那個頭結點...呵呵多謝了

		自動登錄	找回密碼
密碼			注冊

關于二叉樹的順序存儲

NEW最新資料推薦

RE: 關于二叉樹的順序存儲

RE: 關于二叉樹的順序存儲