数据结构与算法⑩(第四章_上)树和二叉树和堆的概念及结构（上）：https://developer.aliyun.com/article/1513412
2.3完全二叉树
定义：对于深度为h的，有 n个结点的二叉树，当且仅当其每一个结点都与深度为h的满二叉树中编号从 1 至 n的结点一一对应时称之为完全二叉树。
前h-1层是满的，最后一层不满，但是最后一层从左到右是连续的。
完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。
所以，满二叉树是一种特殊的完全二叉树（每一层节点均为2）。
常识：
① 完全二叉树中，度为 1 的最多只有 1 个。
② 高度为 h的完全二叉树节点范围是
（如果不是满二叉树，最小个数就是倒数第一层（满二叉树）的高度算出的节点数+1（至少有一个），是满二叉树最大个数就是2^h - 1）
2.4二叉树的性质
四点规则：
① 若规定根节点的层数为 1 ，则一颗非空二叉树的第i层上最多有2^(i-1)个节点。
② 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h- 1.
（此时为满二叉树）（等比数列公式）
③ 任何一棵二叉树, 如果叶结点（度为0）个数为 n0, 度为2的分支结点个数为 n2,则有n0＝n2＋1
（从只有一个结点（空树度也是0），逐个增加，就可以找到规律）
④ 若规定根节点的层数为1，具有N个结点的满二叉树的深度，h=log(N+1)（log以2为底）。
2.4.1二叉树性质相关选择题：
1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）
A. 不存在这样的二叉树
B. 200
C. 198
D. 199
2.在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）
A. n
B. n+1
C. n-1
D. n/2
3.一棵完全二叉树的节点数位为531个，那么这棵树的高度为（ ）
A. 11
B. 10
C. 8
D. 12
4. 一个具有767个节点的完全二叉树，其叶子节点个数为（）
A. 383
B. 384
C. 385
D. 386
答案解析：
1. n0＝n2＋1
2.假设叶子节点（度为0）有X个 则度为2的节点有x-1个，完全二叉树中度为1的节点为0个或1个
所以X+(X-1)+(0或1)=2n,所以叶子结点x个数为n
3.具有N个结点的满二叉树的深度，h=log(N+1)（log以2为底）。
高度为 h的完全二叉树节点范围是
2的9次方= 512,2的10次方 - 1 = 1023 在范围内
4.同2 假设叶子节点有X个 则度为0的节点有x-1个，完全二叉树中度为1的节点为0个或1个
X+(X-1)+(0或1)=767 , x=383
1.B
2.A
3.B
4.A
2.5二叉树的顺序存储：
顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，关于堆后面的章节会专门讲解。
二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。
完全二叉树的顺序存储中
若父亲下标是i，则左孩子下标是2 * i + 1 右孩子下标是2 * i + 2
若孩子下标是i，则父亲下标是（ i - 1）/2
像上面左图中C下标为2，左孩子F下标就为2 * 2 + 1=5，右孩子G下标为2 * 2 + 2=6，
D下标为3，E下标为4 则父亲B下标为（3 -1）/ 2 = 1 或者（4 -1）/ 2 = 1。
2.6二叉树的链式存储：
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。
通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，
左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。
链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，
后面学到高阶数据结构如红黑树等会用到三叉链。
// 二叉链 struct BinaryTreeNode { struct BinTreeNode* pLeft; // 指向当前节点左孩子 struct BinTreeNode* pRight; // 指向当前节点右孩子 BTDataType _data; // 当前节点值域 } // 三叉链 struct BinaryTreeNode { struct BinTreeNode* pParent; // 指向当前节点的双亲 struct BinTreeNode* pLeft; // 指向当前节点左孩子 struct BinTreeNode* pRight; // 指向当前节点右孩子 BTDataType _data; // 当前节点值域 }
3.堆的概念及结构
【百度百科】堆（Heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做 一棵完全二叉树的数组对象。
完全二叉树的性质就是堆的性质，堆是完全二叉树的顺序结构存储。
① 堆总是一棵完全二叉树。
② 堆中的某个节点的值总是不大于或不小于其父节点的值。
堆的物理结构是数组，逻辑结构则是二叉树。
堆有多种，其中典型的是：大堆 和 小堆。
3.1小堆：
任意一个节点的两个子节点都比自己的值大或相等，也就是根最小，整个二叉树从上到下递增。
即父亲位，比孩子位，要小；
3.2大堆：
任意一个节点的两个子节点都比自己的值小或相等，也就是根最大，整个二叉树从上到下递减。
即父亲位，比孩子位，要大。
常考选择题：
解析：
题目只说明是堆，大堆小堆都可以。
一个个分析后发现除了A都不是
A差不多是这样：
100
60 70
50 32 65
3.3堆的作用
① 八大排序算法之一：堆排序
② 解决TopK问题，在N个数中找出最大的前K个或找出最小的K个......
4.树的笔试选择题
1.在用树表示的目录结构中，从根目录到任何数据文件，有（ ）通道
A.唯一一条
B.二条
C.三条
D.不一定
2.在一颗度为3的树中，度为3的结点有2个，度为2的结点有1个，度为1的结点有2个，则叶子结点有（ ）个
A.4
B.5
C.6
D.7
3.一颗拥有1000个结点的树度为4，则它的最小深度是（ ）
A.5
B.6
C.7
D.8
4.下列关于二叉树的叙述错误的是（ ）
A.二叉树指的是深度为 2 的树
B.一个 n 个结点的二叉树将拥有 n-1 条边
C.一颗深度为 h 的满二叉树拥有 2^h-1 个结点（根结点深度为1）
D.二叉树有二叉链和三叉链两种表示方式
5.一颗完全二叉树有1001个结点，其叶子结点的个数是（ ）
A.251
B.500
C.501
D.不能确定
6.在一颗完全二叉树中，某一个结点没有其左孩子，则该结点一定（ ）
A.是根结点
B.是叶结点
C.是分支结点
D.在倒数第二层
7.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为（ ）个
A.11
B.12
C.13
D.14
8.下列关于树的叙述正确的是（ ）
A.树中可以有环
B.树的度是指所有结点中度最小的结点的度
C.树的深度指的是结点数最多的那一层的深度
D.树的根结点是所有结点的祖先结点
9.有n个元素的完全二叉树的深度是（ ）
A.nlogn
B.nlogn+1
C.logn
D.logn+1
答案及解析
（可以开两个网页对着题目看）
1.答案：A
解析：
树的特点是不相交，所以不可能有多个路径同时到达一个点。
2.答案：C
解析：
设度为i的节点个数为ni, 该树总共有n个节点,则n=n0+n1+n2+n3.
有n个节点的树的总边数为n-1条.
根据度的定义,总边数与度之间的关系为：n-1=0*n0+1*n1+2*n2+3*n3.
联立两个方程求解,可以得到n0 = n2 + 2n3 + 1, n0=6
3.答案：B
解析：
如果这棵树每一层都是满的，则它的深度最小，假设它为一个四叉树，高度为h，则这个数的节点个数为(4^h - 1) / 3，当h = 5, 最大节点数为341， 当h = 6, 最大节点数为1365，所以最小深度应该为6。
4.答案：A
解析：
A错误: 二叉树指最大孩子个数为2，即树的度为二的树。深度描述的为树的层数。
B正确: 对于任意的树都满足：边的条数比节点个数少1，因为每个节点都有双亲，但是根节点没有
C正确: 正确，参加二叉树性质
D正确: 二叉链一般指孩子表示法，三叉连指孩子双亲表示法，这两种方式是二叉树最常见的表示方式，虽然还有孩子兄弟表示法，该中表示方式本质也是二叉链
5.答案：C
解析：
该题需要用到二叉树性质：在任意二叉树中，度为0的节点都比度为2的节点多1个，即 n0 = n2 + 1
另外，在完全二叉树中，如果节点总个数为奇数，则没有度为1的节点，如果节点总个数为偶数，只有一个度为1的节点
因此：n0 + n1 + n2 = 1001 节点总数为奇数，没有度为1的节点
n0 + 0 + n2 = 2*n0-1 = 1001 n0 = 501
6.答案：B
解析：
完全二叉树中如果一个节点没有左孩子，则一定没有右孩子，必定为一个叶子节点，最后一层一定为叶子节点，但是倒数第二层也可能存在叶子节点。
7.答案：C
解析：
设Ni表示度为i的节点个数，则节点总数 N = N0 + N1 + N2
节点个数于节点边的关系： N个节点的树有N-1个边
边与度的关系：N - 1 = N1 + 2 * N2
故：N0 + N1 + N2 - 1 = N1 + 2 * N2
因此，得：N0 = N2 + 1
回到原题，N0 = 3，N1 = 8，可得N2 = 2。
因此答案是 3 + 8 + 2 = 13。
8.答案：D
解析：
A: 树中的节点不能相交
B: 树的度为所有节点中度最大的节点的度
C: 树的深度为根节点到叶子节点的最大深度
9.答案：D
解析：
参考完全二叉树的特性，高度h = log(n)向上取整 注意：底数是2
