數(shù)據(jù)結(jié)構(gòu)——二叉樹(c)-資料下載頁
2025-06-17 06:44本頁面
【正文】 另外，二叉樹中依中序列表的第一個結(jié)點的LeftChild指針，和最后一個結(jié)點的RightChild指針都指向頭結(jié)點。這就像為二叉樹建立了一個雙向線索鏈表，既可從第一個結(jié)點起，順著后繼進行遍歷，也可從最后一個結(jié)點起順著前驅(qū)進行遍歷。探討線索化二叉樹是否降低空間效率：第一，二叉樹的葉子節(jié)點還有兩個指針域沒有用，可以節(jié)省內(nèi)存。第二，我們想用比較少的時間，尋找二叉樹某一個遍歷線性序列的前驅(qū)或者后繼。當(dāng)然，這樣的操作很頻繁的時候，做這方面的改善才是有意義的。：求遍歷后的線性序列的前驅(qū)和后繼。，但是前驅(qū)需要求雙親；中序線索化前驅(qū)和后繼都不需要求雙親，但是都不很直接；后序線索化能依次找到前驅(qū)，但是后繼需要求雙親。可以看出，線索化成中序是最佳的選擇，基本上算是達到了要求?！。壕€索化增加了兩個標(biāo)志位，但是這兩個位怎么儲存？即使是在支持位存儲的CPU上，也不能拿位存儲器來存的，第一是因為結(jié)構(gòu)體成員變量的內(nèi)存地址是在連續(xù)的一起的，第二是位存儲器的存儲數(shù)目是有限的。目前的計算機最少需要1個字節(jié)來儲存這兩個標(biāo)志位。而為了傳輸速度和內(nèi)存移植，大部分的內(nèi)存是要對齊的，這就導(dǎo)致在內(nèi)存中使用線索化二叉樹根本就沒節(jié)省內(nèi)存。假設(shè)把個內(nèi)存空間用來儲存雙親指針時，帶來的方便絕對不是線索化所能比擬的，前面已經(jīng)給出了無棧的非遞歸遍歷。并且，在線索化二叉樹上插入刪除操作附加的代價太大。 結(jié)論：線索化線索化二叉樹在現(xiàn)在的計算機上是毫無用處的。參考文獻： 1. 《數(shù)據(jù)結(jié)構(gòu)理論與實踐》 楊永斌 楊友斌編著 天津：天津科技技術(shù)出版社2. 《數(shù)據(jù)結(jié)構(gòu)題集》（c語言版） 嚴(yán)蔚敏等 編著 北京：清華大學(xué)出版社3. 數(shù)據(jù)結(jié)構(gòu)二叉樹的運用
畢業(yè)設(shè)計相關(guān)推薦
鄂ICP備17016276號-1