遍歷(非遞歸)
-
先序遍歷算法
- 首先申請一個(gè)新的棧户秤,記為stack胎署;
- 然后將頭結(jié)點(diǎn)head壓入棧stack中睬关;
- 每次從stack中彈出棧頂節(jié)點(diǎn)诱担,記為cur,然后打印cur節(jié)點(diǎn)的值电爹。如果cur右孩子不為空的話蔫仙,將cur的右孩子壓入stack中。最后如果cur的左孩子不為空的話丐箩,將cur的左孩子壓入stack中摇邦。
- 不斷重復(fù)步驟3,直到stack為空屎勘,全部過程結(jié)束施籍。
-
中序遍歷算法
- 申請一個(gè)新的棧,記為stack概漱,申請一個(gè)變量cur丑慎,初始時(shí)令cur等于頭結(jié)點(diǎn);
- 先把cur節(jié)點(diǎn)壓入棧中瓤摧,對以cur節(jié)點(diǎn)為頭的整顆子樹來說竿裂,依次把整顆樹的左邊界壓入棧中,即不斷令cur==cur.left姻灶,然后重復(fù)步驟2铛绰;
- 不斷重復(fù)步驟2,直到發(fā)現(xiàn)cur為空产喉,此時(shí)從stack中彈出一個(gè)節(jié)點(diǎn)捂掰,記為node。打印node的值曾沈,并讓cur==node.right这嚣,然后繼續(xù)重復(fù)步驟2;
- 當(dāng)stack為空并且cur為空時(shí)塞俱,整個(gè)過程結(jié)束姐帚。
-
后序遍歷算法
方法一:使用兩個(gè)棧實(shí)現(xiàn)
- 申請一個(gè)棧,記為s1障涯,然后將頭節(jié)點(diǎn)壓入s1中罐旗;
- 從s1中彈出的節(jié)點(diǎn)記為cur膳汪,然后先把cur的左孩子壓入s1中,然后把cur1的右孩子壓入s1中九秀;
- 在整個(gè)過程中遗嗽,每一個(gè)從s1中彈出的節(jié)點(diǎn)都放進(jìn)第二個(gè)棧s2中;
- 不斷重復(fù)步驟2和步驟3鼓蜒,直到s1為空痹换,過程停止。
- 從s2中依次彈出節(jié)點(diǎn)并打印都弹,打印的順序就是后續(xù)遍歷的順序了娇豫。
方法二:使用一個(gè)棧實(shí)現(xiàn)
- 申請一個(gè)棧,記為stack畅厢,將頭節(jié)點(diǎn)壓入stack冯痢,同時(shí)設(shè)置兩個(gè)變量h和c。在整個(gè)流程中或详,h代表最近一次彈出并打印的節(jié)點(diǎn)系羞,c代表當(dāng)前stack的棧頂節(jié)點(diǎn)郭计,初始時(shí)令h為頭節(jié)點(diǎn)霸琴,c為NULL;
- 每次令c等于當(dāng)前stack的棧頂節(jié)點(diǎn)昭伸,但是不從stack中彈出節(jié)點(diǎn)梧乘,此時(shí)分以下三種情況:
(1)如果c的左孩子不為空,并且h不等于c的左孩子庐杨,也不等于c的右孩子选调,則把c的左孩子壓入stack中;
(2)如果情況1不成立灵份,并且c的右孩子不為空仁堪,并且h不等于c的右孩子,則把c的右孩子壓入stack中填渠;
(3)如果情況1和情況2都不成立弦聂,那么從stack中彈出c并打印,然后令h等于c氛什。 - 一直重復(fù)步驟2莺葫,直到stack為空,過程停止枪眉。