二叉樹的遍歷-數據結構

一、二叉樹遍歷的遞歸實現

二叉樹的遍歷是指按某種次序訪問二叉樹上的所有節點，使每個節點被訪問一次且僅被訪問一次。

由二叉樹的定義可知，一顆二叉樹由三部分組成：根、根的左子樹和根的右子樹。因此對二叉樹的遍歷只要按某種次序執行下列三步，就可以遍歷整個二叉樹。

（1） 訪問根結點；

（2）遍歷根的左子樹（即依次訪問左子樹上的全部結點）；

（3）遍歷根的右子樹（即依次訪問右子樹上的全部結點）。

因為左、右子樹都是二叉樹（可以是空叉樹），對它們的遍歷可以按上述方法繼續分解，直到每棵樹均為空二叉樹為止，由此可見，若以D、L、R分別表示訪問根結點、遍歷根結點的左子樹和遍歷根結點先左後右，即只考慮DLR、LDR和LRD,這三種次序分別稱為先序遍歷、中序遍歷和後序遍歷。

1.0 先序遍歷

若被遍歷的二叉樹為空，執行空操作；否則，依次執行下列操作：

（1）訪問根結點

（2）先序遍歷左子樹

（3）先序遍歷右子樹

2.0 中序遍歷

若被遍歷的二叉樹為空，執行空操作；否則，依次執行下列操作：

（1）中序遍歷左子樹；

（2）訪問根結點；

（3）中序遍歷右子樹；

3.0 後序遍歷

若被遍歷的二叉樹為空，執行空操作；否則，依次執行下列操作：

（1）後序遍歷左子樹；

（2）後序遍歷右子樹；

（3）訪問根結點。

上面給出的先序、中序和後序遍歷的定義都是遞歸的，因而根據定義很容易得到相應遍歷的遞歸算法。假定 visit(bt) 是一個已定義的過程，其功能是訪問指針bt 所指結點。

在二叉鏈表上實現三種遍歷的遞歸算法描述如下：

<code>void preorder(BinTree bt){
  if (bt!=NULL){
    visit(bt);
    preorder(bt->lchild);
    preorder(bt->rchild);
  }
}
void inorder(BinTree bt){
  
  if(bt!=NULL){
    inorder(bt->lchild);
    visit(bt);
    inorder(bt->rchild);
  }
}
void postorder(BinTree bt){
  if(bt!]NULL){
    postorder(bt->lchild);
    postorder(bt->rchild);
    visit(bt);
  }
}
/<code>

上述三種遍歷算法均可實現訪問一顆二叉樹中每個結點的訪問，且每個結點僅被訪問一次，由於訪問根結點的操作 visit(bt) 在算法中的位置不同，因此訪問根結點的順序不同，最後得到的結點訪問序列也不同。

閱讀更多 風箏科技前沿 的文章

關鍵字: 算法 數據結構 遍歷