其實(shí)二叉樹的中序遍歷算法的問題并不復(fù)雜，但是又很多的朋友都不太了解中序遍歷的時(shí)間復(fù)雜度，因此呢，今天小編就來(lái)為大家分享二叉樹的中序遍歷算法的一些知識(shí)，希望可以幫助到大家，下面我們一起來(lái)看看這個(gè)問題的分析吧！

中序遍歷結(jié)果為abc的二叉樹有幾種

總共有3種。分別為左a中b右c

一棵二叉樹的中序遍歷序列為：DGBAECHF，后序遍歷序列為：GDBEHFCA，則前序列遍歷序列是

不知道你理解前，中，后序遍歷的概念沒？

前序遍歷又叫先根遍歷，就是先訪問根再訪問左子樹再訪問右子樹。

中序就是先訪問左子樹再訪問根再是右子樹。

后根就是先訪問左子樹然后是右子樹最后是根。

簡(jiǎn)單的講就是，你看后序遍歷序列為：GDBEHFCA，最后一個(gè)是A，說(shuō)明A是根。然后再去看中序遍歷序列為：DGBAECHF，看到A在中間，把DGBAECHF分成DGB和ECHF兩部分，好，現(xiàn)在單獨(dú)看這兩個(gè)子樹，左子樹DGB和右子樹ECHF。

同樣后序遍歷序列GDBEHFCA中，找到DGB這三個(gè)字母，發(fā)現(xiàn)它是這樣排列的，GDB，因?yàn)樗呛蟾闅v，所以子樹DGB的根是B，這時(shí)候，你通過(guò)觀察中序的DGB和后序的GDB，發(fā)現(xiàn)中序的右邊沒有東西，所以得出：子樹GDB沒有右支。同樣的道理，發(fā)現(xiàn)子樹ECHF的根是C，左子樹只有E，右子樹是HF。

像這樣一步步分析

那么結(jié)論就是前序遍歷是ABDGCEFH。

你最好能畫個(gè)圖就好理解多了。

圖給你畫了，有點(diǎn)丑，湊合看吧，呵呵。

二叉樹進(jìn)行中序遍歷需使用哪一種數(shù)據(jù)結(jié)構(gòu)

輔助的就是隊(duì)列了，如果是堆棧就成了深度優(yōu)先算法了；其實(shí)這里輔助結(jié)構(gòu)決定了算法的性質(zhì)，你可以換成最大堆，最小堆等，就可以達(dá)到很多不同的效果

同時(shí)知道該二叉樹的中序遍歷序列為CEIFGBADH，求前序遍歷

前序遍歷，先根，再左，再右；中序遍歷，先左，再根，再右。

前序遍歷序列的第一個(gè)節(jié)點(diǎn)是根節(jié)點(diǎn)，記做A，中序遍歷中，A之前的是根節(jié)點(diǎn)的左子樹，A之后的是根節(jié)點(diǎn)的右子樹。

找出左右子樹在前序和中序中的子序列，遞歸下去即可唯一重構(gòu)二叉樹結(jié)構(gòu)，也就確定了后續(xù)遍歷的順序。

參考

ConstructTreefromgivenInorderandPreordertraversals-GeeksforGeeks

二叉樹的先序遍歷為: F B A C D E G H , 中序遍歷為: A B D C E F G H ,該二叉樹

二叉樹為：F/\BG/\\ACH/\DE

已知二叉樹的中序遍歷結(jié)果為DBHEAFICG，后序遍歷結(jié)果為DHEBIFGCA，試畫出該二叉樹，并求其前序遍列序列

--------------------A

---------------B----------C

----------D---------E--F--------G

------------------H-------I

前序?yàn)锳BDEHCFIG

關(guān)于二叉樹的中序遍歷算法和中序遍歷的時(shí)間復(fù)雜度的介紹到此就結(jié)束了，不知道你從中找到你需要的信息了嗎 ？如果你還想了解更多這方面的信息，記得收藏關(guān)注本站。