這里還是用到棧的思想，為了方便用了c++的一些內(nèi)容，把出棧，進(jìn)棧，讀棧頂元素用一個(gè)個(gè)函數(shù)封裝起來了，前面做了一些處理來使用這些函數(shù)。

前序非遞歸

思想：一直走左邊，依次進(jìn)棧。等左邊為空的時(shí)候，返回，也就是讀棧頂元素，讀一個(gè)出一個(gè)，并讓cur指向它的右邊，把它的右邊的結(jié)點(diǎn)當(dāng)作根結(jié)點(diǎn)，再走一邊上面的過程。

中序非遞歸

前序是在訪問根結(jié)點(diǎn)時(shí)打印，中序是先訪問左結(jié)點(diǎn)，所以在指向左結(jié)點(diǎn)時(shí)打印，也就是一直往左走依次入棧，走到頭返回讀棧頂元素并出棧時(shí)打印就行，然后cur等于當(dāng)前棧頂元素的右子樹，再把這個(gè)結(jié)點(diǎn)當(dāng)根結(jié)點(diǎn)，再走一邊這樣的過程。

后序非遞歸

比較難想，要有一個(gè)指針last指向上一次操作完整遍歷完的樹的結(jié)點(diǎn)也就是這個(gè)結(jié)點(diǎn)是當(dāng)前最底下的那個(gè)結(jié)點(diǎn)。
一直往左并入棧，走到頭把top指上去，如果top的右邊為空，打印并出棧，否則看右邊是不是last如果是也打印出棧，
否則沒有跑到右邊最后一個(gè)，（如果跑到了，肯定是打印出棧，最后一個(gè)就變了）。cur就等于當(dāng)前棧頂元素的右子樹。

總結(jié)

以上是生活随笔為你收集整理的非递归实现二叉树（前序，中序，后序）c/c++实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。