二分查找 ＆＆ 树

22. 二分查找 && 树

22.1 二分查找

22.1.1 递归代码实现

22.1.2 时间复杂度

• 最优——O(1)
• 最坏——O(logn)

22.2 树

22.2.1 特点

• 每个结点有0个或多个子节点
• 没有父节点的结点称为根节点
• 每一个非根节点有且仅有一个父节点
• 除了根节点外，每个子节点可以分为多个不想交的子树

22.2.2 相关术语

• 节点的度
  一个节点含有的子节点的个数称为该节点的度
• 树的度
  一棵树中，最大的节点的度称为树的度
• 叶节点(终端节点)
  度为0的结点
• 父亲节点(父节点)
  若一个节点含有子节点，则这个节点称为其子节点的父节点
• 孩子节点(子节点)
  一个节点含有的子树的根节点称为该节点的子节点
• 兄弟节点
  具有相同父节点的结点互称为兄弟节点
• 节点的层次
  从根节点定义起，根为第一层，以此类推
• 树的高度或深度
  树中节点的最大层次
• 堂兄弟节点
  父节点在同一层的节点互为堂兄弟
• 节点的祖先
  从根到该节点所经分支上的所有节点
• 子孙
  以某节点为根的子树中任一节点都称为该节点的子孙
• 森林
  由m(m >= 0) 棵互不相交的树的集合称为森林

22.2.3 种类

• 有序树
  • 霍夫曼树
  • B树
  • 二叉树
    • 完全二叉树
    • 满二叉树
    • 非完全二叉树
    • 平衡二叉树AVL树
    • 排序二叉树BST树——包含空树
• 无序树

22.2.4 二叉树的存储

• 顺序存储
• 链式存储

22.2.5 应用场景

数据库索引

22.2.6 二叉树

• 性质

  

• 遍历

  • 广度优先
    • 找到最短路径
  • 深度优先
    • 先序——根左右
    • 中序——左根右
    • 后序——左右根