當前位置:編程學習大全網 - 編程語言 - 設壹顆二叉樹的中序遍歷結果是DBEAFC,前序遍歷結果是ABDECF,則後序便利結果是什麽?

設壹顆二叉樹的中序遍歷結果是DBEAFC,前序遍歷結果是ABDECF,則後序便利結果是什麽?

後序遍歷結果是DEBFCA。

前序遍歷得知A是根節點,在中序遍歷中,A講節點非分根節點A左右子樹:即

A

DBE ?FC

下面看DBE序列,在前序遍歷中,這三個的先後順序是BDE,所以這三個節點中B是根節點,根據中序遍歷結果,該三個節點順序是DBE,所以B講著三個節點劃分為左右節點:結果如下:

A

B ?FC

D E

下面再看FC兩個節點,他們在前序遍歷結果中的結果是CF,所以C是這兩個節點中的根節點,再根據他們在中序遍歷結果中的順序FC,則F將他們本身劃分為左子樹(此時為空)和右子樹C,則二叉樹示意圖如下:

A

B C

D E 空 ? F

擴展資料:

樹的3種最重要的遍歷方式分別稱為前序遍歷、中序遍歷和後序遍歷。以這3種方式遍歷壹棵樹時,若按訪問結點的先後次序將結點排列起來,就可分別得到樹中所有結點的前序列表、中序列表和後序列表。相應的結點次序分別稱為結點的前序、中序和後序。

如果T是壹棵空樹,那麽對T進行前序遍歷、中序遍歷和後序遍歷都是空操作,得到的列表為空表。

如果T是壹棵單結點樹,那麽對T進行前序遍歷、中序遍歷和後序遍歷根,樹根的子樹從左到右依次為T1,T2,..,Tk,那麽有:

對T進行前序遍歷是先訪問樹根n,然後依次前序遍歷T1,T2,..,Tk。

對T進行中序遍歷是先中序遍歷T1,然後訪問樹根n,接著依次對T2,T2,..,Tk進行中序遍歷。

對T進行後序遍歷是先依次對T1,T2,..,Tk進行後序遍歷,最後訪問樹根n。

百度百科-遍歷

  • 上一篇:沈從文 <邊城>中翠翠的結局
  • 下一篇:RFID在物流中有什麽應用?
  • copyright 2024編程學習大全網