對(duì)稱(chēng)序周游序列是什么？

在一顆二叉樹(shù)中，要將它按對(duì)稱(chēng)序線索化，其做法是按對(duì)稱(chēng)序周游此二叉樹(shù)，在周游的過(guò)程中用線索代替空指針。

周游采用非遞歸的方法對(duì)二叉樹(shù)按順序周游，所以設(shè)置一個(gè)棧結(jié)構(gòu)，保存周游過(guò)程中需要回溯的指針。

算法中的指針，p指向正在訪問(wèn)的結(jié)點(diǎn)，pr是指向它的對(duì)稱(chēng)序的前驅(qū)，即上一次剛訪問(wèn)過(guò)的結(jié)點(diǎn)。

要周游對(duì)稱(chēng)序二叉樹(shù)，首先找到對(duì)稱(chēng)序列中的第一個(gè)結(jié)點(diǎn)，然后依次找到結(jié)點(diǎn)的后繼結(jié)點(diǎn)，直到其后繼結(jié)點(diǎn)為空即可。

要找第一個(gè)結(jié)點(diǎn)，只要從根節(jié)點(diǎn)出發(fā)，沿著左指針不斷往下走，直至左指針為空，到達(dá)最左下結(jié)點(diǎn)，這就是第一個(gè)結(jié)點(diǎn)。

找任意結(jié)點(diǎn)的對(duì)稱(chēng)序后繼結(jié)點(diǎn)。一個(gè)結(jié)點(diǎn)的右指針如果是線索，它就指向該結(jié)點(diǎn)在對(duì)稱(chēng)序下的后繼。如果不是線索，則它指向該結(jié)點(diǎn)右子樹(shù)的根，而該結(jié)點(diǎn)在對(duì)稱(chēng)序下的后繼應(yīng)是此右子樹(shù)的最左下結(jié)點(diǎn)。