Daily Summary(122)

11.2_Data Structure

1、平衡二叉树

• 平衡因子：左右子树深度之差
• 用途：是的二叉树排序效率最高

2、树与二叉树的转换

• 树→（无右）二叉树：
  1. 添线：所有兄弟连一条线
  2. 抹线：除最左边孩子以外的线抹除
  3. 旋转：将兄弟作为右子树
• 二叉树→树：
  1. 添线：与左子树的所有右结点连线
  2. 抹线：抹除之前连接的线
  3. 旋转

树的前序序列和其对应二叉树的前序序列相同；
树的后序序列和其对应二叉树的中序序列相同；

3、图

• 图的分类
  • 无向图
  • 有向图
• 完全图：具有n(n-1)/2条边的无向图
• 有向完全图：具有n(n-1)条弧的有向图