之前我们学过的数据结构都是线性数据结构，而树是我们学习的第一个非线性数据结构。
树
“树”这个数据结构的名字非常形象，如果将它颠倒，它的结构就像是一棵树，下面给出几个树：
树的定义.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的《数据结构与算法之美》专栏的总结，我大量引用了其中的代码和截图，如果想要了解具体内容，可以前往极客时间
网友评论