數(shù)據(jù)結(jié)構(gòu)——二叉樹(c)(參考版)
2025-06-20 06:44本頁面
【正文】 參考文獻(xiàn)： 1. 《數(shù)據(jù)結(jié)構(gòu)理論與實(shí)踐》 楊永斌 楊友斌編著 天津：天津科技技術(shù)出版社2. 《數(shù)據(jù)結(jié)構(gòu)題集》（c語言版） 嚴(yán)蔚敏等 編著 北京：清華大學(xué)出版社3. 數(shù)據(jù)結(jié)構(gòu)二叉樹的運(yùn)用 。并且，在線索化二叉樹上插入刪除操作附加的代價太大。而為了傳輸速度和內(nèi)存移植，大部分的內(nèi)存是要對齊的，這就導(dǎo)致在內(nèi)存中使用線索化二叉樹根本就沒節(jié)省內(nèi)存?！。壕€索化增加了兩個標(biāo)志位，但是這兩個位怎么儲存？即使是在支持位存儲的CPU上，也不能拿位存儲器來存的，第一是因?yàn)榻Y(jié)構(gòu)體成員變量的內(nèi)存地址是在連續(xù)的一起的，第二是位存儲器的存儲數(shù)目是有限的。，但是前驅(qū)需要求雙親；中序線索化前驅(qū)和后繼都不需要求雙親，但是都不很直接；后序線索化能依次找到前驅(qū)，但是后繼需要求雙親。當(dāng)然，這樣的操作很頻繁的時候，做這方面的改善才是有意義的。探討線索化二叉樹是否降低空間效率：第一，二叉樹的葉子節(jié)點(diǎn)還有兩個指針域沒有用，可以節(jié)省內(nèi)存。另外，二叉樹中依中序列表的第一個結(jié)點(diǎn)的LeftChild指針，和最后一個結(jié)點(diǎn)的RightChild指針都指向頭結(jié)點(diǎn)。如果在每個結(jié)點(diǎn)中增加指向其前驅(qū)和后繼結(jié)點(diǎn)的指針，將降低存儲空間的效率。（） 可知這樣造成的存儲空間的浪費(fèi)索化二叉樹，因?yàn)槊總€結(jié)點(diǎn)中只有指向其左、右孩子結(jié)點(diǎn)的指針，所以從任一結(jié)點(diǎn)出發(fā)只能直接找到該結(jié)點(diǎn)的左、右孩子。一個只有k個結(jié)點(diǎn)的右單枝樹卻需要2k1個結(jié)點(diǎn)的存儲空間。 假設(shè)對結(jié)點(diǎn)為i 的二叉樹有如下定義：1. 僅當(dāng)i=1時，結(jié)點(diǎn)i為根結(jié)點(diǎn)；2. 當(dāng)i1時，結(jié)點(diǎn)i的父結(jié)點(diǎn)為[i/2]；3. 結(jié)點(diǎn)i的左孩子結(jié)點(diǎn)為2i；4. 結(jié)點(diǎn)i的右孩子結(jié)點(diǎn)為2i+
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號-1