中序遍歷

標籤: 暫無標籤

17

更新時間: 2013-09-04

廣告

廣告

  中序遍歷(LDR)中序遍歷也叫做中根遍歷,可記做左根右。
  中序遍歷首先遍歷左子樹,然後訪問根結點,最後遍歷右子樹。在遍歷左、右子樹時,仍然先遍歷左子樹,再訪問根結點,最後遍歷右子樹。即:
  若二叉樹為空則結束返回,
  否則:
  (1)中序遍歷左子樹。
  (2)訪問根結點。
  (3)中序遍歷右子樹。
  注意的是:遍歷左右子樹時仍然採用中序遍歷方法。
  即左子樹(B D E)還是左邊開始(D),然後是(B),再是右邊(E),完后經過(A),接著右子樹(C F) 還是左邊開始(F),再是中間(C),
  即順序是DBEAFC
  中序遍歷的時間複雜度為:O(n)。
  如果一棵二叉排序樹的節點值是數值,中序遍歷的結果為升序排列的數組。可以利用該性質檢測一棵樹是否為二叉排序數。

1 中序遍歷 -程序實現

廣告