數據結構之二叉樹的遍歷

二叉樹遍歷的基本概念 　

　　遍歷（Traversal）是指沿著某條搜索路線依次對樹中每個結點均做一次且僅做一次訪問
　　從二叉樹的遞歸定義可知二叉樹是由三個基本單元組成根結點左子樹和右子樹因此若能依次遍歷這三部分便是遍歷了整個二叉樹假如以LDR分別表示遍歷左子樹訪問根結點和遍歷右子樹則可有DLRLDRLRDDRLRDLRLD六種遍歷二叉樹的方案若限定先左後右則只有前三種情況分別稱之為前序遍歷中序遍歷和後序遍歷
 
前序遍歷

　　前序遍歷（Preorder Traversal）亦稱先序遍歷定義為
　　若二叉樹為空則空操作否則執行下列步驟
　　（）訪問根結點
　　（）遍歷左子樹
　　（）遍歷右子樹

中序遍歷

　　中序遍歷（Inorder Traversal）定義為
　　若二叉樹為空則空操作否則執行下列步驟
　　（）遍歷左子樹
　　（）訪問根結點
　　（）遍歷右子樹

後序遍歷

　　後序遍歷（Postorder Traversal）定義為
　　若二叉樹為空則空操作否則執行下列步驟
　　（）遍歷左子樹
　　（）遍歷右子樹
　　（）訪問根結點

構造二叉鏈表

　　基於先序遍歷構造二叉鏈表算法
　　依據前序遍歷中序遍歷或中序遍歷後序遍歷構造二叉樹

From:http://tw.wingwit.com/Article/program/sjjg/201311/23163.html