算法学习十七、二叉树基础(上)

树(Tree)

“树”这种数据结构很像我们现实生活中的“树”,这里面每个元素我们叫作“节点”;用来连线相邻节点之间的关系,我们叫作“父子关系”。

比如下面这幅图,A 节点就是 B 节点的父节点,B 节点是 A 节点的子节点。B、C、D 这三个节点的父节点是同一个节点,所以它们之间互称为兄弟节点。我们把没有父节点的节点叫作根节点,也就是图中的节点 E。我们把没有子节点的节点叫作叶子节点或者叶节点,比如图中的 G、H、I、J、K、L 都是叶子节点。

关于“树”,还有三个比较相似的概念:高度(Height)深度(Depth)层(Level)

比如下面

“高度”这个概念,其实就是从下往上度量,比如我们要度量第 10 层楼的高度、第 13 层楼的高度,起点都是地面。所以,树这种数据结构的高度也是一样,从最底层开始计数,并且计数的起点是 0。

“深度”这个概念在生活中是从上往下度量的,比如水中鱼的深度,是从水平面开始度量的。所以,树这种数据结构的深度也是类似的,从根结点开始度量,并且计数起点也是 0。

“层数”跟深度的计算类似,不过,计数起点是 1,也就是说根节点的位于第 1 层。

二叉树(Binary Tree)

二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子节点和右子节点。

编号 2 的二叉树中,叶子节点全都在最底层,除了叶子节点之外,每个节点都有左右两个子节点,这种二叉树就叫作满二叉树。

编号 3 的二叉树中,叶子节点都在最底下两层,最后一层的叶子节点都靠左排列,并且除了最后一层,其他层的节点个数都要达到最大,这种二叉树叫作完全二叉树

要理解完全二叉树定义的由来,我们需要先了解,如何表示(或者存储)一棵二叉树?

链式存储法。每个节点有三个字段,其中一个存储数据,另外两个是指向左右子节点的指针。

顺序存储法。我们把根节点存储在下标 i = 1 的位置,那左子节点存储在下标 2 * i = 2 的位置,右子节点存储在 2 * i + 1 = 3 的位置。以此类推,B 节点的左子节点存储在 2 * i = 2 * 2 = 4 的位置,右子节点存储在 2 * i + 1 = 2 * 2 + 1 = 5 的位置。

如果节点 X 存储在数组中下标为 i 的位置,下标为 2 * i 的位置存储的就是左子节点,下标为 2 * i + 1 的位置存储的就是右子节点。反过来,下标为 i/2 的位置存储就是它的父节点。通过这种方式,我们只要知道根节点存储的位置(一般情况下,为了方便计算子节点,根节点会存储在下标为 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

伪代码

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节点

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