2021計(jì)算機(jī)考研：如何在線索樹(shù)中找結(jié)點(diǎn)的后繼?

　　對(duì)于打算報(bào)考2021考研計(jì)算機(jī)的考生們來(lái)說(shuō)復(fù)習(xí)是難點(diǎn)，很多本專(zhuān)業(yè)或者跨專(zhuān)業(yè)的學(xué)生在備考考研數(shù)據(jù)結(jié)構(gòu)中經(jīng)常遇到一個(gè)難點(diǎn)問(wèn)題，如何在線索樹(shù)中找結(jié)點(diǎn)的后繼?雖然有些題目設(shè)置的靈活多變，有的時(shí)候甚至可能分析不出來(lái)題目的考點(diǎn)在這里。下面小編整理了詳細(xì)內(nèi)容，供大家參考。

　　如何在線索樹(shù)中找結(jié)點(diǎn)的后繼?

　　(1)中序線索樹(shù)中找結(jié)點(diǎn)的后繼

　?、贅?shù)中所有葉子結(jié)點(diǎn)的右鏈?zhǔn)蔷€索，則右鏈域直接指示了結(jié)點(diǎn)的后繼。

　　②樹(shù)中所有非終端結(jié)點(diǎn)的右鏈均為指針，根據(jù)中序遍歷的規(guī)律，結(jié)點(diǎn)的后繼應(yīng)是遍歷其右子樹(shù)時(shí)訪問(wèn)的第一個(gè)結(jié)點(diǎn)，即右子樹(shù)中最左下的結(jié)點(diǎn)。

　　反之，在中序線索樹(shù)中找結(jié)點(diǎn)前驅(qū)的規(guī)律是：若其左標(biāo)志為“1”，則左鏈為線索，指示其前驅(qū)，否則遍歷左子樹(shù)時(shí)最后訪問(wèn)的一個(gè)結(jié)點(diǎn)(左子樹(shù)中最右下的結(jié)點(diǎn))為其前驅(qū)。

　　(2)后序線索樹(shù)中找結(jié)點(diǎn)后繼

　?、偃艚Y(jié)點(diǎn)x是二叉樹(shù)的根，則其后繼為空

　?、谌艚Y(jié)點(diǎn)x是其雙親的右孩子或是其雙親的左孩子且其雙親沒(méi)有右子樹(shù)，則其后繼即為雙親結(jié)點(diǎn)

　?、廴艚Y(jié)點(diǎn)x是其雙親的左孩子，且其雙親有右子樹(shù)，則其后繼為雙親的右子樹(shù)上按后序遍歷列出的第一個(gè)結(jié)點(diǎn)。

　　可見(jiàn)，在后序線索化樹(shù)上找后繼時(shí)需知道結(jié)點(diǎn)雙親，即需帶標(biāo)志域的三叉鏈表作存儲(chǔ)結(jié)構(gòu)。

　　最后給大家留一個(gè)題目，希望可以幫助各位小伙伴們檢驗(yàn)一下知識(shí)點(diǎn)的掌握情況。

　　二叉樹(shù)在線索化后，仍不能有效求解的問(wèn)題是( )。

　　A.先序線索二叉樹(shù)中求先序后繼

　　B.中序線索二叉樹(shù)中求中序后繼

　　C.中序線索二叉樹(shù)中求中序前驅(qū)

　　D.后序線索二又樹(shù)中求后序后繼

　　小伙伴們，看到這里的時(shí)候相信大家已經(jīng)有了自己的答案，在這里我們對(duì)一下正確選項(xiàng)：D。簡(jiǎn)單分析一下：不是每個(gè)結(jié)點(diǎn)經(jīng)過(guò)線索都可以直接找到它的前驅(qū)和后繼。在先序線索二叉樹(shù)中查找一個(gè)結(jié)點(diǎn)的先序后繼很簡(jiǎn)單，而查找先序前驅(qū)必須知道該結(jié)點(diǎn)的雙親結(jié)點(diǎn)。中序線索二叉樹(shù)中根據(jù)中序遍歷的規(guī)律查找中序前驅(qū)和中序后繼也是很方便的。同樣，在后序線索二叉樹(shù)中查找一個(gè)結(jié)點(diǎn)的后序前驅(qū)也很簡(jiǎn)單，而查找后序后繼也必須知道該結(jié)點(diǎn)的雙親結(jié)點(diǎn)，而二叉鏈表中沒(méi)有存放雙親的指針。

　　最后希望各位小伙伴們?cè)诳佳械穆飞喜粩噙~進(jìn)，繼續(xù)加油，我們下次再見(jiàn)。

　　(注：本文來(lái)自網(wǎng)絡(luò)，如有侵權(quán)，請(qǐng)聯(lián)系刪除)