树和图

基础知识

树

1. 基本概念

• 树叶leaf
• 兄弟sibling
• 深度depth，根的深度为0
• 到节点的路径path
• 节点的高height：该节点到树叶的长度

左儿子，右兄弟表示法（可转化为二叉树）

2. 二叉树 Binary Tree

• 先序遍历
• 中序遍历
• 后序遍历
• 表达式树

3. 二叉查找树

任意节点的左子树的所有关键值小于该节点值，右子树的所有关键值大于该节点值（任选一方等于）

图

基本知识

• 由顶点（vertex）集与边（edge）集组成
• 边称为弧arc
• 有向图和无向图
• 边可能有权（weight）或值（cost）
• 路径和路径长
• 无边路径长为0
• 有边到自己叫环（loop），一般研究无环图（顶点互异，第一和最后一个可能相同）
• 圈（cycle），是满足W1 = Wn(顶点序列)，长不为0的路径
• 有向无圈图，acyclic，简称DAG
• 连通的：如果一个无向图中从每一个顶点到每个其他顶点都存在一条路径.
• 具有这样性质（连通的）的有向图称为是强连通的
• 弱连通的，它的基础图（underlying graph）是连通的，即边去掉方向。有向不是强连通的。
• 完全图(complete graph)，每一对顶点间都存在一条边。
• 顶点的入度（indegree）

存储结构

• 邻接矩阵，二维数组：适用于稠密（dense）的图
• 邻接表（数组加链表）：使用于稀疏（sparse）的图