遍歷(非遞歸)
-
先序遍歷算法
- 首先申請一個(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為空，過程停止枪眉。
