目前為止我們應用樹狀結構來當作我們的資料結構實現了很多有效率的ADT(Abstract Data Type)。這章節要來探討樹狀結構的另一種作用，traversal。

假設我們把一個File System用樹狀結構來表示如下：

接著我們可能會想做到一些功能，比如我想知道每個資料夾包含的檔案大小是多少？或者我想印出由上到下整個File System包含了哪些資料夾跟檔案？要在樹狀結構做到這些功能，就不像一個list只要iterate就好，因為tree要iterate會有順序的問題，而traversal就是在討論這件事情。

Tree的Traversal主要分為兩個方向：

1. Depth First Traversal
2. Level Order Traversal

等等的討論會以下面這棵樹來舉例：

首先來談談Depth First Traversal：

顧名思義這類的Traversal會優先往深度來去拜訪節點，等拜訪完最深的節點後，再回到parent，往其他的分支鑽。這樣的traversal有三種方法：

1. Preorder Traversal

Preorder會先紀錄root node，然後優先往左拜訪直到盡頭，之後往右拜訪。

所以用上面那棵樹來舉例的話，就會是DBACFEG

以code來表示會是：

preorder(BSTNode node){
	if(node == null){
		return;
	}
	print(node.val);
	preorder(node.left);
	preorder(node.right);
}

2. Inorder Traversal

Inorder會先往左拜訪直到盡頭，之後紀錄root node，然後往右拜訪。

所以用上面那棵樹來舉例的話，就會是ABCDEFG

以code來表示會是：

inorder(BSTNode node){
	if(node == null){
		return;
	}
	inorder(node.left);
	print(node.val);
	inorder(node.right);
}

3. Postorder Traversal

Postorder會先往左拜訪直到盡頭，然後往右拜訪，最後紀錄root node。

所以用上面那棵樹來舉例的話，就會是ACBEGFD

以code來表示會是：

postorder(BSTNode node){
	if(node == null){
		return;
	}
	postorder(node.left);
	postorder(node.right);
	print(node.val);
}

再來談談Level Order Traversal，有別於剛剛先往深度拜訪的原則，Level Order Traversal就是往寬度來優先拜訪。

所以以上面那棵樹為範例的話，就會是DBFACEG

以code來實作會用Breath-First Search演算法，會需要一個Queue來紀錄拜訪到的node有哪些小孩，並根據Queue的原理poll出下一個要拜訪的node：

bfs(BSTNode node){
		if(node == null){
		    return;
		}
		Queue<TreeNode> queue = new LinkedList<>();
		queue.add(node);
		while(queue.size() != 0){
		    List<Integer> levelList = new ArrayList<>();
		    int levelSize = queue.size();
		    for(int i = 0; i < levelSize; i++){
		        TreeNode current = queue.poll();
		        levelList.add(current.val);
		        if(current.left != null){
		            queue.add(current.left);
		        }
		        if(current.right != null){
		            queue.add(current.right);
		        }
		    }
		    print(levelList);
		}
}

實作過程有趣的地方在於要從queue中poll出node來拜訪時，queue中的元素剛好就會是當前這個level的所有元素，因為每一層拜訪完時，前一層的元素都被poll出去了，真是完美的queue應用情境。

Slides are from Josh Hug CS61B

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License