接上节内容
目录
3.3 堆的实现
3.2.1 堆向下调整算法
3.2.2大堆的创建
3.4 堆的应用
3.4.1 堆排序
3.4.2 TOP-K问题
编辑
二叉树的性质
练习
4.二叉树链式结构的实现
4.1 前置说明
4.2二叉树的遍历
4.2.1 前序、中序以及后序遍历
4.3 节点个数以及高度等
4.3.1二叉树节点个数
4.3.2二叉树叶子节点个数
4.3.3二叉树第k层节点个数
4.4练习
完全二叉树/满二叉树 的存储方式为数组存储，而 非完全二叉树/满二叉树 如果使用数组存储会有许多空位，造成空间的浪费。
完全二叉树/满二叉树 节点的下标之间的关系：
leftchild = parent *2+1
rightchild = parent *2+2
parent = (child-1)/2
大堆：任何父亲>=孩子
小堆：任何父亲<=孩子
孩子之间没有关系
小堆的插入：
在数组上尾插,再判断与所有祖先节点的大小，刚好大于父亲节点，无需改变。
在数组上尾插，发现小于父亲节点，就要找到父亲节点并与它交换位置（数组中和逻辑结构中均交换）
小于哪一个祖先节点就当它的父节点，其余子孙节点依次往下移。
3.3 堆的实现
3.2.1 堆向下调整算法
现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整 成一个 小堆 。向下调整算法有一个 前提：左右子树必须是一个小堆，才能调整。int array [] = { 27 , 15 , 19 , 18 , 28 , 34 , 65 , 49 , 25 , 37 };
父节点不断向下遍历，找到最小的子节点与其交换值，直到叶节点。
//数据向下调整（找较小的孩子往上推）
void AdjustDown(HPDataType* a,int n, int parent)
{
//假设较小孩子为左孩子
int child = parent * 2 + 1;
while (child<n)
{
//如果右孩子更小
//child+1必须小于n，否则当child=n-1,child+1就越界
if (child+1<n&&a[child + 1] < a[child])
{
child++;
}
if (a[child] < a[parent])
{
//较小的子节点向上挪
Swap(&a[child], &a[parent]);
//父节点向下移动继续判断
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}3.2.2大堆的创建
下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个大堆，现在我们通过算法，把它构建成一个大堆。如果用向下调整法，要求左右子树都是大堆，但可以观察到根节点左右子树都不是大堆，我们怎么调整呢？叶节点只有一个值，我们可以随意把它看成是一个大堆或者小堆，因此无需调整， 这里我们从 倒数的第一个非叶节点的子树 开始往 根节点 向下调整，一直调整到根节点的树，就可以调整成堆。
//向下调整建堆
for (int i = (n - 1-1) / 2; i >= 0; i--)
{
//从最后一个父节点开始往第一个节点向下调整
AdjustDown(a, n, i);
}3.4 堆的应用
3.4.1 堆排序
堆排序即利用堆的思想来进行排序，总共分为两个步骤：1. 建堆升序：建大堆堆顶根最后一个位置交换，最大的值就排好了剩下的数据依次向下调整，依次选出次大的，代价为 logN.降序：建小堆2. 利用堆删除思想来进行排序建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。
// 排升序（建大堆）
void HeapSort(int* a, int n)
{
向上调整建堆
// //O(N*logN)
//for (int i = 1; i < n; i++)
//{
// AdjustUp(a, i);
//}
//向下调整建堆
// //O(N)(效率更高）
for (int i = (n - 1-1) / 2; i >= 0; i--)
{
//从最后一个父节点开始往第一个节点向下调整
AdjustDown(a, n, i);
}
int end = n - 1;
while (end > 0)
{
//交换最最大值到堆尾
Swap(&a[0], &a[end]);
//小的往上，大的往下调整，选出次大的
AdjustDown(a, end, 0);
//缩小调整范围
--end;
}
}3.4.2 TOP-K问题
TOP-K 问题：即求数据结合中前 K 个最大的元素或者最小的元素，一般情况下数据量都比较大 。比如：专业前 10 名、世界 500 强、富豪榜、游戏中前 100 的活跃玩家等。对于 Top-K 问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了 ( 可能 数据都不能一下子全部加载到内存中) 。最佳的方式就是用堆来解决，基本思路如下：1. 用数据集合中前 K 个元素来建堆前 k 个最大的元素，则建小堆，这样前k个最大元素一定能进入到前 k 个最小的元素，则建大堆2. 用剩余的 N-K 个元素依次与堆顶元素来比较，不满足则替换堆顶元素将剩余 N-K 个元素依次与堆顶元素比完之后，堆中剩余的 K 个元素就是所求的前 K 个最小或者最大的元素。
用堆来解决TOP-K问题在效率和空间上都堪称完美。
问:我们如何直到自己用程序找出来的TOP-K是否正确？
在给全部数据赋随机值时，给它们都模一个数（例如1000000），也就是所有的随机值都小于1000000，然后将任意几个数的值改为大于1000000，检查结果中是否有这几个值即可。
实现：
//创文件并生成随机值
void CreateNDate()
{
//总数据个数
int n = 10000000;
srand(time(0));
//文件声明
const char* file = "data.txt";
//创建文件
FILE* fin = fopen(file,"w");
if (fin == NULL)
{
perror("fopen error");
return;
}
//赋随机值
for (int i = 0; i < n; i++)
{
int x = (rand() + i) % 10000000;
fprintf(fin, "%d\n", x);
}
fclose(fin);
}
//找出TopK
void PrintTopK(const char* filename,int k)
{
// 1. 建堆--用a中前k个元素建堆
//读文件
FILE* fout = fopen(filename,"r");
if (fout == NULL)
{
perror("fopen error");
return;
}
//开辟堆的空间
int* minheap = (int*)malloc(sizeof(int) * k);
if (minheap == NULL)
{
perror("malloc fail");
return;
}
for (int i = 0; i < k; i++)
{
//将文件中的数据读到数组中
fscanf(fout, "%d", &minheap[i]);
}
//将数组中的数据向下调整建堆
//从最后一个父节点开始调整
for (int i = (k - 2) / 2; i >= 0; i--)
{
AdjustDown(minheap,k, i);
}
// 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换
int x = 0;
//读到空为止
while (fscanf(fout, "%d", &x) != EOF)
{
if (x > minheap[0])
{
//替换x进堆
minheap[0] = x;
//向下调整，去合适的位置
AdjustDown(minheap, k, 0);
}
}
for (int i = 0; i < k; i++)
{
printf("%d ", minheap[i]);
}
printf("\n");
//释放数组空间，关闭文件
free(minheap);
fclose(fout);
}int main()
{
//建文件
CreateNDate();
PrintTopK("data.txt", 10);
return 0;
}二叉树的性质
重要结论：n0=n2+1;
增加一个n2等于减少一个n0，增加两个n0，增加一个n2，因此增加一个n2就等于增加一个n0。
练习
n0=n2+1=200;
A
关键点：完全二叉树
完全二叉树度为1的节点有一个或零个，
n0+n1+n2=2n
n0=n2+1
n0+n1+n0-1=2n
n1只能为奇数，即1
一颗高度为h的满二叉树的总节点数为2^(h-1)，当h为9时，满二叉树有512个节点，因此此二叉树高度为10，为不满10层的完全二叉树。
完全二叉树n1为0或者1 此处n1=0
n0+n2=767
n0=n2+1
2n0-1=767
n=384
4.二叉树链式结构的实现
4.1 前置说明
堆能够实现排序，TOPK等问题，而非完全二叉树/满二叉树没有任何实际意义，他们的用处在于
1.为更复杂的二叉树搜索树AVL （红黑树）打基础
例如搜索树：左子树总是小于右子树，能实现而二分查找类似的功能（中序），排序（先序）
2.很多二叉树的题在这上面出
4.2二叉树的遍历
4.2.1 前序、中序以及后序遍历
完全二叉树通过数组存储和遍历，非完全二叉树通过不同的方式储存和遍历。
遍历非完全二叉树我们要习惯于将一个二叉树无限拆分为 根，左子树和右子树。
1. 前序遍历(Preorder Traversal 亦称先序遍历 )—— 访问根结点的操作发生在遍历其左右子树之前。2. 中序遍历 (Inorder Traversal)—— 访问根结点的操作发生在遍历其左右子树之中（间）。3. 后序遍历 (Postorder Traversal)—— 访问根结点的操作发生在遍历其左右子树之后。
实现：
定义，创建，初始化
//定义二叉树节点
typedef struct BinaryTreeNode
{
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
int val;
}BTNode;
//创建节点
BTNode* BuyNode(int x)
{
//申请空间
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
if (node == NULL)
{
perror("malloc");
exit(-1);
}
//初始化节点
node->val= x;
node->left = NULL;
node->right = NULL;
return node;
}前序遍历：
通过递归调用的方式来实现，当节点不为空时，调用本函数来访问左子节点，参数为左子节点，在栈帧上额外开辟一块空间用来存放数据，再以同样的方式访问右子节点，直到下一个节点为空，就逐步递归返回值。
//前序遍历
void PrevOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
printf("%d ", root->val);
PrevOrder(root->left);
PrevOrder(root->right);
}以此类推写出中序遍历
//中序遍历
void Postrder(BTNode* root)
{
//节点为空，返回
if (root == NULL)
{
printf("NULL ");
return;
}
//先左 后根 再右
PrevOrder(root->left);
printf("%d ", root->val);
PrevOrder(root->right);
}4.3 节点个数以及高度等
4.3.1二叉树节点个数
采用分治的思想，每个节点负责计算出本身以及其左右子树的节点之和，因此依旧采用递归的方法。
// 二叉树节点个数
int TreeSize(BTNode* root)
{
//节点如果为空，返回0，不为空返回其左右子树的节点之和再加本身（1）
return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}4.3.2二叉树叶子节点个数
1.空树没有叶子 reutrn 0
2.左右子树为空就为叶子 return 1
3.左子树中叶子节点个数+右子树中叶子节点个数
// 二叉树叶子节点个数
int TreeLeafSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
if (root->left ==NULL&& root->right == NULL)
{
return 1;
}
return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}4.3.3二叉树第k层节点个数
当前树的第k层等于左子树的第k-1层和右子树的第k-1层节点数之和
当k=1则为要求的节点本身，返回1
k应该>=1
// 二叉树第k层节点个数
int TreeLevelKSize(BTNode* root, int k)
{
assert(k > 0);
if (root == NULL)
{
return 0;
}
//K=1则为本身
if (k == 1)
{
return 1;
}
return TreeLevelKSize(root->left, k-1) +
TreeLevelKSize(root->right, k-1);
}4.4练习
1.965. 单值二叉树 - 力扣（LeetCode）
什么情况返回 ture: 访问完所有节点（访问到空节点），每个节点的值都等于根节点。
什么情况返回 false :有任意一个节点存在且值不等于它的根节点。
我们只需要找出返回 false 的情况，剩下的就都默认访问到空节点返回 true 了
递归的方式我们采用 &&，即左右任意一个递归调用的返回值为 false，结果就为 false 了
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
bool isUnivalTree(struct TreeNode* root) {
//节点不存在，直接返回true
if(root==NULL)
{
return true;
}
//如果左子节点存在且不等于跟
if(root->left&&root->val!=root->left->val)
{
return false;
}
//如果右子节点存在且不等于根
if(root->right&&root->val!=root->right->val)
{
return false;
}
//如果左右子节点都等于根或者不存在，往子节点走
//其中一个返回false，则结果为false
return isUnivalTree(root->right)&&isUnivalTree(root->left);
}
