大家好，今天來(lái)為大家分享二叉樹(shù)遍歷的實(shí)質(zhì)的一些知識(shí)點(diǎn)，和樹(shù)的遍歷和二叉樹(shù)的遍歷區(qū)別的問(wèn)題解析，大家要是都明白，那么可以忽略，如果不太清楚的話(huà)可以看看本篇文章，相信很大概率可以解決您的問(wèn)題，接下來(lái)我們就一起來(lái)看看吧！

為什么樹(shù)的后根遍歷就是對(duì)應(yīng)二叉樹(shù)的中序遍歷

一棵樹(shù)的后根遍歷與這棵樹(shù)所對(duì)應(yīng)的二叉樹(shù)的中序遍歷相同。

當(dāng)對(duì)一棵數(shù)學(xué)表達(dá)式樹(shù)進(jìn)行中序，前序和后序遍歷時(shí)，就分別得到表達(dá)式的中綴、前綴和后綴形式。中綴（infix）形式即平時(shí)所書(shū)寫(xiě)的數(shù)學(xué)表達(dá)式形式，在這種形式中，每個(gè)二元操作符（也就是有兩個(gè)操作數(shù)的操作符）出現(xiàn)在左操作數(shù)之后，右操作數(shù)之前。

一棵二叉樹(shù)的前序遍歷結(jié)果是ABCEDF，中序遍歷結(jié)果是CBAEDF，則其后序遍歷的結(jié)果是

二叉樹(shù)是：A/\BE/\CD\F所以后序遍歷是：CBFDEA

二叉樹(shù)三種遍歷順序的特點(diǎn)

二叉樹(shù)的遍歷分為以下三種：

先序遍歷：遍歷順序規(guī)則為【根左右】

中序遍歷：遍歷順序規(guī)則為【左根右】

后序遍歷：遍歷順序規(guī)則為【左右根】

某二叉樹(shù)的后序遍歷序列與中序遍歷序列相同

后序遍歷說(shuō)明E是根節(jié)點(diǎn)，可見(jiàn)在中序中E的左邊是左子樹(shù)，右邊是右子樹(shù)，可知左子樹(shù)只有一個(gè)D節(jié)點(diǎn)，再看后序遍歷中ACB序列說(shuō)明B是右子樹(shù)的根節(jié)點(diǎn)，在中序中找到B，發(fā)現(xiàn)B沒(méi)有左子樹(shù)，就是說(shuō)AC都在B的右子樹(shù)上，又知道后序遍歷中順序是AC說(shuō)明A是C的子節(jié)點(diǎn)，而中序順序是AC說(shuō)明A在C的左子樹(shù)上，前序：EDBCA

二叉樹(shù)遍歷例題

假設(shè)某二叉樹(shù)的先序遍歷序列是abdgcefh，中序遍歷序列是dgbaechf，畫(huà)出二叉樹(shù)，并給出其后序遍歷序列。分析過(guò)程：

以下面的例題為例進(jìn)行講解：

已知一棵二叉樹(shù)的先序遍歷序列和中序遍歷序列分別是abdgcefh、dgbaechf，求二叉樹(shù)及后序遍歷序列。

分析：先序遍歷序列的第一個(gè)字符為根結(jié)點(diǎn)。對(duì)于中序遍歷，根結(jié)點(diǎn)在中序遍歷序列的中間，左邊部分是根結(jié)點(diǎn)的左子樹(shù)的中序遍歷序列，右邊部分是根結(jié)點(diǎn)的右子樹(shù)的中序遍歷序列。先序：abdgcefh-->abdgcefh

中序：dgbaechf-->dgbaechf

得出結(jié)論：a是樹(shù)根，a有左子樹(shù)和右子樹(shù)，左子樹(shù)有bdg結(jié)點(diǎn)，右子樹(shù)有cefh結(jié)點(diǎn)。先序：bdg-->bdg

中序：dgb-->dgb

得出結(jié)論：b是左子樹(shù)的根結(jié)點(diǎn)，b無(wú)右子樹(shù)，有左子樹(shù)。先序：dg-->dg

中序：dg-->dg

得出結(jié)論：d是b的左子樹(shù)的根結(jié)點(diǎn)，d無(wú)左子樹(shù)，有右子樹(shù)。先序：cefh-->cefh

中序：echf-->echf

得出結(jié)論：c是右子樹(shù)的根結(jié)點(diǎn)，c有左子樹(shù)(只有e結(jié)點(diǎn))，有右子樹(shù)(有fh結(jié)點(diǎn))。先序：fh-->fh

中序：hf-->hf

得出結(jié)論：f是c的左子樹(shù)的根結(jié)點(diǎn)，f有左子樹(shù)(只有h結(jié)點(diǎn))，無(wú)右子樹(shù)。還原二叉樹(shù)為：

a

bc

def

gh后序遍歷序列：gdbehfca

前序遍歷是什么

這個(gè)是二叉樹(shù)里面的一種遍歷情況，前序遍歷也叫做先根遍歷，可記做根左右。

前序遍歷首先訪(fǎng)問(wèn)根結(jié)點(diǎn)然后遍歷左子樹(shù)，最后遍歷右子樹(shù)。在遍歷左、右子樹(shù)時(shí)，仍然先訪(fǎng)問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹(shù)，最后遍歷右子樹(shù)。

二叉樹(shù)中序遍歷的結(jié)果

根據(jù)已知的中序和后序，可以確定根結(jié)點(diǎn)A和左子樹(shù)：BDCE右子樹(shù)：FHG然后再確定左子樹(shù)的中序BDCE和后序DECB確定左子樹(shù)的根結(jié)點(diǎn)為B，右子樹(shù)的中序FHG后序HGF確定右子樹(shù)根結(jié)點(diǎn)為F，再確定左子樹(shù)的左子樹(shù)及右子樹(shù)的右子樹(shù)這樣遞歸下去直到所有的結(jié)點(diǎn)！

關(guān)于本次二叉樹(shù)遍歷的實(shí)質(zhì)和樹(shù)的遍歷和二叉樹(shù)的遍歷區(qū)別的問(wèn)題分享到這里就結(jié)束了，如果解決了您的問(wèn)題，我們非常高興。