数据结构学习之二叉树（上）

一. 有哪些二叉树？

1. 二叉树
每个结点最多俩个子节点，分别是左结点和右结点。二叉树并不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点。

2. 满二叉树
叶子结点全都在最底层，除了叶子节点之外，每个结点都有左右俩个子节点，这种二叉树就叫做满二叉树。

3. 完全二叉树
叶子节点都在最底下俩层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种就是完全二叉树。

二. 二叉树有哪几种存储方式呢？

1. 链式存储法
假设每个节点有三个字段，其中一个存储数据，另外俩个指向左右子节点的指针。只要知道根节点，那么就可以通过左右子节点的指针，把整棵树串起来。这种方式较常用，看下图可能会更直观

链式

2. 顺序存储法
把根节点存储在下标 i = 1的位置, 那左子节点的存储下标 2 * i = 2 的位置，右子节点存储子 2 * i + 1 = 3 的位置。依次类推，那么 B 节点的左子节点存储在 2 * i = 2 * 2 = 4 的位置，右子节点存储在 2 * i + 1 = 2 * 2 + 1 = 5 的位置。

image.png

如果节点 x 存储在数组中下标为 i 的位置，下标为 2 * i 的位置就是左子节点，下标为 2 * i + 1 就是右子节点。反过来 ，下标为 i / 2 的位置存储的就是它的父节点。

三. 二叉树有哪些遍历方式呢？

经典的方法有三种
1. 前序遍历
前序遍历是指，对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，再打印它的右子树。

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

3. 后序遍历
后续遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。

image.png

二叉树的前、中、后序遍历就是一个递归的过程。那么写递归代码的关键，就是看能不能写出递推公式。

前序遍历的递推公式：
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

有了递推公式，那么这三种遍历方式的代码就容易写了

void preOrder(Node* root) {
  if (root == null) return;
  print root // 此处为伪代码，表示打印 root 节点
  preOrder(root->left);
  preOrder(root->right);
}

void inOrder(Node* root) {
  if (root == null) return;
  inOrder(root->left);
  print root // 此处为伪代码，表示打印 root 节点
  inOrder(root->right);
}

void postOrder(Node* root) {
  if (root == null) return;
  postOrder(root->left);
  postOrder(root->right);
  print root // 此处为伪代码，表示打印 root 节点
}

那想一下二叉树遍历的时间复杂度是多少呢？

从前、中、后序遍历的顺序图，可以看出来，每个节点最多会被访问俩次，所以遍历操作的时间复杂度，跟节点的个数成正比，也就是说二叉树的时间复杂度是O( n )。