當前位置:成語大全網 - 書法字典 - 遍歷序列和字典解釋

遍歷序列和字典解釋

前置遍歷是先遍歷根節點,然後是左邊的節點,最後是右邊的節點;

中間順序遍歷是先遍歷左側節點,然後是中間根節點,最後是右側節點;

後序遍歷是先遍歷左邊的節點,然後是右邊的節點,最後是中間的根節點。

二叉樹的這三種遍歷方法是按照每個子樹的根節點順序進行遍歷的。

擴展數據:

例:已知二叉樹的後序遍歷序列為dabec,中序遍歷序列為debac,其前序遍歷序列為(cedba)。

(1)中間順序遍歷:debac

後序遍歷:dabec

後序遍歷序列的最後壹個節點是根節點,所以我們知道C是根節點。

有序遍歷序列的根節點位於中間,左子樹和右子樹位於其左側。因此,從順序遍歷序列可以看出,根節點C只有左子樹,沒有右子樹。

(2)中階遍歷:巴德

後序遍歷:dabe

後序遍歷序列的最後壹個節點是根節點,所以我們知道E是c的左子樹的根節點。

有序遍歷序列的根節點位於中間,左子樹和右子樹位於其左側。因此,從順序遍歷序列可以看出,根節點E的左子節點是D,右子樹是ba。

(3)中序遍歷:ba

後序遍歷

從後序遍歷序列可以知道B是e的右子樹的根節點。從中間序列遍歷序列可以看出A是根節點B的右子節點。