1 树的常见概念

定义：

树是n(n>=0) 个有限结点组成的一个具有层次关系的集合。每个结点有0个或者多个子结点，没有父结点的结点称为根结点，也就是说，除了根结点外每个结点都有父结点，并且有且只有一个。常见的树种类有二叉树，基本结构如下图：

参考上面的结构，可以很方便的理解树的如下概念：
1.节点的度：一个节点含有的子节点的个数称为该节点的度；

2.树的度：一棵树中，树中结点的最大层次数称为树的深度或高度，注意与节点度的区别；

3.叶节点或终端节点：度为0的节点称为叶节点；如图中的DEFG结点。
4.非终端节点或分支节点：度不为0的节点；
5.双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
6.孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
7.兄弟节点：具有相同父节点的节点互称为兄弟节点：

8.节点的祖先：从根到该节点所经分支上的所有节点：
9.子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
10.森林：由m(m>=0)棵互不相交的树的集合称为森林；
11.无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树；
12.有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树；
13.二叉树：每个节点最多含有两个子树的树称为二叉树；

2 树的性质

性质1：在二叉树的第i层上至多有2^(i-1)个结点(i>0)
性质2：深度为k的二叉树至多有2^k-1个结点(k>0)
性质3：对于任意一棵二叉树，如果其叶结点数为N0,而度数为2的结点总数为N2,则N0=N2+1;
性质4：具有n个结点的完全二叉树的深度必为Iog2(n+1)
性质5：对完全二叉树，若从上至下、从左至右编号，则编号为i的结点
其左孩子编号必为2，
其右孩子编号必为2i+1;其双亲的编号必为i/2(i=1时为根，除外)
满二叉树和完全二叉树的区分：
满二叉树就是如果一棵二叉树只有度为0的节点和度为2的节点，并且度为0的节点在同一层上，则这棵二叉树为满二叉树。

这棵二叉树为满二叉树，也可以说深度为k=4,有2^k-1=15个节点的二叉树。
完全二叉树的定义如下:在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。

前面两棵树的前n-1层都是满的，最后一层所有节点都集中在左侧区域，而且节点之间不能有空隙。最后一个为什么不是？因为有一节点缺了一个左子节点。

3 树的定义与存储方式

定义树的原理与链表的本质是一样的，只不过多了一个指针，如果是二叉树，只要在链表的定义上增加一个指针就可以。

struct TreeNode {
	int val;
  TreeNode *left;
  TreeNode *right;
}

这里本质上就是两个引用，分别指向两个位置。
那二叉树的存储方式又是怎样的呢
二叉树的顺序存储结构就是使用一维数组存储二叉树中的结点，并且结点的存储位置，就是数组的下标索引。
用数组来存储二叉树如何遍历的呢？如果父节点的数组下表是i，那么它的左孩
子就是i2+1，右孩子就是i2+2。但是用链式表示的二叉树，更有利于理解，所以一般我们都是用链式存储二叉树。不过也要了解，用数组依然可以表示二叉树。
使用数组存储的最大不足是可能存在大量的空间浪费。例如上图中如果b分支没有，那么数组中1 3 4位置都要空着，但是整个数组的大小仍然是7，因此很少使用数组来存储树。

4 树的遍历方式

二叉树的遍历方式有层次遍历和深度优先遍历两种：

• 深度优先遍历：先往深走，遇到叶结点再往回走。
• 广度优先遍历：一层一层的去遍历，一层访问完再访问下一层。

这两种遍历方式不仅仅是二叉树，N叉树也有这两种方式的，图结构也有，只不过更习惯叫广度优先和深度优先，本质是一回事。深度优先又有前中后序三种，这里容易分不清这三个顺序，问题就在不清楚这里前中后是相对谁来说的。记住一点：前指的是中间的父节点在遍历中的顺序，只要记住前中后序指的就是中间节点的位置就可以了。
看如下中间节点的顺序，就可以发现，访问中间节点的顺序就是所谓的遍历方式
前序遍历：中左右
中序遍历：左中右
后序遍历：左右中
如图对应的各种遍历方式为：

5 通过序列构造二叉树

5.1 通过中序和后序序列恢复二叉树

已知二叉树的中序和后序如下所示，如何通过给出的序列来恢复原始二叉树？
中序：3 4 8 6 7 5 2 1 10 9 11 15 13 14 12
后序：8 7 6 5 4 3 2 10 15 14 13 12 11 9 1

• 第一轮：

已知后序最后一个访问的是根结点，所以得到根节点就是1。
中序遍历的特点是根结点的左子树的元素都在根结点的左侧，右子树的元素都在根结点的右侧，所以通过中序序列可以进行以下结构划分

上面后序序列第一个括号里的都是左子对的元素，第二个括号一定都是右子树的元素。
那这里怎么知道两个括号从哪里分开呢？是参照中序的两个数组划分的。可以看到后序中2之前的元素都在中序第一个数组中，10之后的所有元素就在第二个数组中，所以从2和10之间划分。
由此，画图可以直观表示此时树的结构为：

• 第二轮：

先看两个序列中的第一个数组：
中序：3 4 8 6 7 5 2
后序：8 7 6 5 4 3 2
根据上面的结论划分：根结点是2，根据2在中序的位置划分

此时树的结构为：

• 第三轮：

对 8 7 6 5 4 3 继续划分：

树结构为：

• 第四轮：

对 8 7 6 5 4 继续划分：

树结构为：

• 第五轮：

对 8 7 6 5 继续划分：

树结构为：

• 第六轮：

对 8 7 6 继续划分：

树结构为：

到这一步，左边的序列已复原。同理，对右边的序列10 9 11 15 13 14 12 也依次进行划分，可得最后的树结构为：

5.2通过前序和中序序列恢复二叉树

通过前序和中序也能恢复原始序列的，唯一的不同是前序序列的第一个是根
节点，中序的处理也是上面一样的过程；

注意：只通过前序和后序不能恢复二叉树。
因为通过前序和后序可以知道根结点，但是却无法对左子树和右子树的结点进行区分，所以无法恢复。