二叉树基础

相关概念

• 根节点：没有父节点的结点。
• 叶子节点：没有子节点的结点。
• 高度：节点到叶子节点的“最长路径”(边数)。
• 深度：根节点到这个节点所经历的“边的个数”。
• 层：节点的深度+1。
• 树的高度：根节点的高度。

图片引自《数据结构与算法之美》王争

二叉树（Binary Tree）

• 每个节点最多有两个“叉”，也就是两个子节点，分别是“左子节点”和“右子节点”；二叉树并不要求每个节点都有2个子节点。

满二叉树

• 除叶子节点外，每个节点都有左右2个子节点。

完全二叉树

• 叶子节点都在最底下2层，且最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大。

二叉树的存储方法

• 链式存储法
  基于指针，每个节点有3个字段，有个存储数据，另外两个是指向左右子节点的指针。
• 顺序存储方法
  基于数组，节点 X 存储在数组中下标为 i 的位置，下标为2*i的位置存储的就是其左子节点，下标为2*i+1的位置存储的就是其右子节点。此时，如果被存储的树是一棵完全二叉树，用数组存储是最节省内存的一种方式。“堆”其实就是一种完全二叉树，最常用的存储方式是数组。

二叉树的遍历

• 前序遍历
  对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。

preOrder(r) = print r -> preOrder(r->left) -> preOrder(r->right)

• 中序遍历
  对于任意节点来说，先打印它的左子树，然后打印它本身，最后打印它的右子树。

inOrder(r) = inOrder(r->left) -> print r -> inOrder(r->right)

• 后序遍历
  对于任意节点来说，先打印它的左子树，再打印它的右子树，最后打印这个节点本身。

postOrder(r) = postOrder(r->left) -> postOrder(r->right) -> print r

二叉树遍历的时间复杂度

• 每个节点最多会被访问2次，所以遍历操作的时间复杂度和节点个数n成正比，也就是说二叉树遍历的时间复杂度是O(n)。