树形结构的应用场合非常多，比如计算机某块硬盘下的目录结构、一个公司的组织架构划分、一个家族的族谱等等。
在计算机领域，树形结构也被广泛应用，比如编译器、数据库里都会用到，也因此，树形结构非常重要。而在众多树形结构中，最常用的一种，就是二叉树了。
在日常生活中，树是一种随处可见的植物，它由树根、树枝、树叶这些主要结构组成。而 “树形结构”，就是基于日常生活中的树而得名的一种非线性数据结构。
什么是 “非线性的数据结构” ？想象一下，一根树枝可以分叉出很多树枝、树叶，我们也可以将 “非线性的数据结构” 理解成一种一对多的关系，而不是像一条线一样，按顺序排列的一对一关系。
在绘制树这种数据结构时，人们往往会从上向下绘制，也就是将树根绘制在最上面，下图就是一棵树：
在这幅图中，所有标有字母的圆圈就是树的节点。树（Tree）是 n（n≥0）个节点的有限集。这里有了一个限定范围，n≥0。你可以尝试想象几种不同的情况，比如 n=0，n=1，以及 n>1 这三种。
当 n=0 时，树就是一棵空树。
如果树为非空，那么就会有两种情况：
子树的概念比较难理解，我们举个例子。下图中：
B、D、E、F、H、I、J、K，也就是左半边，构成了以 B 为根节点的 子树。
根据树的定义：有限集 T1 由 B、D、E、F、H、I、J、K 构成。C、G，也就是右半边，构成了以 C 为根节点的子树。根据树的定义：有限集 T2 由 C、G 构成。
子树，又可以看成是由更多更小的、互不相交的子树构成，所以我们也把树称为是一种递归定义的数据结构。如果树中节点的各子树从左到右是有次序的、不能互换的，则称该树为有序树，否则就叫做无序树。
注意，如果子树存在，那么子树之间不能相交，比如下图所列的情形就不是一棵树，节点 E 和 F 之间以及节点 G 和 K 之间都不应该有连线：
树的节点包含一个数据元素以及若干指向其子树的分支（分支也可以称为指针或索引），这里会经常用到一些概念。这些概念不需要死记硬背，只需要理解就好，将来忘记了可以随时来回顾。（以下面这幅图为例）
树的结构多种多样，对树的操作也各不相同，但最常用是二叉树，因为大部分树都可以转换为二叉树。那什么是二叉树呢？
二叉树的特点是每个节点 最多 有两棵子树（左子树 和 右子树），这意味着每个节点的度都不大于 2。它的两棵子树有左右之分。想象一下，人的脚是分左右的，右脚不能穿左侧的鞋，和二叉树两棵子树的左右之分是一个道理。另外，次序也是不能随意颠倒的，这表明二叉树是一棵有序树。
这里，我们给二叉树下一个明确的定义：二叉树是 n（n≥0）个节点的有限集合，该集合或者为空集（即 n=0，叫做空二叉树），或者由一个根节点和两个互不相交的该根节点的左子树和右子树构成，左子树和右子树又分别是一棵二叉树。
除空二叉树外，下图列出了其他四种形态的二叉树，分别是只有根节点的二叉树、只有左子树的二叉树、只有右子树的二叉树、既有左子树又有右子树的二叉树。
你可以思考一下，有三个节点的二叉树会有几种形态呢？答案是有 5 种形态，如下图所示：
二叉树有一些特殊的形态在后面会经常被提到或者用到，这里先认识一下满二叉树、完全二叉树以及斜树。
如下图所示，就是一棵满二叉树：
我们先说下满二叉树有什么特点：
可以看到，满二叉树看上去是很平衡的。在同样高度的二叉树当中，满二叉树一定是节点个数最多，叶子数最多的二叉树。
那要怎么去定义 “满二叉树” 呢？
观察一下，图中，第一层有 1 个节点，第二层有 2 个节点，第三层有 4 个节点，第四层有 8 个节点，所以总共的节点数为 1+2+4+8=15 个，即 2 4 − 1 2^4-1 24−1 个。
由此，我们可以给出满二叉树的定义：满二叉树是指一棵高度为 h，且含有 2 h − 1 2^h-1 2h−1 个节点的二叉树。
最后，我们说一下编号的特点。
按照图中的顺序给每个满二叉树的节点从上到下从左到右进行编号，比如图中的 1 到 15，不难发现，编号为 i 的分支节点，它的左孩子的编号为 2i，右孩子的编号为 2i+1。如果节点 i 存在父节点，则其父节点的编号是 i/2 的结果，如果没整除，那么去掉小数部分即可。
完全二叉树理解起来有一点难度。下图就是一棵完全二叉树：
想一想，完全二叉树有什么特点呢？
可以看到，满二叉树一定是一棵完全二叉树，但完全二叉树不一定是满二叉树。
现在，我们可以借助满二叉树的概念，给出完全二叉树的定义：一棵高度为 h 的完全二叉树，当且仅当其每个节点都与高度为 h 的满二叉树中编号为 1~n 的节点一 一对应时，称为完全二叉树。
按照图中的顺序，我们给每个完全二叉树的节点从上到下从左到右进行编号，不难发现，编号为 i 的分支节点，其左孩子的编号为 2i，右孩子的编号为 2i+1。如果节点 i 存在父节点，则其父节点的编号是 i/2 的结果，如果没整除则去掉小数部分。
按照图中的顺序给每个完全二叉树的节点从上到下从左到右进行编号，随便拿出一个节点比如编号为 9 的节点，会发现该节点是编号为 4 的节点的右子树。
此时再观察下图中的满二叉树，会发现，编号为 9 的节点与上图中编号为 9 的节点位置完全相同，并且同样是编号为 4 的节点的右子树。
下图所示的几棵二叉树就都不是完全二叉树：
图中第一棵树的节点 5 缺少左子树（编号 10），第二棵树的节点 3 缺少两棵子树（编号 6、7），第三棵树的节点 5 缺少两棵子树（编号 10、11）。
所以，如何判断是否是完全二叉树，就可以按照下面的步骤去做：
所有节点都只有左子树的二叉树叫左斜树。所有节点都只有右子树的二叉树叫右斜树。这两种树统称斜树。
斜树的特点是每一层只有一个节点，节点个数与二叉树深度相同。这种树看起来更像线性表。
在对二叉树进行编码过程中，尤其是涉及开辟多少空间保存数据的时候，往往会用到二叉树的性质。（五星级非常重要）
性质一：在二叉树的第 i 层上，最多有 2 i − 1 2^i−1 2i−1 个节点（ i ≥ 1 i≥1 i≥1 ）
满二叉树可以认为是第 i 层上节点最多的二叉树了。回忆一下满二叉树的定义：满二叉树是指一棵高度为 h，且含有 2 h − 1 2^h-1 2h−1 个节点的二叉树。在下图中，第一层有 1 个节点，第二层有 2 个节点，第三层有 4 个节点，第四层有 8 个节点，满足二叉树的性质一。
性质二：高度为 k 的二叉树至多有 2 k − 1 2^k-1 2k−1 个节点（ k ≥ 1 k≥1 k≥1 ）
满二叉树可以认为是有最多个节点的二叉树了。在下图中，满二叉树的高度为 4 层，第一层有 1 个节点，第二层有 2 个节点，第三层有 4 个节点，第四层有 8 个节点，总共的节点数为 1+2+4+8=15 个，即 2 4 − 1 2^4-1 24−1 个节点，满足二叉树的性质二。
性质三：二叉树节点的总数量等于节点的总度数 +1
观察一棵二叉树不难发现，除根节点外，每个节点头上都有一个分支（每个节点都有一个父节点），那么一棵二叉树节点总数量其实就是这些分支的总数量 +1，之所以 +1，是因为根节点头上没有分支。一棵二叉树节点的总度数，其实就是每个节点头上分支的总数量，所以得出性质三的结论：二叉树节点的总数量 = 节点的总度数 + 1。
性质四：对任何一棵二叉树，如果其叶节点数量为 n 0 n0 n0，度为 2 的节点数量为 n 2 n2 n2，则叶节点的数量比有两棵子树的节点数量多一个，即： n 0 = n 2 + 1 n0=n2+1 n0=n2+1。
这里我们可以来证明一下，如下图所示：
观察上面的完全二叉树，除了叶节点（度为 0），其他的节点度数要么为 1 ，要么为 2，如果假设度为 1 的节点数量是 n1，那么该二叉树的节点总数量 n = n 0 + n 1 + n 2 n = n0 + n1 + n2 n=n0+n1+n2。
再算一算节点的总度数，节点的总度数应该等于 【度为 2 的节点数量 * 2 + 度为 1 的节点数量 * 1】，因此，节点的总度数 = 2 n 2 + n 1 2n2 + n1 2n2+n1。
再根据性质三，节点的总数量 = 节点的总度数 + 1，就有：节点总数量 n = 2 n 2 + n 1 + 1 n = 2n2 + n1+ 1 n=2n2+n1+1。
结合刚才的节点总数量式子，可以得到： n 0 + n 1 + n 2 = 2 n 2 + n 1 + 1 n0 + n1 + n2 = 2n2 + n1+ 1 n0+n1+n2=2n2+n1+1。
两边同时减少一个 n 1 n1 n1 和一个 n 2 n2 n2，不难得到： n 0 = n 2 + 1 n0 = n2+ 1 n0=n2+1，得出了性质四的结论。
试想一下，如果有一个完全二叉树，知道了其节点总数 n n n，那么如何求出 n 0 n0 n0（叶节点数量）、 n 1 n1 n1（度为 1 的节点数量）、 n 2 n2 n2（度为 2 的节点数量）的值呢？
首先，完全二叉树最多只有一个度为 1 的节点，即 n 1 = 0 n1= 0 n1=0 或者 n 1 = 1 n1= 1 n1=1。
其次，根据前面的公式 n = 2 n 2 + n 1 + 1 n = 2n2 + n1+ 1 n=2n2+n1+1。该公式中的 2 n 2 + 1 2n2+ 1 2n2+1 的结果肯定是奇数（不能被 2 整除的整数）。
那么，如果该完全二叉树节点总数是偶数（能够被 2 所整除的整数）个，那么 n 1 n1 n1 必定是奇数也就是值 1。如果该完全二叉树节点总数是奇数，那么 n 1 n1 n1 必定是偶数也就是值 0。
最后， n n n 值已知， n 1 n1 n1 值上步已推出，根据公式 n = 2 n 2 + n 1 + 1 n = 2n2 + n1 + 1 n=2n2+n1+1， n 2 n2 n2 值就可以求得。再根据性质 4 的 n 0 = n 2 + 1 n0= n2+ 1 n0=n2+1， n 0 n0 n0 的值就可以求得。
性质五：具有 n（ n > 0 ）个节点的完全二叉树的高度为 ⌈ l o g 2 ( n + 1 ) ⌉ ⌈ log_2^{(n+1)} ⌉ ⌈log2(n+1)⌉ 或者 ⌊ l o g 2 n ⌋ + 1 ⌊log_2^n ⌋ +1 ⌊log2n⌋+1 。
这里要注意：第一，符号 ⌈ x ⌉ ⌈ x ⌉ ⌈x⌉ 表示向上取整，也就是比 x 大的最小整数。如果 x 本身是整数，那么 ⌈ x ⌉ ⌈ x ⌉ ⌈x⌉ 就等于本身。
第二，符号 ⌊ x ⌋ ⌊ x ⌋ ⌊x⌋ 表示向下取整，也就是比 x 小的最大整数。如果 x 本身是整数，那么 ⌊ x ⌋ ⌊ x ⌋ ⌊x⌋ 就等于本身。
我们先来看一看第一个式子是如何推导的：
再看一看第二个式子是如何推导的：
所以，不妨扩展一下性质五：一个完全二叉树的第 k 的节点的高度为 ⌈ l o g 2 ( k + 1 ) ⌉ ⌈log_2^{(k+1)}⌉ ⌈log2(k+1)⌉ 或者 ⌊ l o g 2 k ⌋ + 1 ⌊log_2^k ⌋ +1 ⌊log2k⌋+1。
性质六：如果对一棵有 n 个节点的完全二叉树的节点按层从 1 开始编号（从上到下从左到右编号，如图所示）
则对任意节点 i i i（ 1 ≤ i ≤ n 1≤i≤n 1≤i≤n ），有：
这篇文章描述了树形结构，也给出了许多和它相关的基本概念，其中比较重要的概念是树根、子树、节点的度，叶节点、子节点、父节点、兄弟节点、树的高度这几个部分。
其次，引入了二叉树的概念。可以说，二叉树在树形结构中最常用，主要重点放在了认识各种形态的二叉树上，比如理解满二叉树、完全二叉树、斜树的概念。
最后，则是二叉树性质的学习。也许你会觉得这些性质离实际应用太过遥远，但其实它对于后面编写程序时决定内存空间分配多少、二叉树的高度和节点数量如何计算以及如何寻找某个节点的父或子节点等都具有重要的指导意义，这一点在后续编写代码时你会越来越清楚。
