在筆者的『基礎資料結構 3 — 樹狀結構與二元樹』的這篇文章中，我們介紹了樹的基本概念，也學習了如何遍歷樹的方法，在之前的文章中，我們有說到，如果要遍歷樹大至上有以下三種方法 :
中序追蹤 (in-order): 先走訪左子樹，然後在根，最後在右子樹。(DBEAFCG)前序追蹤 (pre-order): 先走訪根，然後在左子樹，最後在右子樹。(ABDECFG)後序追蹤 (post-order): 先走訪左子樹，然後在右子樹，最後是根。(DEBFGCA)level-order: 先走訪第一層節點，再走訪第二層，最後會走到最後一層。(ABCDEFG)
補充: 這裡我們在補充第四種追蹤
level-order，事實上它就是BFS，也就是一層一層的掃
那為什麼我們這裡要在拿來說一次呢 ?
因為我們之前實作的方法是用『 Recursion 』來實作。
有寫過程式的人大概會知道，在使用recursion 實作程式碼，常常有可能會發生memory leak事件，所以我們這篇將要來說明，如何不使用它，來實作以上三種 traversal。
中序追蹤 (in-order)
左 => 根 => 右
iteration
- 直接先深入最深的左子樹，並將行經的節點，存放到 stack 中。
- 然後深入到最後時，發現是 null ，開始從 stack 中 pop 東西出來。
- 接下來在從 pop 出的節點的右子樹開始重複第一個步驟。
/**
* Tree inordrTraversal (no recursive)
* Tip: 左根右
*/
BinarySearchTree.prototype.inorderTraversal = function(){
let stack = [];
let current = this.root;
while (current !== null || stack.length !== 0) {
while(current != null){
stack.push(current);
current = current.left;
}
current = stack.pop();
console.log(current.val);
current = current.right;
}
}
recursion
BinaryTree.prototype.inOrderTraverse = function(callback) {
inOrderTraverseNode(this.root,callback);
function inOrderTraverseNode(node,callback) {
if(node !== null){
inOrderTraverseNode(node.left,callback);
callback(node.data);
inOrderTraverseNode(node.right,callback);
}
}
};
前序追蹤 (pre-order)
根 => 左 => 右
iteration
- 先將 root 存放到 stack 中。
- 然後因為pre-order 是先根在子樹，所以直接從 stack pop 出節點輸出。
- 接下來在將左右子樹放入 stack。
- 重複第二個步驟。
/**
* Tree preorderTraversal (no recursive)
* Tip: 根左右
*/
BinarySearchTree.prototype.preorderTraversal = function(){
let stack = [];
stack.push(this.root);
let current;
while (stack.length > 0) {
current = stack.pop();
console.log(current.data);
if(current.right){
stack.push(current.right);
}
if(current.left){
stack.push(current.left);
}
}
}
recursion
BinaryTree.prototype.preOrderTraverse = function(callback) {
preOrderTraverseNode(this.root,callback);
function preOrderTraverseNode(node,callback) {
if(node !== null){
callback(node.data);
preOrderTraverseNode(node.left,callback);
preOrderTraverseNode(node.right,callback);
}
}
};
後序追蹤 (post-order)
左 => 右 => 根
iteration
- 將第一個節點丟到 stack 中。
- 然後在進行 while
- pop 出節點，然後丟到 temp 陣列中。
- 在將該節點的左右子樹丟到 stack 中。
- 重複 while
- 最後在將 temp 陣列中的節點取出。
/**
* Tree postOrder Traversal (no recursive)
* Tip: 左右根
*/
BinarySearchTree.prototype.postOrderTraversal = function() {
let stack = [];
let temp = [];
let current = this.root;
let isEnd = false;
stack.push(current);
while(stack.length > 0){
current = stack.pop();
temp.push(current);
if(current.left != null){
stack.push(current.left);
}
if(current.right != null){
stack.push(current.right);
}
}
while(temp.length > 0){
current = temp.pop();
console.log(current.data);
}
}
recursion
BinaryTree.prototype.postOrderTraverse = function(callback) {
postOrderTraverseNode(this.root,callback);
function postOrderTraverseNode(node,callback) {
if(node !== null){
postOrderTraverseNode(node.left,callback);
postOrderTraverseNode(node.right,callback);
callback(node.data);
}
}
};
層級追蹤 (level-order BFS)
就是所謂的 BFS 廣度優先搜尋，也就是一層一層找。
- 將第一個 root 丟入 queue 中 ( queue 是先進先出 )。
- 從 queue 中取出節點。
- 然後再將左右子樹丟進去 queue 中。
- 然後就重複 2 的動作。
下面的程式碼中多了一些記 level 的東西，那是因為我希望的輸出結果會像下面這樣，所以才有下面的其它步驟。
1
2 3
[[1],[2,3]]
iteration
BinarySearchTree.prototype.bfsTraversal = function() {
let current;
let queue = [];
let result = [];
if(!this.root){
return [];
}
queue.push({
node: this.root,
level: 0
});
while (queue.length > 0){
current = queue.shift();
if(result[current.level]){
result[current.level].push(current.node.data);
}else{
result[current.level] = [];
result[current.level].push(current.node.data);
}
if(current.node.left != null){
queue.push({
node: current.node.left,
level: current.level + 1
});
}
if(current.node.right != null){
queue.push({
node: current.node.right,
level: current.level + 1
})
}
}
return result;
}
let tree = new BinarySearchTree();
tree.add(new Node(1));
tree.add(new Node(2));
tree.add(new Node(3));
tree.add(new Node(4));
tree.add(new Node(5));
tree.add(new Node(6));
tree.add(new Node(7));
//輸出: [ [ 1 ], [ 2, 3 ], [ 4, 5, 6, 7 ] ]