樹和森林的遍歷

樹的遍歷

　　設樹T如下圖所示結點R是根根的子樹從左到右依次為TT…Tk
            
．樹T的前序遍歷定義
　　若樹T非空則
　①訪問根結點R
　②依次前序遍歷根R的各子樹TT…Tk

．樹的後序遍歷定義
　　若樹T非空則
　①依次後序遍歷根T的各子樹TlT…Tk
　②訪問根結點R
【例】對下面的(a)圖中的樹進行前序遍歷和後序遍歷得到的前序序列和後序序列分別是ABCDE和BDCEA 

    
　注意
　　① 前序遍歷一棵樹恰好等價於前序遍歷該樹對應的二叉樹
　　② 後序遍歷樹恰好等價於中序遍歷該樹對應的二叉樹

森林的兩種遍歷方法

．前序遍歷森林
　　若森林非空則
①訪問森林中第一棵樹的根結點
②前序遍歷第一棵樹中根結點的各子樹所構成的森林
③前序遍歷除第一棵樹外其它樹構成的森林

．後序遍歷森林
　　若森林非空則:
①後序遍歷森林中第一棵樹的根結點的各子樹所構成的森林
②訪問第一棵樹的根結點
③後序遍歷除第一棵樹外其它樹構成的森林
　注意
　　① 前序遍歷森林等同於前序遍歷該森林對應的二叉樹
　　② 後序遍歷森林等同於中序遍歷該森林對應的二叉樹
【例】對下面(a)圖中所示的森林進行前序遍歷和後序遍歷則得到該森林的前序序列和後序序列分別為ABCDEFICJH和BDCAIFJGHE而(b)圖所示二叉樹的前序序列和中序序列也分別為ABCDEFICJH和BDCAIFJGHE 

 
　　③ 當用二叉鏈表作樹和森林的存儲結構時樹和森林的前序遍歷和後遍歷可用二叉樹的前序遍歷和中序遍歷算法來實現

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