树和二叉树

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分

树和二叉树

• 树的逻辑结构
  • 树的定义和基本术语
  • 树的抽象数据类型定义
  • 树的遍历操作
    • 前序遍历
    • 后序遍历（对应二叉树的中序）
    • 层序遍历
• 树的存储结构
  • 双亲表示法
  • 孩子表示法
    • 多重链表表示法
    • 孩子链表表示法
  • 双亲孩子表示法
  • 孩子兄弟表示法（二叉链表）
• 二叉树的逻辑结构
  • 二叉树的定义
  • 二叉树的性质
    • 第i层最多有2^i-1个结点
    • 深度为k的二叉树中，最多有(2^k)-1个结点，最少有k个结点
    • 二叉树中，n0=n2-1
    • n个结点的完全二叉树的深度为log2n(下取整)+1
    • 双亲与孩子的编号对应关系
  • 二叉树的抽象数据类型
  • 二叉树的遍历操作
    • 前序遍历
    • 中序遍历
    • 后序遍历
    • 层序遍历
• 二叉树的存储结构及实现
  • 顺序存储结构
  • 二叉链表（实现代码）
  • 三叉链表
  • 线索链表
• 二叉树遍历的非递归算法（栈）
  • 前序遍历非递归算法
  • 中序遍历非递归算法
  • 后序遍历非递归算法
• 树、森林、与二叉树的转换
  • 树转二叉树
  • 森林转二叉树
  • 二叉树转树或森林
  • 森林的遍历
    • 前序遍历
    • 后序遍历（相当于对应二叉树的中序遍历）