穿線二叉樹(shù)

1、穿線樹(shù):也叫線索二叉樹(shù)

在二叉鏈表存儲(chǔ)形式的二叉樹(shù)中，把節(jié)點(diǎn)中空指針利用成為周游線索。原來(lái)為空的左指針指向結(jié)點(diǎn)在某種周游序列下的前驅(qū)，原來(lái)為空的右指針指向結(jié)點(diǎn)在同一種周游序列下的后繼。這樣的二叉樹(shù)稱為穿線樹(shù)。

.. 可以有中序穿線樹(shù)，前序穿線樹(shù)，后序穿線樹(shù)。每種穿線樹(shù)可以只穿一半。穿線樹(shù)的目的是利用空指針的存儲(chǔ)空間，建立周游線索。為了區(qū)分線索和指針，需在每個(gè)結(jié)點(diǎn)中增加兩個(gè)標(biāo)志位，分別標(biāo)識(shí)左右指針域是實(shí)際指針還是線索。

2、中序周游中序穿線樹(shù):先從穿線樹(shù)的根出發(fā)，一直沿左指針，找到"最左"(它一定是中序的第一個(gè)

結(jié)點(diǎn));然后反復(fù)地找結(jié)點(diǎn)的中序后繼。一個(gè)結(jié)點(diǎn)的右指針如果是線索，則右指針就是下一個(gè)要周游的結(jié)點(diǎn)，如果右指針不是線索，則它的中序后繼是其右子樹(shù)的"最左"結(jié)點(diǎn)。

3、穿線樹(shù)節(jié)點(diǎn)的插入:

往中序穿線樹(shù)里插入結(jié)點(diǎn)的算法，規(guī)定插入這樣進(jìn)行:newpointer指向要插入的新結(jié)點(diǎn)，pointer指向穿線二叉樹(shù)里的一個(gè)結(jié)點(diǎn)。將新結(jié)點(diǎn)插進(jìn)來(lái)作為pointer指向的結(jié)點(diǎn)的右子樹(shù)的根。pointer指向的結(jié)點(diǎn)的原來(lái)的右子樹(shù)現(xiàn)在作為新結(jié)點(diǎn)的右子樹(shù)(新結(jié)點(diǎn)的左子樹(shù)為空)。即在中序序列里，新結(jié)點(diǎn)剛好插到p所指向的結(jié)點(diǎn)的后面。pointer的新后繼結(jié)點(diǎn)是newpointer，newpointer的后繼是pointer->rightchild()。如果Pointer的右子樹(shù)不空，則右子樹(shù)的最左結(jié)點(diǎn)線索指向newpointer;若空，則pointer的右線索給newpointer繼承。