二叉树和堆概念
二叉树概念
一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树
的二叉树组成。
二叉树的特点：
- 每个结点最多有两棵子树，即二叉树不存在度大于2的结点。
- 二叉树的子树有左右之分，其子树的次序不能颠倒。
上述都是二叉树。
特殊的二叉树：
满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。
满二叉树总节点个数：
已知满二叉树有N个节点，那么它的高度是多少？
2^k-1 = N，求K即可。 层数是从1开始数的。
完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
即：K层的树，前K-1层都是满的，只有K层不满，但最后一层是需要从左到右连续的。
已知完全二叉树有N个节点，那么它的高度是多少？
2^k-X = N，求K即可。 层数是从1开始数的。 X为最后一层的节点个数。
对于满二叉树和完全二叉树，他们的高度都可看作为 log(N)，N为节点个数。
二叉树的性质
-
若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个结点.
-
若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h- 1.
-
对任何一棵二叉树, 如果度为0（叶子节点）其叶结点个数为 n0, 度为2（有两个分支的节点）的分支结点个数为 n2,则有n0＝n2＋1。即：度为0的节点比度为2节点的永远多一个。如下图：黑度为0的节点红度为2的节点
-
若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=Log2(n+1). (ps：Log2(n+1)是log以2为
底，n+1为对数) .
度为0的节点比度为2节点的永远多一个，所以200个度为0的节点。 B
假设度为0的节点有a0个，度为1的节点有a1，度为2的节点有a2个，所以2n = a0+a1+a2。a2 = a0+1,
2n = a0 + a1 + a0-1 = 2a0 -1 + a1。对于完全二叉树，度为1的有0个或者最多一个节点。如果a1=0，a0就是一个小数的结果，不存在这样的节点。所以，a1=1，所以叶子节点为n。
满二叉树的节点总数是(2^k) -1。
2^9 -1 = 511。满二叉树9层就有511个节点了。
2^10 = 1024 k=10。 所以K至少大于9层，为10层。
假设度为0的节点有a0个，度为1的节点有a1，度为2的节点有a2个，767 = a0 + a1 + a2 = 2a0 + a1 - 1，如果a1 = 1,则不匹配左边，所以a1 = 0。所以 a0 = 768/2 = 384。
堆 — 完全二叉树
堆的物理结构（内存中如何存）：
堆的逻辑结构（想象到的结构）：
堆分为两种，大根堆和小根堆：
小根堆：父亲小于孩子。
大根堆：父亲大于孩子的值。
假设父亲的下标是parent，则左孩子的下标是 leftc = 2parent + 1，右孩子的下标是 rightc = 2parent + 2。
选A，因为只有A满足大根堆。其他不满足大小根堆。