中間順序遍歷是先遍歷左側節點,然後是中間根節點,最後是右側節點;
後序遍歷是先遍歷左邊的節點,然後是右邊的節點,最後是中間的根節點。
二叉樹的這三種遍歷方法是按照每個子樹的根節點順序進行遍歷的。
擴展數據:
例:已知二叉樹的後序遍歷序列為dabec,中序遍歷序列為debac,其前序遍歷序列為(cedba)。
(1)中間順序遍歷:debac
後序遍歷:dabec
後序遍歷序列的最後壹個節點是根節點,所以我們知道C是根節點。
有序遍歷序列的根節點位於中間,左子樹和右子樹位於其左側。因此,從順序遍歷序列可以看出,根節點C只有左子樹,沒有右子樹。
(2)中階遍歷:巴德
後序遍歷:dabe
後序遍歷序列的最後壹個節點是根節點,所以我們知道E是c的左子樹的根節點。
有序遍歷序列的根節點位於中間,左子樹和右子樹位於其左側。因此,從順序遍歷序列可以看出,根節點E的左子節點是D,右子樹是ba。
(3)中序遍歷:ba
後序遍歷
從後序遍歷序列可以知道B是e的右子樹的根節點。從中間序列遍歷序列可以看出A是根節點B的右子節點。