f674 - FJCU_109_Winter_Day2_Lab2 遍歷樹

🔗 前往 ZeroJudge 原題

題目描述

題目給定一棵樹，以 adjacency list 的形式表示，樹的根節點為 0。要求輸出這棵樹的前序、中序和後序遍歷序列。

解題思路

本題使用深度優先搜尋 (DFS) 演算法來遍歷樹。定義一個遞迴函式 dfs，接受節點編號 no 和遍歷類型 type 作為參數。type 的值分別為 0、1 和 2，對應前序、中序和後序遍歷。

• 前序遍歷：先輸出當前節點，再遞迴遍歷左子樹，最後遞迴遍歷右子樹。
• 中序遍歷：先遞迴遍歷左子樹，再輸出當前節點，最後遞迴遍歷右子樹。
• 後序遍歷：先遞迴遍歷左子樹，再遞迴遍歷右子樹，最後輸出當前節點。

在 main 函式中，首先讀取樹的結構，將節點的左子節點和右子節點儲存在 t 陣列中。然後，分別以 0、1 和 2 作為 type 的值，呼叫 dfs 函式三次，輸出前序、中序和後序遍歷序列。

複雜度分析

• 時間複雜度: O(N)，其中 N 是樹的節點數量。因為 DFS 演算法會遍歷樹中的每個節點一次。
• 空間複雜度: O(H)，其中 H 是樹的高度。這是因為遞迴呼叫堆疊的深度與樹的高度成正比。在最壞情況下，樹是一個鏈狀結構，H = N，空間複雜度為 O(N)。

程式碼

#include <iostream>
using namespace std;
int n,t[51][2],a,l,r;
inline void dfs(int no,int type){
	if(no==-1)return;
	if(type==0)cout << no << " ";
	dfs(t[no][0],type);
	if(type==1)cout << no << " ";
	dfs(t[no][1],type);
	if(type==2)cout << no << " ";
}
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> n;
	for(int i=0;i<n;++i){
		cin >> a >> l >> r;
		t[a][0]=l;
		t[a][1]=r;
	}
	for(int i=0;i<3;++i){
		dfs(0,i);
		cout << "\n";
	}
}