前面讲的都是线性表结构，栈、队列等等。今天讲一种非线性表结构，树。树这种数据结构比线性表的数据结构要复杂得多，内容也比较多，所以我会分四节来讲解。
二叉树有哪几种存储方式？什么样的二叉树适合用数组来存储？
树
关于树，有几个比较常用的概念需要掌握，那就是：根节点、叶子节点、父节点、子节点、兄弟节点，还有节点的高度、深度、层数，以及树的高度。
这里主要来明晰一下高度（Height）、深度（Depth）、层（Level）。
节点的高度 = 该节点到叶子节点的最长路径（边数）
节点的深度 = 根节点到这个节点所经历的边的个数
节点的层数 = 节点的深度 + 1
树的高度 = 根节点的高度
高度和深度按照常识来计数，分别是从下往上、从上往下，从 0 开始计数；
层数规定根节点位于第 1 层，从 1 开始计数。
二叉树
满二叉树：每个节点都有左右两个子节点的树
完全二叉树：除了最后一层，其他层的节点个数达到最大，最后一层的叶子节点都靠左连续排列。
满二叉树是特殊的完全二叉树。
为什么偏偏把最后一层的叶子节点靠左排列的叫完全二叉树呢？靠右不行吗？
要理解完全二叉树定义的由来，我们需要先了解，如何表示（或者存储）一棵二叉树？
两种方法，一种是基于指针或者引用的二叉链式存储法，一种是基于数组的顺序存储法。
二叉链式存储法（常用）
数组顺序存储法
关于数组顺序存储法，总结一下，如果节点 X 存储在数组中下标为 i 的位置，下标为 2 * i 的位置存储的就是左子节点，下标为 2 * i + 1 的位置存储的就是右子节点。反过来，下标为 i/2 的位置存储就是它的父节点。
通过这种方式，我们只要知道根节点存储的位置（一般情况下，为了方便计算子节点，根节点会存储在下标为 1 的位置），这样就可以通过下标计算，把整棵树都串起来。
刚刚举的例子是一棵完全二叉树，所以仅仅“浪费”了一个下标为 0 的存储位置。如果是非完全二叉树，其实会浪费比较多的数组存储空间。
所以，如果某棵二叉树是一棵完全二叉树，那用数组存储无疑是最节省内存的一种方式。因为数组的存储方式并不需要像链式存储法那样要存储额外的左右子节点的指针。这也是为什么完全二叉树会单独拎出来的原因，也是为什么完全二叉树要求最后一层的子节点都靠左的原因。
后面讲堆和堆排序的时候，你会发现堆就是一种完全二叉树，最常用的存储方式就是数组。
二叉树的遍历
如何将所有节点都遍历打印出来呢？经典的方法有三种，前序遍历、中序遍历和后序遍历。其中，前、中、后序，表示的是节点与它的左右子树节点遍历打印的先后顺序。
-
前序遍历是指，对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。
-
中序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。
-
后序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。
二叉树的前、中、后序遍历就是一个递归的过程。
前序遍历的递推公式：
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
有了递推公式，代码写起来就简单多了，这是前序遍历的伪代码。
二叉树遍历的时间复杂度是多少？
可以看出来，每个节点最多会被访问两次，所以遍历操作的时间复杂度，跟节点的个数 n 成正比，也就是说二叉树遍历的时间复杂度是 O(n)。
课后思考
-
给定一组数据，比如 1，3，5，6，9，10。你来算算，可以构建出多少种不同的二叉树？
-
我们讲了三种二叉树的遍历方式，前、中、后序。实际上，还有另外一种遍历方式，也就是按层遍历，你知道如何实现吗？
网友评论