一、树的结构及概念
1.树的概念
树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
这是一个简单的树（画图板不太会用，我下去努力学）
每一颗数都是由根+多个子树构成的，没有子树是空树
树与非树？
1.子树是不相交的（树中没有环）
2.除了根结点外，每个节点有且仅有一个父节点。
树的必备知识
（1）结点的度：一个节点含有的子树的个数称为该节点的度；如上图：A的为6，即B、C、D、E、F、G。
（2）叶结点：度为0的节点称为叶结点；如上图：B、C、H、I…等为叶结点。
（3）双亲结点或父结点：若一个节点含有子结点，则这个结点称为其子结点的父结点；如上图：A是B的父结点。
（4）孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点。
（5）兄弟结点：具有相同父结点的结点互称为兄弟结点。
（6）树的度：一棵树中，最大的节点的度称为树的度。
（7）结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推。
（8）树的高度或深度：树中结点的最大层次
（9）节点的祖先：从根到某一结点所经分支上的所有结点。
（10）子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙。
（11）森林：多棵互不相交的树的集合称为森林。
树的表示
树并没有规定他有多少个孩子。
struct TreeNode
{
int val;
struct TreeNode* child1;
struct TreeNode* child2;
struct TreeNode* child3;
...
};
左孩子右兄弟表示法
这个方法的优点是，无论树中一个节点有多少个孩子，都可以表示，因为我只指向第一个孩子，剩下的孩子，让孩子之间用兄弟指针串起来。
还有一种双亲表示法，每个值存双亲的下标，不实用。
二、二叉树的概念及结构
概念：一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。
二叉树的特点：
- 每个结点最多有两棵子树，即二叉树不存在度大于2的结点。
- 二叉树的子树有左右之分，其子树的次序不能颠倒。
特殊的二叉树
- 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。
- 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
如果一个满二叉树有N个节点，那么他的高数是多少
2^k-1=N
k=log2n+1
完全二叉树的特点
前k-1层都是满的，最后一层可以不满，但从左到右都是连续的
二叉树的性质
- 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个结点.
- 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h- 1.
- 对任何一棵二叉树, 如果度为0其叶结点个数为 n0, 度为2的分支结点个数为 n2,则有n0＝n2＋1
- 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=Log2(n+1). (ps：Log2(n+1)是log以2为底，n+1为对数)
- 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：
- 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
- 若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子
- 若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子
三、堆–完全二叉树
堆分为大根堆和小根堆
小根堆：父亲小于等于孩子
大根堆：父亲大于等于孩子
堆能总结出一个公式：
假设父亲的下标是parent
leftchild=parent2+1
rightchild=parent2+2
特点：左子树和右子树恰好是小堆，但整体不是小堆。
向下调整算法方法：
1.选出左右孩子中小的那一个
2.小的这个孩子跟父亲比
a、如果小的孩子比父亲小，则跟父亲交换，并且把原来孩子的位置当成父亲继续往下调整。
b、如果小的孩子比父亲大，则不需要处理，调整完成，整个树已经是小堆。
排升序，建大堆还是小堆呢？ 大堆
升序？为什么不能建小堆呢？
首先建堆选出一个最小的数，剩下的数父子关系全乱了，效率太低。
