二叉樹總結(jié)

遍歷(非遞歸)

  • 先序遍歷算法

  1. 首先申請一個(gè)新的棧户秤,記為stack胎署;
  2. 然后將頭結(jié)點(diǎn)head壓入棧stack中睬关;
  3. 每次從stack中彈出棧頂節(jié)點(diǎn)诱担,記為cur,然后打印cur節(jié)點(diǎn)的值电爹。如果cur右孩子不為空的話蔫仙,將cur的右孩子壓入stack中。最后如果cur的左孩子不為空的話丐箩,將cur的左孩子壓入stack中摇邦。
  4. 不斷重復(fù)步驟3,直到stack為空屎勘,全部過程結(jié)束施籍。

  • 中序遍歷算法

  1. 申請一個(gè)新的棧,記為stack概漱,申請一個(gè)變量cur丑慎,初始時(shí)令cur等于頭結(jié)點(diǎn);
  2. 先把cur節(jié)點(diǎn)壓入棧中瓤摧,對以cur節(jié)點(diǎn)為頭的整顆子樹來說竿裂,依次把整顆樹的左邊界壓入棧中,即不斷令cur==cur.left姻灶,然后重復(fù)步驟2铛绰;
  3. 不斷重復(fù)步驟2,直到發(fā)現(xiàn)cur為空产喉,此時(shí)從stack中彈出一個(gè)節(jié)點(diǎn)捂掰,記為node。打印node的值曾沈,并讓cur==node.right这嚣,然后繼續(xù)重復(fù)步驟2;
  4. 當(dāng)stack為空并且cur為空時(shí)塞俱,整個(gè)過程結(jié)束姐帚。

  • 后序遍歷算法

方法一:使用兩個(gè)棧實(shí)現(xiàn)

  1. 申請一個(gè)棧,記為s1障涯,然后將頭節(jié)點(diǎn)壓入s1中罐旗;
  2. 從s1中彈出的節(jié)點(diǎn)記為cur膳汪,然后先把cur的左孩子壓入s1中,然后把cur1的右孩子壓入s1中九秀;
  3. 在整個(gè)過程中遗嗽,每一個(gè)從s1中彈出的節(jié)點(diǎn)都放進(jìn)第二個(gè)棧s2中;
  4. 不斷重復(fù)步驟2和步驟3鼓蜒,直到s1為空痹换,過程停止。
  5. 從s2中依次彈出節(jié)點(diǎn)并打印都弹,打印的順序就是后續(xù)遍歷的順序了娇豫。

方法二:使用一個(gè)棧實(shí)現(xiàn)

  1. 申請一個(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;
  2. 每次令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氛什。
  3. 一直重復(fù)步驟2莺葫,直到stack為空,過程停止枪眉。
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末捺檬,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子贸铜,更是在濱河造成了極大的恐慌堡纬,老刑警劉巖聂受,帶你破解...
    沈念sama閱讀 222,729評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異烤镐,居然都是意外死亡饺饭,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,226評論 3 399
  • 文/潘曉璐 我一進(jìn)店門职车,熙熙樓的掌柜王于貴愁眉苦臉地迎上來瘫俊,“玉大人,你說我怎么就攤上這事悴灵】秆浚” “怎么了?”我有些...
    開封第一講書人閱讀 169,461評論 0 362
  • 文/不壞的土叔 我叫張陵积瞒,是天一觀的道長川尖。 經(jīng)常有香客問我,道長茫孔,這世上最難降的妖魔是什么叮喳? 我笑而不...
    開封第一講書人閱讀 60,135評論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮缰贝,結(jié)果婚禮上馍悟,老公的妹妹穿的比我還像新娘。我一直安慰自己剩晴,他們只是感情好锣咒,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,130評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著赞弥,像睡著了一般毅整。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上绽左,一...
    開封第一講書人閱讀 52,736評論 1 312
  • 那天悼嫉,我揣著相機(jī)與錄音,去河邊找鬼拼窥。 笑死戏蔑,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的闯团。 我是一名探鬼主播辛臊,決...
    沈念sama閱讀 41,179評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼房交!你這毒婦竟也來了彻舰?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,124評論 0 277
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎刃唤,沒想到半個(gè)月后隔心,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,657評論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡尚胞,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,723評論 3 342
  • 正文 我和宋清朗相戀三年硬霍,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片笼裳。...
    茶點(diǎn)故事閱讀 40,872評論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡唯卖,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出躬柬,到底是詐尸還是另有隱情拜轨,我是刑警寧澤,帶...
    沈念sama閱讀 36,533評論 5 351
  • 正文 年R本政府宣布允青,位于F島的核電站橄碾,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏颠锉。R本人自食惡果不足惜法牲,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,213評論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望琼掠。 院中可真熱鬧拒垃,春花似錦、人聲如沸眉枕。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,700評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽速挑。三九已至,卻和暖如春副硅,著一層夾襖步出監(jiān)牢的瞬間姥宝,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,819評論 1 274
  • 我被黑心中介騙來泰國打工恐疲, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留腊满,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 49,304評論 3 379
  • 正文 我出身青樓培己,卻偏偏與公主長得像碳蛋,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個(gè)殘疾皇子省咨,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,876評論 2 361