本文同步更新於個人網站中,有更好的排版和程式碼區塊 highlighting 支援。
樹的走訪(traversal)或者說遍歷是一個很基礎的問題,有很多實際應用,可以用來找到匹配的字串、檔案路徑等問題。樹的走訪有兩種方式:深度優先(Depth First Search)和廣度優先(Breadth First Search)。
深度優先走訪又根據處理某個子樹的根節點順序不同,可以分為:前序(Preorder)、中序(Inorder)、後序(Postorder)。
從上面的流程描述來看,深度優先走訪很適合用遞迴來實現。我們透過下面的程式碼來實作前序、中序、後序這三種走訪方式,然後借助 type
去選擇走訪方式:
inOrder(callback) {
this._forEach(this.root, callback, 'middle');
}
preOrder(callback) {
this._forEach(this.root, callback, 'pre');
}
postOrder(callback) {
this._forEach(this.root, callback, 'post');
}
_forEach(node, callback, type) {
if (node) {
if (type === 'middle') {
this._forEach(node.left, callback, type);
callback(node);
this._forEach(node.right, callback, type);
} else if (type === 'pre') {
callback(node);
this._forEach(node.left, callback, type);
this._forEach(node.right, callback, type);
} else if (type === 'post') {
this._forEach(node.left, callback, type);
this._forEach(node.right, callback, type);
callback(node);
}
}
}
我們在總結一下這三種走訪的輸出結果有什麼特點:
現在來透過一道題目來驗收一下學習成果:
已知二元樹的中序和前序走訪結果,如何求後序走訪結果?例如一棵樹的前序走訪是“GDAFEMHZ”,而中序走訪是“ADEFGHMZ”,應該如何求其後序走訪結果?
具體步驟如下:
其實如果只是要求寫出後序走訪,甚至不要求專門佔用空間保存還原後的樹。只需要稍微改動第 5 步,就能實現要求。僅需把遞迴過程改成:
用程式表達的話如下:
function getPostorder(preorder, inorder, postorder = []) {
const root = preorder[0];
const inLeftTree = [];
const inRightTree = [];
let list = inLeftTree;
// 分離出 inorder 的左右子樹
for (let i = 0; i < inorder.length; i++) {
if (inorder[i] === root) {
list = inRightTree;
} else {
list.push(inorder[i]); // 根節點不會放在兩個子樹中
}
}
const boundary = inLeftTree.length;
const preLeftTree = [];
const preRightTree = [];
// 分離出 preorder 的左右子樹
for (let i = 1; i < preorder.length; i++) {
const el = preorder[i];
if (preLeftTree.length < boundary) {
preLeftTree.push(el);
} else {
preRightTree.push(el);
}
}
// postorder 左子樹遞迴
if (preLeftTree.length > 0) {
getPostorder(preLeftTree, inLeftTree, postorder);
}
// postorder 右子樹遞迴
if (preRightTree.length > 0) {
getPostorder(preRightTree, inRightTree, postorder);
}
// postorder 處理根節點
if (root) {
postorder.push(root);
}
return postorder;
}
題目中的 Tree 結構還原後如下:
使用 stack 取代遞迴,首先要用一個 while
迴圈將所有的節點都放入 stack 中,然後再一個一個取出來處理。先不放根節點,統一在迴圈內部去放。
xxxOrder(callback) {
const stack = [];
let node = this.root;
while (node || stack.length) { // 將所有子節點推入 stack
if (node) {
stack.push(node);
} else {
node = stack.pop();
}
}
}
迴圈中有兩個分支,分別做 push
和 pop
,push
的條件是 node
存在,以這個為界切開迴圈。前序和中序都是先 push left 再 push right,實作程式碼如下:
preOrder(callback) { // 口訣:中左右
const stack = [];
let node = this.root;
while (node || stack.length) {
if (node) {
callback(node); // 中先於左
stack.push(node);
node = node.left; // push left
} else {
node = stack.pop();
node = node.right; // push right
}
}
}
inOrder(callback) { // 口訣:左中右
const stack = [];
let node = this.root;
while (node || stack.length) {
if (node) {
stack.push(node);
node = node.left; // push left
} else {
node = stack.pop();
callback(node); // 中先於右
node = node.right; // push right
}
}
}
postOrder(callback) { // 口訣:左右中
const stack = [];
const out = [];
let node = this.root;
while (node || stack.length) {
if (node) { // 類似於 preOrder,可以當作 根 -> 右 -> 左,然後再反轉
stack.push(node);
out.push(node);
node = node.right;
} else {
node = stack.pop();
node = node.left;
}
}
while (out.length) {
callback(out.pop());
}
}
二元搜尋樹後面會介紹到,總之就是一棵樹,每個節點的值都大於左子樹的所有節點的值,我們要從這棵樹中找出第 k
大的節點。我們這裡先關注如何透過中序走訪來解決這個問題。
方法一:最樸素的方法是透過中序走訪將二元樹轉換成陣列,然後取出索引值為 k-1
的元素即可。
function kthNode(root, k) {
if (!root || k < 0) {
return null;
}
const array = [];
inOrder(root, array);
if (k > array.length) {
return null;
}
return array[k - 1];
}
function inOrder(root, array) {
if (root === null) {
return;
}
inOrder(root.left, array);
array.push(root);
inOrder(root.right, array);
}
方法二:不用收集所有節點,設置一個計數器,在中序走訪的過程中,累加訪問過的節點數,當計數器的值等於 k
時,回傳該節點。
function kthNode2(root, k) {
let index = 0;
const _kthNode = (root, k) => {
if (root) {
let node = _kthNode(root.left, k);
if (node !== null) {
return node;
}
index++;
if (index === k) {
return root;
}
node = _kthNode(root.right, k);
if (node !== null) {
return node;
}
}
return null;
};
return _kthNode(root, k);
}
我們今天已經看完了深度優先走訪的實作,基本上深度優先走訪的實作都是透過遞迴或者 stack 來實現的,而且遞迴的實現方式比較簡單,所以通常只需要掌握遞迴的實現方式就可以了。明天我們要繼續來看到廣度優先走訪,並且還要來實作如何在終端中 print 出一棵樹。