線索二叉樹的插入有幾種情況？在線程二叉樹中插入新節(jié)點(diǎn)時，必須在插入位置修改原有的前導(dǎo)和后繼線索，這樣既能保留原有的線程關(guān)系，又能在插入新節(jié)點(diǎn)后正確維護(hù)原有的線程關(guān)系。以中階線程二叉樹為例，如果將新節(jié)點(diǎn)

線索二叉樹的插入有幾種情況？

在線程二叉樹中插入新節(jié)點(diǎn)時，必須在插入位置修改原有的前導(dǎo)和后繼線索，這樣既能保留原有的線程關(guān)系，又能在插入新節(jié)點(diǎn)后正確維護(hù)原有的線程關(guān)系。以中階線程二叉樹為例，如果將新節(jié)點(diǎn)R作為節(jié)點(diǎn)s的右子節(jié)點(diǎn)插入，則應(yīng)根據(jù)s的右子字段是線索還是右子指針來確定不同的處理方法。同樣，如果將新節(jié)點(diǎn)R作為節(jié)點(diǎn)s的左子節(jié)點(diǎn)插入，還應(yīng)考慮s的leftchild字段是線索還是左子指針，以確定不同的處理方法。

在不同的線索化二叉樹中，空余指針個數(shù)分別是多少？

通過以某種方式遍歷二叉樹，可以將二叉樹中的所有節(jié)點(diǎn)排序?yàn)橐粋€線性序列。在該序列中，除第一個節(jié)點(diǎn)外，每個節(jié)點(diǎn)具有且僅具有一個直接前導(dǎo)節(jié)點(diǎn)；除最后一個節(jié)點(diǎn)外，每個節(jié)點(diǎn)具有且僅具有一個直接后繼節(jié)點(diǎn)。這些指向直接前驅(qū)節(jié)點(diǎn)和直接后續(xù)節(jié)點(diǎn)的指針稱為線程，線程二叉樹稱為線程二叉樹。按一定順序遍歷二叉樹的實(shí)質(zhì)是按該順序遍歷二叉樹，在遍歷過程中用線程代替空指針。綜上所述，如果第一個節(jié)點(diǎn)沒有前導(dǎo)節(jié)點(diǎn)，則其左指針為空；如果最后一個節(jié)點(diǎn)沒有后繼節(jié)點(diǎn)，則其右指針為空。因此，在不同的線程二叉樹中，自由指針的數(shù)目應(yīng)該是兩個。

怎樣先序線索化二叉樹？

我了解的方法：首先，要標(biāo)記的二叉樹：都設(shè)置兩個標(biāo)記LTAG，rtag，如果左子指針為空，LTAG=1，如果右子指針為空，rtag=1。按順序遍歷線程二叉樹：首先按順序遍歷線程二叉樹，然后將得到的節(jié)點(diǎn)按順序加入隊(duì)列。然后，根據(jù)標(biāo)簽，隊(duì)列中的第一個節(jié)點(diǎn)是LTAG=0。如果LTAG=1，則左指針指向團(tuán)隊(duì)中的前一個元素。如果rtag=1，則右指針指向團(tuán)隊(duì)中的下一個元素。中階遍歷線程二叉樹：首先進(jìn)行中階遍歷，然后依次對得到的節(jié)點(diǎn)進(jìn)行排隊(duì)，然后依次對隊(duì)列中除根節(jié)點(diǎn)以外的節(jié)點(diǎn)進(jìn)行排隊(duì)。根據(jù)標(biāo)記，隊(duì)列中的第一個節(jié)點(diǎn)LTAG=0，如果LTAG=1，左指針指向團(tuán)隊(duì)中的前一個元素，如果rtag=1，右指針指向團(tuán)隊(duì)中的下一個元素。按后序遍歷線程二叉樹：先按后序遍歷，然后依次對得到的節(jié)點(diǎn)進(jìn)行排隊(duì)。然后，依次標(biāo)記隊(duì)列中除根節(jié)點(diǎn)以外的節(jié)點(diǎn)。隊(duì)列中的第一個節(jié)點(diǎn)是LTAG=0。如果LTAG=1，則左指針指向隊(duì)列中的前一個元素。如果rtag=1，

中序線索化二叉樹程序？

首先我自己理解了這個方法，標(biāo)記二叉樹：設(shè)置兩個標(biāo)簽，LTAG和rtag。如果左子指針為空，則LTAG=1；如果右子指針為空，則rtag=1。按順序遍歷線程二叉樹：首先按順序遍歷線程二叉樹，然后將得到的節(jié)點(diǎn)按順序加入隊(duì)列。然后，根據(jù)標(biāo)簽，隊(duì)列中的第一個節(jié)點(diǎn)是LTAG=0。如果LTAG=1，則左指針指向團(tuán)隊(duì)中的前一個元素。如果rtag=1，則右指針指向團(tuán)隊(duì)中的下一個元素。中階遍歷線程二叉樹：首先進(jìn)行中階遍歷，然后依次對得到的節(jié)點(diǎn)進(jìn)行排隊(duì)，然后依次對隊(duì)列中除根節(jié)點(diǎn)以外的節(jié)點(diǎn)進(jìn)行排隊(duì)。根據(jù)標(biāo)記，隊(duì)列中的第一個節(jié)點(diǎn)LTAG=0，如果LTAG=1，左指針指向團(tuán)隊(duì)中的前一個元素，如果rtag=1，右指針指向團(tuán)隊(duì)中的下一個元素。以后序方式遍歷線程二叉樹：首先遍歷后序方式，然后依次對隊(duì)列中除根節(jié)點(diǎn)外的節(jié)點(diǎn)進(jìn)行排隊(duì)。根據(jù)標(biāo)記，隊(duì)列中的第一個節(jié)點(diǎn)是LTAG=0。如果LTAG=1，則左指針指向隊(duì)列中的前一個元素。如果rtag=1，則左指針指向隊(duì)列中的前一個元素，