二叉树

种类

  • 满二叉树：2^k-1
  • 完全二叉树：除底层其他满，底层连续
  • 二叉搜索树：节点有一定顺序
  • 平衡二叉搜索树：左子树和右子树高度差不超过1

存储方式

  • 链式存储：左右指针
  • 顺序存储：两个子节点2i+1，2i+2
  • 一般把二叉树当作一个链表来构造

遍历方式

  • 深度优先搜索：递归法和迭代法，栈
    • 前序遍历，中左右
    • 中序遍历，左中右
    • 后序遍历，左右中
  • 广度优先搜索：迭代法，队列，一层一层/一圈一圈地遍历
    • 层序遍历

定义（ACM模式）

1
2
3
4
5
6
7
struct TreeNode{
  int val;
  TreeNode* left;
  TreeNode* right;
  //构造函数...
  略
}