王道程序员求职宝典（十一）指针与引用，树

指针与引用

• 指针
  • 声明
  • typedef
    • 别名
    • 类型检查
  • void*指针
  • 指向指针的指针
  • 函数指针
    • typedef简化函数指针定义
    • 初始化
      • 函数名可直接对函数指针做初始化
      • 函数名=&函数名
    • 使用
      • 指针（）
      • &指针（）
    • 函数指针做形参
    • 返回函数指针
      • 返回类型 (*函数指针(形参))(形参)
    • 指向重载函数的指针
• 引用
  • 和指针区别
    • 引用不能为空
    • 引用不可改变指向
    • sizeof(引用)=引用变量大小
    • 动态分配对象必须用指针
    • &引用=引用变量的地址
  • const引用
  • 引用做类数据成员
    • 必须定义构造函数
    • 使用初始化列表

树

• 树的基本概念和性质
  • 度，层次，深度，有序，森林
  • 基本性质
    • 结点树等于度数之和+1
    • m叉树i层最多m^(i-1)结点
    • 高度为h的m叉树最多有(m^(h-1))/(m-1)
    • n个结点m叉树最小高度为 向上取整(log(n(m-1)+1))
• 二叉树
  • 特殊二叉树
    • 满二叉树
    • 完全二叉树
      • n奇偶数性质
      • 最小高度
  • 二叉树性质
  • 二叉树存储结构
    • 顺序存储
    • 链式存储
  • 二叉树遍历
    • 递归方法
    • 非递归方法
      • 后序非递归方法
    • 层次遍历
• 二叉树的应用
  • 判断二叉树是否相同
  • 二叉树深度
  • 求二叉树结点最大距离
  • 由遍历序列构造二叉树
• 树的应用
  • 二叉排序树
    • 判断是否为二叉排序树
  • 平衡二叉树
    • 判断是否为平衡二叉树
    • 红黑树
  • 哈夫曼树及哈夫曼编码
• 并查集
  • 单链表实现
  • 并查集森林
    • 按秩合并
    • 路径压缩