C++數據結構學習:二叉樹(2)

2019-11-17 05:04:14

字體：大中小

來源：轉載

供稿：網友

　　線索化二叉樹

　　這是數據結構課程里第一個碰到的難點，不知道你是不是這樣看，反正我當初是費了不少腦細胞——當然，惱人的矩陣壓縮和相關的加法乘法運算不在考慮之列。

我費了不少腦細胞是因為思考：他們干什么呢？很欣喜的看到在這本黃皮書上，這章被打了*號，雖然我不確定作者是不是跟我一個想法——線索化二叉樹在現在的PC上是毫無用處的！——不知我做了這個結論是不是會被人罵死，^_^。

　　為了證實這個結論，我們來看看線索化二叉樹提出的緣由：第一，我們想用比較少的時間，尋找二叉樹某一個遍歷線性序列的前驅或者后繼。當然，這樣的操作很頻繁的時候，做這方面的改善才是有意義的。第二，二叉樹的葉子節點還有兩個指針域沒有用，可以節省內存。說真的，提出線索化二叉樹這樣的構思真的很精巧，完全做到了“廢物利用”——這個人真應該投身環保事業。但在計算機這個死板的東西身上，人們的精巧構思往往都是不能實現的——為了速度，計算機的各個部件都是整潔劃一的，而構思的精巧往往都是建立在組成的復雜上的。

　　我們來看看線索化二叉樹究竟能不能達到上面的兩個目標。

　　求遍歷后的線性序列的前驅和后繼。前序線索化能依次找到后繼，但是前驅需要求雙親；中序線索化前驅和后繼都不需要求雙親，但是都不很直接；后序線索化能依次找到前驅，但是后繼需要求雙親。可以看出，線索化成中序是最佳的選擇，基本上算是達到了要求。

　　節省內存。添加了兩個標志位，問題是這兩個位怎么儲存？即使是在支持位存儲的CPU上，也是不能拿位存儲器來存的，第一是因為結構體成員的地址是在一起的，第二是位存儲器的數目是有限的。因此，最少需要1個字節來儲存這兩個標志位。而為了速度和移植，一般來說，內存是要對齊的，實際上根本就沒節省內存！然而，當這個空間用來儲存雙親指針時，帶來的方便絕對不是線索化所能比擬的，前面已經給出了無棧的非遞歸遍歷。并且，在線索化二叉樹上插入刪除操作附加的代價太大。

　　綜上，線索化最好是中序線索化（前序后序線索化后還得用棧，何必要線索化呢），附加的標志域空間至少1個字節，在32位的CPU會要求對齊到4字節，還不如存儲一個雙親指針，同樣能達到中序線索化的目的，并且能帶來其他的好處。所以，線索化二叉樹在現在的PC上是毫無用處的！

更多內容請看C/C++技術專題數據結構數據結構教程專題，或　　由于對其他體系不太了解，以下觀點姑妄聽之。在內存空間非常充裕的現在，一個節點省2～3個字節實在是沒什么意思（實際上由于對齊還省不出來）；而在內存非常寶貴的地方（比如單片機），會盡量避免使用樹結構——利用其他的方法。所以，現在看來，線索化二叉樹真的是毫無用處了。