特殊化的图

• 树是包含 n（n>=0）个结点的有穷集
• 每个元素称为结点
• 有一个特定的结点被称为根结点或树根
• 除根结点外的其余元素被分为 m（m>=0）个互不相交的集合

• 树是按层级构建的
• 一个节点的所有子节点与另一个节点的所有子节点无关
• 叶子节点都是独一无二的

• 节点的高度
• 节点的深度
• 节点的层数
• 树的高度

每个结点最多有两个子树的树结构

• 空二叉树
• 只有根节点二叉树
• 只有左子树
• 只有右子树
• 完全二叉树

• 广度优先搜索
• 深度优先搜索

def preorder(self, root):
    if root:
        self.traverse_path.append(root.val)
        self.preorder(root.right)
        self.preorder(root.left)

def inorder(self, root):
    if root:
        self.inorder(root.left)
        self.traverse_path.append(root.val)
        self.inorder(root.right)

def postorder(self, root):
    if root:
        self.postorder(root.left)
        self.postorder(root.right)
        self.traverse_path.append(root.val)

• 一个完全二叉树

1. 除了最底层其他每一层的节点都是满的
2. 在最底层从左往右填充节点

• 每个结点的值都必须大于等于（或小于等于）其子树中每个结点的值

1. 大于等于 -> 大顶堆
2. 小于等于 -> 小顶堆

• 堆化：O(n)

1. 从下往上
2. 从上往下

• 插入：O(longn)

1. 新元素一律先插入到堆的尾部
2. 依次从下向上调整整个堆的结构直到堆顶（HeapifyUp）

• 删最：O(logn)/O(1)

1. 将堆尾元素替换到顶部（即对堆顶被替代删除掉）
2. 依次从根向下调整整个堆的结构直到堆尾（HeapifyDown）

• 查最：O(1)

• 概念解析

1. 左子树上所有节点的值均小于它的根节点的值
2. 右子树上所有节点的值均大于它的根节点的值
3. 依次类推：左右子树也分别为二叉搜索树

• 常见操作
• 基本实现
• 简单分析

1. 左子树和右子树的深度差（平衡因子）的绝对值不超过 1
2. 左右子树也分别为平衡二叉树

由顶点的有穷非空集合和顶点之间边的集合组成：G(V, E)

• G（Graph）：表示一个图
• V（Vertex）：图 G 中的顶点的集合

1. 度：入度和出度
2. 点与点之间：连通与否

• E（Edge）：图 G 中边的集合

1. 有向和无向（单行线）
2. 权重（边长）

• 无向图
• 有向图
• 完全图

• 邻接矩阵 -> 很多条边
• 邻接表 -> 稀疏连接

• 微信等社交网络中的好友关系
• 地图导航及交通网络
• 游戏地图与迷宫
• 计算机网络
• 人际关系推荐系统
• 知识图谱