先根遍歷

標籤: 暫無標籤

7

更新時間: 2013-09-04

廣告

後序遍歷是二叉樹遍歷的一種。後序遍歷指在訪問根結點、遍歷左子樹與遍歷右子樹三者中,首先遍歷左子樹,然後遍歷右子樹,最後遍歷訪問根結點,在遍歷左、右子樹時,仍然先遍歷左子樹,然後遍歷右子樹,最後遍歷根結點。後序遍歷有遞歸演算法和非遞歸演算法兩種。

  假如以L、D、R分別表示遍歷左子樹、訪問根結點和遍歷右子樹,則可以有DLR,LDR,LRD,DRL,RDL,RLD這6中遍歷二叉樹的方案,若限定先左後右則只有前三種。先根遍歷
先根遍歷

即DLR,也稱先序遍歷。

  首先訪問根結點然後遍歷左子樹,最後遍歷右子樹。在遍歷左、右子樹時,仍然先訪問根結點,然後遍歷左子樹,最後遍歷右子樹。

  先根遍歷二叉樹的操作定義為:

  若二叉樹為空則結束返回,否則:

  (1)訪問根結點

  (2)先根遍歷左子樹

  (3)先根遍歷右子樹

  如右圖二叉樹的先根遍歷為:ABDECF

廣告

廣告