树 - 树和二叉树基础

之前我们学过的数据结构都是线性数据结构，而树是我们学习的第一个非线性数据结构。

树

“树”这个数据结构的名字非常形象，如果将它颠倒，它的结构就像是一棵树，下面给出几个树： 树的定义.jpg

可以发现，树的子结点（如果没有标注，你可以将“结点” 和“节点”理解为同一个东西）只有一个父结点，这也许就是树区别于图的最重要的特征。

树中的相关概念

树有着上下级结构，这让我们需要一些额外的概念描述他们之间的关系（由于这个介绍的资料随处可见，在这里就简要介绍了，如果想要了解详细，可以自行百度，（狗头保命.jpg））

节点：

树-结点.jpg

• 父节点：A 节点是 B 节点的父节点。
• 子节点：B 节点是 A 节点的子节点。
• 兄弟节点：B、C、D 拥有同一个父节点，所以他们之间称为兄弟节点。
• 根节点：是指没有父节点的节点，E 节点是根节点。
• 叶子节点：没有子节点的结点，G、H、I、J、K、L都是叶子节点。

度：

树-度的概念.jpg
可能你没太明白，下面给个例子： 树-度的举例.jpg

二叉树

顾名思义，二叉树只有两个“叉”，也就是两个子节点，分别是 左子节点 和 右子节点。一般来说，一个节点是左子节点还是右子节点，会有特殊的含义，至于是什么含义，这是由数据结构的定义决定的。
当然，一个节点不一定有两个节点：

二叉树.jpg
在这里，编号为 2 的二叉树称为满二叉树，它的叶子节点全都在最底层，除了叶子节点，所有的节点都有两个节点。
标号为 3 的二叉树称为完全二叉树，你可以将它看成满二叉树的一般情况：当完全二叉树的最后一层将叶子节点填充完全，就是满二叉树。 为了加深理解，这里有识别完全二叉树的例子： 二叉树-完全二叉树.jpg

你可能会疑惑，满二叉树是比较特殊的二叉树，这可以理解，但是完全二叉树有什么意义呢？
要回答这个问题，我们要了解二叉树的存储方式。

二叉树的存储

和你猜的一样，二叉树有两种存储方式：链式存储法 和 顺序存储法

链式存储：

二叉树-链式存储.jpg

链式存储比较简单和直观：一个节点有三个部分：data 部分存储数据，left 部分存储左子节点的指针，right 部分存储右子节点的指针。
这种方法比较常见，也是最常用的春初方法。

顺序存储：

二叉树-顺序存储.jpg

顺序存储使用数组实现，你会发现，一个节点被存储在 i 的位置，它的左子节点就在 2 * i 的位置，右子节点的位置为 2 * i + 1 。你可以通过计算，把整棵树都串起来。

不过，上面的例子中是一课完全二叉树，如果是非完全二叉树，就会浪费较多的存储空间：

二叉树-顺序存储-非完全二叉树.jpg
所以，你可以这么认为：完全二叉树比较适合使用数组存储，内存空间浪费很小。这也是完全二叉树被单拿出来的原因。
在之后我们会学习到堆和堆排序，你会发现堆就是完全二叉树。

二叉树的遍历

二叉树的遍历是非常重要的操作，也是非常常见的面试题，二叉树遍历的经典方法有三种：前序遍历、中序遍历、后续遍历：

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

• 后序遍历：先打印左子树，再打印右子树，最后打印本身。

  
  二叉树的遍历.jpg

这种遍历都可以使用递归来实现：

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

二叉树遍历的时间复杂度

从之前的遍历顺序图可以看出，每个节点最多被访问两次，所以遍历的复杂度和节点个数 n 成正比，也就是说二叉树遍历的时间复杂度为O(n)。

---

以上就是树和二叉树的基础内容

注：本文章的主要内容来自我对极客时间app的《数据结构与算法之美》专栏的总结，我大量引用了其中的代码和截图，如果想要了解具体内容，可以前往极客时间