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

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

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

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

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

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

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

二叉樹的遍歷分為以下三種：

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

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

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

某二叉樹的后序遍歷序列與中序遍歷序列相同

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

二叉樹遍歷例題

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

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

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

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

中序：dgbaechf-->dgbaechf

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

中序：dgb-->dgb

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

中序：dg-->dg

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

中序：echf-->echf

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

中序：hf-->hf

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

a

bc

def

gh后序遍歷序列：gdbehfca

前序遍歷是什么

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

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

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

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

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