数据结构

1. 数据存储(物理)结构

• 顺序

  把逻辑上相邻的结点按顺序存储在物理上相邻的连续存储单元中，结点逻辑关系由存储单元的邻接关系体现。查找快，插入、删除慢。

• 链式

  用一组任意的存储单元存储逻辑上相邻的结点（存储单元可以连续也可以不连续），逻辑关系记录在指针域中。查找慢，插入、删除快。

• 哈希(散列)

  根据存储数据的内容计算哈希值来决定存储地址，根据内容查找时快

• 索引

  另外设置一个索引表来存储结点的地址，分开存放数据结点和结点逻辑关系

2. 数据逻辑结构

• 集合

  无序、不重复的元素构成集合

• 线性

  具有唯一前驱和唯一后继的“一对一”关系的有序线性结构

• 树形

  具有唯一前驱但可以有一个或多个后继的“一对多”关系的树形结构

• 图形

  具有多个前驱和多个后继的“多对多”关系的图形结构

3. 表、堆、栈和队列

• 表

  具有线性逻辑结构的就是线性表简称表，线性表又根据不同的物理实现方式分为：顺序表、链表。

• 堆

  堆是一种经过排序的树形结构。根结点最大的，父结点比子结点大的叫最大堆；根结点最小的叫最小堆。

• 栈

  栈是只允许在栈顶进行插入和删除操作的特殊线性表，栈又根据不同的物理实现方式分为：顺序栈、链式栈。具有“后进先出”的特性

• 队列

  队列是只允许在队尾插入，在队首删除的特殊线性表，队列又根据不同的物理实现方式分为：顺序队列、链式队列。具有“先进先出”的特性

4. 二叉树的深度

当前结点的深度为左右子树深度较大的值+1

class BinaryTreeNode<T> {
    var data: T
    var left: BinaryTreeNode?
    var right: BinaryTreeNode?
    init(_ data: T, _ left: BinaryTreeNode? = nil, _ right: BinaryTreeNode? = nil) {
        self.data = data
        self.left = left
        self.right = right
    }
}

func depth<T>(_ node: BinaryTreeNode<T>?) -> Int {
    guard let node = node else { return 0 }

    let left = depth(node.left) + 1
    let right = depth(node.right) + 1

    return left > right ? left : right
}