安卓开发网站开发,广州高端品牌网站建设,佛山网站建设网络推广,建设一个网站可以放视频的多少钱目录 前言 一、堆的应用 1. 堆排序 1.1 排升序#xff0c;建大堆 1.2 时间复杂度计算 2. Top k问题 二、 二叉树的链式实现 1. 二叉树的遍历 2. 二叉树基础OJ 2.2 100. 相同的树 总结 前言 学习完堆的数据结构#xff0c;我们要清楚#xff0c;它虽然实现了排序功能建大堆 1.2 时间复杂度计算 2. Top k问题 二、 二叉树的链式实现 1. 二叉树的遍历 2. 二叉树基础OJ 2.2 100. 相同的树 总结 前言 学习完堆的数据结构我们要清楚它虽然实现了排序功能但是真正的排序函数应当是在给定的数组内将数组排序如果我们要用堆排序那么我们不可能手写堆的数据结构在堆内排序后再复制给给定的数组这样不仅很麻烦而且还要开辟另外的空间。 所以我们又有了堆排序的方法。 一、堆的应用
1. 堆排序 我们可以将给定的数组看为一个完全二叉树但它此刻还不是堆因为堆是有顺序的所以我们可以使用向上或向下调整函数进行堆排序模拟堆插入这就是一个建堆的过程。 堆排序即利用堆的思想来进行排序总共分为两个步骤 1.建堆 升序建大堆降序建小堆 2.利用堆删除思想进行排序 1.1 排升序建大堆 方法一先利用向上调整建大堆在给定的数组内从下标为1的数据开始进行向上调整然后再进行向下调整完成升序排序 解释 如果采用小堆那么堆顶就是最小值取走堆顶数据后次小数上至堆顶此时堆所表示的二叉树内父子兄弟关系就全乱了不能再按顺序提出堆顶数据。 所以排升序还是需要用大堆 //堆排升序 -- 建大堆
void HeapSort(int* a, int n)
{// 1.建堆 -- 向上调整建堆--模拟插入的过程for (int i 1; i n; i){AdjustUp(a, i);}// 2.利用堆删除思想进行排序int end n - 1;while (end 0){swap(a[0], a[end]);AdjustDown(a, end - 1, 0);end--;//end下标前移}}int main()
{int a[10] { 2, 1, 5, 7, 6, 8, 0, 9, 4, 3 }; // 对数组排序HeapSort(a, 10);return 0;
} 方法二先向下调整建大堆再用向下调整完成升序排序 注意 在向下调整时不能从堆顶开始因为数组最初是无序的而向下调整的前提是其左右子树是大堆或小堆才可以向下调整 所以我们先将最后一个叶子节点的父节点开始向下调整完成调整后从父节点开始向前向下调整直到堆顶完成向下调整后结束。 综上分析方法二效率比方法一高只用写一个向下调整函数即可 //堆排升序 -- 建大堆
void HeapSort(int* a, int n)
{//1.建堆 -- 向下调整建堆for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(a, n, i);}// 2.利用堆删除思想进行排序int end n - 1;while (end 0){swap(a[0], a[end]);AdjustDown(a, end - 1, 0);end--;//end下标前移}}int main()
{int a[10] { 2, 1, 5, 7, 6, 8, 0, 9, 4, 3 }; // 对数组排序HeapSort(a, 10);return 0;
}
1.2 时间复杂度计算 向下调整建堆的时间复杂度计算 O(N) 向上调整建堆的时间复杂度计算 O(N*logN) 最简单的解释向下调整节点最多的一层最坏情况只调整一次节点最少的一层最坏情况调整h-1次而向上调整相反节点最少的一层最坏情况只调整一次节点最多的一层最坏情况调整h-1次显而易见向上调整的时间复杂度大于向下调整. 2. Top k问题 TOP-K问题即求数据结合中前K个最大的元素或者最小的元素一般情况下数据量都比较大。 对于Top-K问题能想到的最简单直接的方式就是排序但是如果数据量非常大排序就不太可取了(可能数据都不能一下子全部加载到内存中)。 最佳的方式就是用堆来解决基本思路下
1. 用数据集合中前K个元素来建堆
前k个最大的元素则建小堆取要排序的前k个数据先建一个小堆之后依次遍历数据与堆顶数据比较大小如果比堆顶数据大就替代它进堆然后向下调整前k个最小的元素则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较不满足则替换堆顶元素将剩余N-K个元素依次与堆顶元素比完之后堆中剩余的K个元素就是所求的前K个最小或者最大的元素 void PrintTopK(const char* file, int k)
{// 1. 建堆--用a中前k个元素建小堆int* topk (int*)malloc(sizeof(int) * k);assert(topk);FILE* fout fopen(file, r);if (fout NULL){perror(fopen error);return;}// 读出前k个数据建小堆for(int i 0; i k; i){fscanf(fout, %d, topk[i]);}for (int i (k-2)/2; i 0; --i){AdjustDown(topk, k, i);}// 2. 将剩余n-k个元素依次与堆顶元素交换不满则则替换int val 0;int ret fscanf(fout, %d, val);while (ret ! EOF){if (val topk[0]){topk[0] val;AdjustDown(topk, k, 0);}ret fscanf(fout, %d, val);}for (int i 0; i k; i){printf(%d , topk[i]);}printf(\n);free(topk);fclose(fout);
}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 (size_t i 0; i n; i){int x rand() % 10000;fprintf(fin, %d\n, x);}fclose(fin);
}int main()
{//int a[10] { 2, 1, 5, 7, 6, 8, 0, 9, 4, 3}; // 对数组排序//HeapSort(a, 10);CreateNDate();PrintTopK(data.txt, 10);return 0;
}
二、 二叉树的链式实现 二叉树本身增删查改没有什么实际意义但当加上了一个特性例如左子树小于根右子树大于根后即搜索二叉树它就有了实际意义。 在看二叉树基本操作前再回顾下二叉树的概念二叉树是 1. 空树 2. 非空根节点根节点的左子树、根节点的右子树组成的。 1. 二叉树的遍历 把每一个二叉树都分为三部分根、左子树、右子树 理解函数栈帧画图就可理解递归调用过程 二叉树结构体
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;1.1 前序遍历根、左子树、右子树 先访问根遇到每一个都作为根
1 2 3 NULL NULL NULL 4 5 NULL NULL 6 NULL NULL
//前序遍历
void PreOrder(BTNode* root) {if (root NULL) {printf(NULL );return;}printf(%d , root-data);PreOrder(root-left);PreOrder(root-right);
}
1.2 中序遍历左子树、根、右子树 (遇到每一个都先访问左子树直到NULL所以访问的第一个一定为NULL)
NULL 3 NULL 2 NULL 1 NULL 5 NULL 4 NULL 6 NULL
//中序遍历
void InOrder(BTNode* root) {if (root NULL) {printf(NULL );return;}InOrder(root-left);printf(%d , root-data);InOrder(root-right);
}1.3 后序遍历左子树、右子树、根 (左、右、根)
NULL NULL 3 NULL 2 NULL NULL 5 NULL NULL 6 4 1
//后序遍历
void PostOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}PostOrder(root-left);PostOrder(root-right);printf(%d , root-data);
}
1.4 层序遍历一层从左往右
1 2 4 3 5 6
用队列实现每出队一个根节点就把它的孩子入队实现出上一层带入下一层
#includeQueue.h
//队列的实现并把data的类型改为树结点指针类型void LevelOrder(BTNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* front QueueFront(q);//用树节点的指针类型接收队头数据因为队头数据类型为树节点指针类型QueuePop(q);printf(%d , front-data);//如果左孩子不为空就入队if(front-left)QueuePush(q, front-left);//如果右孩子不为空就入队if (front-right)QueuePush(q, front-right);}QueueDestroy(q);
}1.计算二叉树内结点个数 注意 如果想要计算二叉树内节点个数可以在传参时加上一个参数psize指针不要在函数内使用static静态局部变量因为它指挥在第一次调用时才执行之后调用都不会再执行也就是说第一次计算二叉树内节点个数是正确的而再次计算时size不能初始化为0所以计算结果就会出错。也尽量不使用全局变量这样的话我们要在每一次调用计算函数前自己手动初始化size全局变量为0并不是很方便。 最简形式 int TreeSize(BTNode* root)
{return root NULL ? 0 : TreeSize(root-left) TreeSize(root-right) 1;
} 2.计算树的高度 看山不是山不考虑太多递归过程看结果 注意 一定要记录递归结果因为如果不记录结果那么程序就会递归两大遍次数 int TreeHeight(BTNode* root)
{if (root NULL)return 0;int leftHeight TreeHeight(root-left);int rightHeight TreeHeight(root-right);return leftHeight rightHeight ? leftHeight 1 : rightHeight 1;
}3.计算第k层节点数 k--直到k为1就找到了要计算的第k层如果此时root不为NULL则return 1如果为NULL则返回0。这样就计算出了左右子树的第k-1层节点数最后相加。 int TreeKLevel(BTNode* root, int k)
{assert(k 0);if (root NULL)return 0;if (k 1)return 1;return TreeKLevel(root-left, k - 1) TreeKLevel(root-right, k - 1);
} 4.二叉树查找值为x的结点 注意 在函数多层调用时返回root是不能直接返回到最外面的只能返回上一个函数调用处 //二叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root NULL)return NULL;if (root-data x)return root;BTNode* lret BinaryTreeFind(root-left, x);if (lret)return lret;BTNode* rret BinaryTreeFind(root-right, x);if (rret)return rret;return NULL;
} 2. 二叉树基础OJ 2.1 965. 单值二叉树 bool isUnivalTree(struct TreeNode* root)
{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;return isUnivalTree(root-left) isUnivalTree(root-right);
}在写递归时要写递归的出口顾名思义是在递归过程中特殊的结果写能阻断递归的逻辑表达式。例如此题第二三个if只有在值不相等的时候返回false终止递归不能在判断中写相等的情况因为那样的判断没有任何用处 。 2.2 100. 相同的树 bool isSameTree(TreeNode* p, TreeNode* q){if(p NULL q NULL)return true;if(p NULL || q NULL)return false;if(p-val ! q-val)return false;return isSameTree(p-left,q-left) isSameTree(p-right,q-right);} 2.3 144. 二叉树的前序遍历 由于要返回数组所以要在函数内开辟一个数组空间而开辟多少字节空间就要我们计算二叉树的结点数
int TreeSize(struct TreeNode* root)
{return root NULL? 0 : TreeSize(root-left) TreeSize(root-right) 1;
}void preorder(struct TreeNode* root, int*arr, int* pi)
{if(root NULL)return;a[(*pi)] root-val;//错误因为i的值不会及时更新preorder(root-left,arr,pi);preorder(root-right,arr,pi);
}int* preorderTraversal(struct TreeNode* root, int* returnSize)
{*returnSize TreeSize(root);int* arr (int*)malloc(sizeof(int)*(*returnSize)));int i 0;preorder(root,arr,i);
}
注意前序遍历函数内数组下标是*pi因为如果只传整形 i 是无法在递归中及时更新i的值的 2.4 572. 另一棵树的子树 使左边的每一颗子树与右边的树比较可以利用上相同的树函数
bool isSameTree(TreeNode* p, TreeNode* q){//两个都为空if(p NULL q NULL)return true;//其中一个为空if(p NULL || q NULL)return false;//可以退出的情况if(p-val ! q-val)return false;return isSameTree(p-left,q-left) isSameTree(p-right,q-right);}bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{if(root NULL)return false;if(isSameTree(root,subRoot))return true;//递归一定要记录不然就白递归了//比如//isSubtree(root-left,subRoot);//isSubtree(root-right,subRoot);//return isSubtree(root-left,subRoot) || isSubtree(root-right,subRoot);//递归了两大遍是错误写法return isSubtree(root-left,subRoot) || isSubtree(root-right,subRoot);
} 2.5 KY11 二叉树遍历 struct TreeNode
{struct TreeNode* left;struct TreeNode* right;char val;
};void InOrder(struct TreeNode* root)
{if (root NULL)return;InOeder(root-left);printf(%c , root-val);InOeder(root-right);
}struct TreeNode* CreateTree(char* a, int* pi)
{if (a[*pi] #){(*pi);return NULL;}struct TreeNode* root (struct TreeNode*)malloc(sizeof(struct TreeNode));root-val a[(*pi)];root-left CreateTree(a, pi);root-right CreateTree(a, pi);return root;
}int main()
{char a[100];scanf(%s, a);int i 0;InOrder(CreateTree(a, i));return 0;
} 总结 二叉树这一数据结构包含了诸多的递归函数本节学习了二叉树的遍历、计算二叉树的高度、第k层结点数、总结点数、如何在二叉树内查找数以及一些二叉树的OJ 如何正确书写递归函数如何正确使用递归函数来计算二叉树的各项属性是学习二叉树的关键。 最后如果小帅的本文哪里有错误还请大家指出请在评论区留言ps抱大佬的腿新手创作实属不易如果满意还请给个免费的赞三连也不是不可以流口水幻想嘿那我们下期再见喽拜拜
