树的概念

树是一种用于描述一对多的数据结构，比如文件目录结构就可以用树来描述。树的定义如下：

树是n(n≥0)个结点的有限集合，n=0时称为空树，在任意一棵非空树中：

注意两点，根结点是唯一的，子树互不相交。

二叉树是一种常用的树，它只有两个子结点，除此外多叉树也可能用到，如果一个集合里包含不止一颗树，则称为森林。

树的存储

树的存储分为顺序存储和链式存储。顺序存储是指通过数组来存储树，分为双亲表示法，孩子表示法，双新孩子表示法，如下：

链式存储使用链表来存储树，分为孩子链表表示法和孩子兄弟表示法，如下：

使用孩子兄弟表示法，长子当左结点，兄弟当右结点。

左结点作为长子，右斜线作为兄弟。

把森林中的每棵树的根当成兄弟结点，先把每个树转换成二叉树，然后再将每棵树的根连接在右斜线上。

右斜线上的每个结点作为一棵树的根，将每棵二叉树还原为树。

第k层最多2^k-1个结点。
k层的二叉树最多2^k-1个结点。
对于任何一棵二叉树，若叶子结点数为n0，度为2的结点数为n2，则n0 = n2 + 1。
满二叉树：每一层都填满的二叉树。
完全二叉树：除最后一层外，每一层都是满的，最后一层节点从左向右出现。
具有n个结点的完全二叉树的深度必为log₂n+1。
将完全二叉树按从上下到、从右到右展开到顺序表中，则编号为i的结点，其左孩子编号必为2i，右孩子编号必为2i+1，其父结点编号必为i/2，应用：
- 一颗完全二叉树有1001个结点，其中叶子节点的个数是多少？
  - 与之最接近的满二叉树为2¹⁰-1 = 1023个节点，也就是这个树有10层，前9层的结点数为2⁹-1 = 511个，最后一层的叶子节点为1001-511 = 490个。
- 一颗完全二叉树第6层有8个叶子，则该完全二叉树最少有几个结点，最多有几个结点？
  - 两种情况，一种是第6层是最后一层，这层不满，对应的结点数为前5层满节点加上第6层的8个叶子。第二种情况是第6层为倒数第二层，这层本身是满的，但最后的8个节点没有子结点，对应的结点数是前6层满节点加上第6层8个叶子节点之前的节点的全部叶子。
二叉树顺序存储：将完全二叉树的的结点按顺序编号，依次存储到顺序表中。