演算法筆記:樹 (Tree)

沒想到演算法筆記也到了第五篇了(拭淚),每次都要好好把內容吸收才能寫出作業,小心得:大部分時候解不出 leetcode 題目是根本就不知道題目後面的概念,與其想破頭不如先讀理論再來解題目。

Tree 是一種資料結構,由 parent & children , node, root node 三個概念組成

樹的最根本特徵就是:在樹的結構裡,只有一個root(樹根),並且不存在cycle
此特徵將衍生出另外兩項等價的性質:

  1. 在樹中若要從root尋找特定node,一定只存在一條路徑(path)。
  2. 每個node只會有一個parent。
樹只有一個 root , leaves 的數目沒有限制
若樹的node只有指向left subtree(左子樹)與right subtree(右子樹)時,又稱為Binary Tree(二元樹)
搜尋速度降為 log n

透過 new 它會幫我們建立一個物件,然後裡面有 TreeNode 這個 function 裡面的內容,並且變成了屬性名稱和屬性值,也就是 root.val == 1,root.right == 2,root.left == 3。

Full & Complete Binary Tree

有兩類Binary Tree十分常見,分別為Full Binary Tree以及Complete Binary Tree
(這裡不知該翻作「完滿二元樹」還是「完整二元樹」,所以就不做翻譯當作專有名詞,請見諒。)

A. Full Binary Tree:

如圖三所示,一棵Full Binary Tree(或稱作Perfect Binary Tree)具有以下性質:

  • 所有internal node都有兩個subtree(也就是兩個child pointer);
  • 所有leaf node具有相同的level(或相同的height)。

由以上性質能夠推論出:

  • 若一棵Full Binary Tree的leaf node之level為nn,整棵樹共有2n−12n−1個node。
  • 例如,若leaf node的level為4, 整棵樹共有15個node。

並且,每個node與其child有以下關係:

  • 第ii個node的left child之index為 2i2i;
  • 第ii個node的right child之index為 2i+12i+1;
  • 除了root之parent為NULL之外,第ii個node的parent之index為 ⌊i2⌋⌊i2⌋ 。
Full Binary Tree
圖三:若一棵Full Binary Tree的leaf node之level為nn,整棵樹共有2n−12n−1個node。

B. Complete Binary Tree:

若一棵樹的node按照Full Binary Tree的次序排列(由上至下,由左至右),則稱此樹為Complete Binary Tree

以圖四及圖五作說明:

圖四的樹共有10個node,且這十個node正好填滿Full Binary Tree的前十個位置,則此樹為Complete Binary Tree。

Complete Binary Tree
圖四:這是一棵Complete Binary Tree。

圖五的樹共有11個node,但是第11個node(K)應該要是第5個node(E)的child,因此,此樹並非Complete Binary Tree。

Not Complete Binary Tree
圖五:這不是一棵Complete Binary Tree。

Javascript 的 Object 建立

當我們使用 new 這個關鍵字時,實際上會先有一個空的物件被建立。接著 TreeNode 這個函式會被執行(invoke)。我們知道當函式執行的時候,在 execution context 中會有 this 被建立,而當我們使用 new 的時候,函式裡面的 this 會被指定成剛剛所建立的那個空物件。所以當執行 TreeNode 這個 function,執行到 this.firstName 和 this.lastName 時,因為 this 現在指稱的是那個空物件,所以實際上是在幫這個空物件賦予屬性名稱和屬性值。在這樣的過程中,只要這個函式建構式 TreeNode 沒有指定 return 為其他物件,它就會直接回傳給我們這個新建立的物件。接著讓我們透過程式碼來更清楚的了解這個執行的過程:

透過 new 會幫我們建立一個空的物件

現在我把我們原本的程式碼改成這樣:

function TreeNode(){
  console.log(this);
}

const root = new TreeNode();

這時候程式碼回傳的結果如下,表示的確在執行這個程式的過程中幫我們建立了一個新的空物件

TreeNode {}

函式的最後若return其他物件,則原新物件內容會被覆蓋

現在,讓我們把原本的程式碼稍微做如下修改,增加第六行的內容:

function TreeNode(val){
  this.val = val;
  this.right = this.left = null;
  return  {"RETURN":"原本this的內容就不會被回傳"};
}

const root = new TreeNode();
console.log(root)

回傳的結果如下,原本被建立的新物件不會被回傳,而是回傳我們最後return給它的內容:

Object {"RETURN":"原本this的內容就不會被回傳"}

function constructor 的實際應用

由上面的方法,我們可以透過 function 的方式來建立一個新的物件,如果我們想要建立出同屬性名稱但不同屬性值的物件內容,我們可以把物件的屬性值變成參數,如此就能透過此 function constructor 建立出許多不同的物件:

function TreeNode (val) {
  this.val = val;
  this.right = this.left = null;
}

const root = new TreeNode(1);
console.log(root);
var root_left = new TreeNode(2);
console.log(root_left);

如此,我們就可以透過同一個函式建構式建立出很多不同的物件:

TreeNode {val: 1, right: null, left:null}
TreeNode {val: 2, right: null, left:null}

此外,我們會把根據建構子(constructor)所建立出來的物件稱作是實例(instance)

注意!如果我們忘了加上關鍵字 new

這裡有一個地方我們需要非常留意,如果你在程式撰寫的過程當中,忘記加上 new 這個關鍵字的話,例如:

const root = TreeNode(1);
console.log(root);

如此,因為 JavaScript 不知道你是要執行這個程式,還是要根據這個 function 去建立object,因次最後回傳 undefined 的結果。

BST 三種 traversal 方式

左中右:輸出最左邊的 node 再來是這個 node 的 parent 再來是右邊的 child node
中左右

BST 題目示範

題目:兩個 BST 是否相同

補充說明:Tries 資料結構

Trie 樹常用於搜尋提示。如當輸入一個網址,可以自動搜尋出可能的選擇。當沒有完全匹配的搜尋結果,可以返回字首最相似的可能

參考資料:
1. http://alrightchiu.github.io/SecondRound/treeshu-introjian-jie.html
2. https://pjchender.blogspot.com/2016/06/javascriptfunction-constructornew.html
3. http://alrightchiu.github.io/SecondRound/binary-search-tree-introjian-jie.html
4. http://alrightchiu.github.io/SecondRound/binary-tree-introjian-jie.html

Share on facebook
Facebook
Share on linkedin
LinkedIn
Share on twitter
Twitter

More to explorer

Close Menu