线性与非线性的资料结构

题组回顾与观念统整

在前三天的刷题实战中，我们一起完成了这三个经典的「资料结构」题：

• 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 担任资料工程师，同时也在中华电信、工研院与多所学校等单位持续开课。拥有多次大型技术会议讲者与竞赛获奖经验，持续在不同的平台发表对 #资料科学、 #网页开发 或 #软件职涯 相关的分享，邀请你加入 订阅 接收最新资讯。