題組回顧與觀念統整

在前三天的刷題實戰中，我們一起完成了這三個經典的「資料結構」題：

• LeetCode 雙刀流： 206. Reverse Linked List
• LeetCode 雙刀流：700. Search in a Binary Search Tree
• LeetCode 雙刀流：144. Binary Tree Preorder Traversal

如果問你心中第一個想到的資料結構會是什麼呢？「鏈結串列（Linked List）」或「樹（Tree）」想必是許多人心中一個出現的資料結構。比起大部分程式語言內建的陣列或物件來說，鏈結串列和樹更容易卡關，也增加了對於資料結構的一絲恐懼感。這三題我們就挑選有關於鏈結串列和樹的題目一探究竟：

➤「Reverse Linked List」

在「Reverse Linked List」題目中，要求將串接而成的鏈結串列「倒序」排列，但因為鏈結串列「相連」的特性（最差情況需要從頭一個一個找到尾），需要思考怎麼操作才能實現倒序的結果。「方法 ①：交換法」透過交換的方式將指針的方向倒序，並且利用「三數交換」進行優化。「方法 ②：遞迴」根據「相連」的特性出發，利用一層一層運算，執行直到沒有下一個為止的做法。換句話說，遞迴能夠「先把下一個記起來，將自己反過來指向前一個」的想法實現倒序的目的。

➤「Search in a Binary Search Tree」

二元搜尋樹會根據資料數值加入的先後順序與大小依序插入，「Search in a Binary Search Tree」練習二元搜尋樹典型的搜尋動作。「方法 ①：迴圈迭代法」對於二元搜尋樹進行迭代運算一個一直找，目標值比較小就往左找、目標值比較小就往右找，直到找到該數值即回傳。「方法 ②：遞迴」概念是「判斷這一層是否符合條件，否則就往兩個子樹各別往下層找」，然後直到找到為止直接回傳，這就是一種適合遞迴方法的典型情境。

➤「Binary Tree Preorder Traversal」

相對於二元搜尋樹來說條件相對沒有那麼嚴謹的二元樹也是一種常見的樹，這一題實現樹結構常見的遍歷方法「前序遍歷（Preorder Traversal）」。所謂的前序遍歷就是先找出「中間節點」、再找「左邊節點」、最後才找「右邊節點」以此類推。「方法 ①」利用迴圈的方式迭代一個一個找、「方法 ②」搭配 Recursive 的概念，取得「中間節點」之後，再往下的「左邊節點」找、找完再找「右邊節點」，利用遞迴對每一個點都做一樣的規則。

抽象資料結構（ADT，Abstract Data Type）

什麼是資料結構（Data Structure）？「資料」是指由多個元素所組成的有限集合，這些元素的組合關係稱為「結構」。換句話說，就是「一組資料在程式當中的儲存/組織方式」，有時候我們也會稱為容器。不同的程式語言會內建提供一些常見的資料結構，例如在 JavaScript 提供「陣列（Array）」和「物件（Object）」、Python 則提供「列表（List）」和「字典（Dictionary）」。

資料容器根據書上的定義如下：

A data type consists of two parts:
(1) a set of data 
(2) the operations operations that can be performed on the data

除了使用內建的陣列或物件之外，我們也可以利用他們拼湊出其他的資料型態，稱為抽象資料結構。關於抽象資料結構的定義如下：

"The specification (spec.) of data and the spec. of operations" are independent with
"the representation of data and the implementation of operations."

這裡的抽象指的是「不管內部怎麼實作，只要可以符合指定的操作的特性」就可以稱為是資料結構。

線性與非線性

從鏈結串列（Linked List）到樹（Tree）或二元搜尋樹（BST，Binary Search Tree），是一種從線性到非線性的概念。線性指的是只會有下一個可能，終究只會有一條路徑；非線性的話則可能有不同的分岔，可能會產生出兩條以上的可能路徑。以二元樹來說，每一個點最多可能會有兩個點的下一個可能，因此可能就會有「不同往下找」的做法，應該先找完同一層的，還是先找到最底再回頭找，就會有許多的變化可以玩。對於一個容器「建立」、「新增」、「刪除」或「查詢」都是基本的操作，不過當遇到複雜的鏈結串列或樹結構，就多了一層的挑戰。

鏈結串列

鏈結串列就是一種抽象資料結構，實作上可以先定義一個 Node。但每個 Node 最多只會連接到下一個點，所以稱為線性的。

class Node {
    constructor(item) {
        this.item = item;
        this.next = null;
    }
}

再將 Node 從 head 開始串接起來：

class LinkedList {
    constructor(){
        this.head = new Node( 'head' );
    }
    append(node){
        ….
    }
}

鏈結串列中常見的操作有建立、查詢（遍歷）、新增、移除和插入，適合插入刪除、但不適合查詢（最差情況需要從頭一個一個找到尾）。

樹

與鏈結串列不同的樹，實作上也需要先需要定義一個 Node，差別是樹上每一個點可以有連接到多個點（稱為子樹）。

function TreeNode(val, left, right) {
     this.val = (val===undefined ? 0 : val)
     this.left = (left===undefined ? null : left)
     this.right = (right===undefined ? null : right)
}

然後再利用 root 將點跟點串起來：

function Tree () {
    this.root = new TreeNode( 'root'); 
    ...
}

嗨，大家好！我是維元，一名擅長網站開發與資料科學的雙棲工程師，斜槓於程式社群【JSDC】核心成員及【資料科學家的工作日常】粉專經營。目前在 ALPHACamp 擔任資料工程師，同時也在中華電信、工研院與多所學校等單位持續開課。擁有多次大型技術會議講者與競賽獲獎經驗，持續在不同的平台發表對 #資料科學、 #網頁開發 或 #軟體職涯 相關的分享，邀請你加入 訂閱 接收最新資訊。