用易语言做刷网站注册软件,网页设计版式布局,中国建设信用卡网站,一级建造师网官网Hi~#xff01;这里是奋斗的小羊#xff0c;很荣幸您能阅读我的文章#xff0c;诚请评论指点#xff0c;欢迎欢迎 ~~ #x1f4a5;#x1f4a5;个人主页#xff1a;奋斗的小羊 #x1f4a5;#x1f4a5;所属专栏#xff1a;C语言 #x1f680;本系列文章为个人学习… Hi~这里是奋斗的小羊很荣幸您能阅读我的文章诚请评论指点欢迎欢迎 ~~ 个人主页奋斗的小羊 所属专栏C语言 本系列文章为个人学习笔记在这里撰写成文一为巩固知识二为展示我的学习过程及理解。文笔、排版拙劣望见谅。 目录 前言一、TOP-K问题二、二叉树的链式结构2.1前中后序遍历2.2节点个数2.3叶子个数2.4高度 / 深度2.5第K层节点数2.6查找值为x的节点2.7二叉树销毁2.8相关OJ题2.9层序遍历 总结 前言
在TOP-K问题中有一种方法能在占用很小空间的情况下高效地找出最大或最小的前K个数。 在上篇文章介绍树时说树是递归定义的因此二叉树的遍历、二叉树的搜索、二叉树的深度、高度、节点数、二叉树的路径求解等问题基本都会用递归解决。 一、TOP-K问题
接上篇文章我们简单地了解了TOP-K问题介绍了如何从比较大的数据量中快速找出最大最小的前K个数据。
| 方法一 用这些较大的数据量建堆循环Top、Pop找出最大最小的前K个数。 但是这个方法有个致命缺陷它只适合数据量还不是特别大的情况因为如果数据量非常大时我们还建堆的话这对空间的消耗是很大的那我们就要想别的办法了。如果数据海量但我们现在只有1GB的内存直接建堆显然行不通。
| 方法二 将这海量数据分成合适的若干份分别建堆找出每份中的最大最小的前K的数再将这些数建堆循环Top、Pop K次就能找到最大最小的前K个数。 但是这个方法也不是特别好因为1GB的内存还是比较大的假如这个问题非要搞我们它有海量的数据但是只给我们1KB的内存甚至更狠一点只给我们100Byte的空间这时候方法二就显得力不从心了因为这个若干份将会非常大非常不理想。
| 方法三 先从这海量数据中拿出前K个数建小堆大堆然后再不断拿出剩下的数和堆顶数据比较如果大小于堆顶就替换掉堆顶再向下调整保证堆成立当这海量的数据全都比完后留在堆内的数就是这海量数据中最大最小的前K个数。 这个方法需要注意的是如果要求我们找最大的前K个数要建小堆最小的前K个数要建大堆。当然K也不能太大要是我们现在可用的内存连这K个数都装不下那就有点扯淡了。
方法三代码如下
void test1()
{FILE* pf fopen(data.txt, w);if (pf NULL){perror(fopen fail);return;}//产生随机的100000个数存到磁盘中for (int i 0; i 100000; i){//rand函数产生的随机数有重复i减少重复的数int ret rand() i;fprintf(pf, %d\n, ret);}fclose(pf);pf NULL;
}void test2()
{FILE* pf fopen(data.txt, r);if (pf NULL){perror(fopen fail);return;}int k 0;scanf(%d, k);int* arr (int*)malloc(k * sizeof(int));if (arr NULL){perror(malloc fail);return;}//读取k个数到数组中for (int i 0; i k; i){fscanf(pf, %d, arr[i]);}//k个数建小堆for (int i (k - 1 - 1) / 2; i 0; i--){AdjustDown(arr, i, k);}//读取剩下的数与堆顶比较int ret 0;while (fscanf(pf, %d, ret) 0){if (ret arr[0]){arr[0] ret;AdjustDown(arr, 0, k);}}//留在堆内的数就是所有数中最大的前K个数for (int i 0; i k; i){printf(%d , arr[i]);}fclose(pf);pf NULL;
}int main()
{srand((unsigned int)time(NULL));test1();test2();return 0;
}这里又有个问题我们怎么知道这K个数就是最大的前K个数呢如何验证
为了验证我们这个程序有没什么问题这里有个简单的小方法我们可以手动地在已经产生了100000个随机数的文件中修改K个使它们一定是最大的K个数然后再运行程序看看是否有问题。运行前先把产生随机数的函数屏蔽掉。 可以看到此时打印出来的10个数就是我们故意放进去的最大的10个数。 二、二叉树的链式结构
在上篇文章中简单地了解了二叉树的链式存储即用链表来表示一棵二叉树用链表来指示元素的逻辑关系。 通常每个节点由三个域组成一个数据域和两个指针域分别用左指针和右指针来指向左孩子和右孩子。链式结构又分为二叉链和三叉链当前我们学习的是二叉链三叉链会在后面的学习中学到。
typedef int BTDataType;
//二叉链
typedef struct BinTreeNode
{struct BinTreeNode* pleft;//左孩子struct BinTreeNode* pright;//右孩子BTDataType data;
}BTNode;二叉树的创建方式比较复杂后续我们会深入学习这里为了测试下面将要介绍的二叉树遍历我们先手动创建一棵链式二叉树。
#define _CRT_SECURE_NO_WARNINGS#include stdio.h
#include stdlib.htypedef int BinTreeType;typedef struct BinaryTreeNode
{BinTreeType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;BTNode* BuyNode(BinTreeType x)
{BTNode* node (BTNode*)malloc(sizeof(BTNode));if (node NULL){perror(malloc fail);return;}node-data x;node-left node-right NULL;return node;
}BTNode* GreatBinaryTree()
{BTNode* node1 BuyNode(1);BTNode* node2 BuyNode(2);BTNode* node3 BuyNode(3);BTNode* node4 BuyNode(4);BTNode* node5 BuyNode(5);BTNode* node6 BuyNode(6);node1-left node2;node1-right node4;node2-left node3;node4-left node5;node4-right node6;return node1;
}int main()
{BTNode* root GreatBinaryTree();return 0;
}2.1前中后序遍历 二叉树的操作离不开树的遍历按照规则二叉树的遍历有前序、中序、后序前根序、中根序、后根序的递归结构遍历。
前序 访问顺序为根节点、左子树、右子树 A B D N N N C E N N F N N 中序 访问顺序为左子树、根节点、右子树 N D N B N A N E N C N F N 后序 访问顺序为左子树、右子树、根节点 N N D N B N N E N N F C A 代码实现
void PrevOrder(BTNode* root)
{if (root NULL){printf(N );return;}printf(%d , root-data);PrevOrder(root-left);PrevOrder(root-right);
}void InOrder(BTNode* root)
{if (root NULL){printf(N );return;}InOrder(root-left);printf(%d , root-data);InOrder(root-right);
}void PostOrder(BTNode* root)
{if (root NULL){printf(N );return;}PostOrder(root-left);PostOrder(root-right);printf(%d , root-data);
}2.2节点个数
如何计算节点的个数呢可能有同学会想到用上面学到的前中后序遍历二叉树计数
int TreeSize(BTNode* root)
{int size 0;if (root NULL){printf(N );return;}size;printf(%d , root-data);TreeSize(root-left);TreeSize(root-right);return size;
}但这样是行不通的因为上面我们前中后序遍历二叉树是递归实现的每一次递归函数栈帧内都重新定义了size。 那可能又有同学说用static修饰size不就好了但是这个方法也不太能行得通。
int TreeSize(BTNode* root)
{static int size 0;if (root NULL){printf(N );return;}size;printf(%d , root-data);TreeSize(root-left);TreeSize(root-right);return size;
}可以看到用static修饰后这个方法也只能计算一次因为static修饰的变量在静态区程序运行结束才销毁。 我们可以考虑用递归的思想解决这个问题。因为一个二叉树的节点个数是左子树节点个数右子树节点个数1根节点左子树的节点个数又是它的左子树节点个数右子树节点个数1根节点所以我们可以用递归解决这个问题。 递归计算节点数代码如下
int TreeSize(BTNode* root)
{if (root NULL){return 0;}return TreeSize(root-left) TreeSize(root-right) 1;
}2.3叶子个数
如果节点的左指针和右指针都指向NULL那这个节点就是叶子如果节点为空就返回0。
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);
}2.4高度 / 深度
一个二叉树的高度是左子树高度和右子树高度大的一个再加一左子树的高度又是它的左子树高度和右子树高度大的一个再加一这显然又是一个递归问题。
int TreeHight(BTNode* root)
{ if (root NULL){return 0;}int lefthight TreeHight(root-left);int leftright TreeHight(root-right);return lefthight leftright ? lefthight 1 : leftright 1;
}这里需要注意要用一个值来接收左右子树的高度不要写成下面这种
int TreeHight(BTNode* root)
{ if (root NULL){return 0;}return TreeHight(root-left) TreeHight(root-right) ? TreeHight(root-left) 1 : TreeHight(root-right) 1;
}虽然下面这种看起来更简单但是当二叉树的深度比较深时这个代码的时间消耗是非常非常非常大的。 2.5第K层节点数
求第K层的节点数就是相对于第二层来说求第K-1层节点数相对于第三层来说求第K-2层节点数也可以用递归解决当节点不为空且K1时返回1。
int TreeKSize(BTNode* root, int k)
{if (root NULL){return 0;}if (k 1){return 1;}return TreeKSize(root-left, k - 1) TreeKSize(root-right, k - 1);
}2.6查找值为x的节点
查找值为x的节点可以用前序遍历二叉树解决当节点值等于x时返回节点指针如果不等于则查找左子树如果左子树找到了就返回节点指针如果没找到返回NULL则查找右子树不管找没找到都返回右子树的返回值。
BTNode* TreeFind(BTNode* root, BinTreeType x)
{if (root NULL){return NULL;}if (root-data x){return root;}BTNode* node TreeFind(root-left, x);if (node)//如果为空则左子树没找到{return node;}return TreeFind(root-right, x);
}2.7二叉树销毁
//二叉树销毁
void TreeDestroy(BTNode* root)
{assert(root);if (root NULL){return;}TreeDestroy(root-left);TreeDestroy(root-right);free(root);
}二叉树销毁函数调用完记得给root置NULL。 2.8相关OJ题
Leetcode—单值二叉树
bool isUnivalTree(struct TreeNode* root) {if (root NULL){return true;}if (root-left root-left-val ! root-val){return false;}if (root-right root-right-val ! root-val){return false;}return isUnivalTree(root-left) isUnivalTree(root-right);
}Leetcode—相同的树
bool isSameTree(struct TreeNode* p, struct 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);
}Leetcode—对称二叉树
bool _isSymmetric(struct TreeNode* p, struct TreeNode* q) {if (p q){if (p-val ! q-val){return false;}return _isSymmetric(p-left, q-right) _isSymmetric(p-right, q-left);}if (p q){return true;}return false;
}
bool isSymmetric(struct TreeNode* root) {if (root NULL){return true;}return _isSymmetric(root-left, root-right);
}Leetcode—二叉树的前序遍历
int TreeSize(struct TreeNode* root)
{if (root NULL){return 0;}return TreeSize(root-left) TreeSize(root-right) 1;
}
void PreOrder(struct TreeNode* root, int* arr, int* pi)
{if (root NULL){return;}//每次递归都会建立新的栈帧空间不同的栈帧空间内相同的变量之间互不影响//而我们需要的是每次函数递归都要改变下标所以需要传地址。arr[(*pi)] root-val;PreOrder(root-left, arr, pi);PreOrder(root-right, arr, pi);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize TreeSize(root);//在开辟空间前可以先算出节点个数以开辟合适的空间int* arr (int*)malloc(*returnSize * sizeof(int));int i 0;PreOrder(root, arr, i);return arr;
}函数每次递归都会建立独立的栈帧空间同一个变量在不同的栈帧空间中互不影响如果我们想让某一变量在每次函数递归都改变则应该传变量地址。 Leetcode—另一棵树的子树
bool isSameTree(struct TreeNode* p, struct 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 (root-val subRoot-val isSameTree(root, subRoot)){return true;}return isSubtree(root-left, subRoot) || isSubtree(root-right, subRoot);
}我们知道二叉树是由根节点和左右子树构成因此我们可以先判断两个根节点是否相等如果相等且左右子树也相等则两个二叉树互为子树如果根节点不相等则递归判断左子树或右子树。 2.9层序遍历
顾名思义层序遍历就是一层一层的遍历二叉树规则是将根节点插入队列中取出根节点后将根节点的两个子节点也就是第二层带入队列中取出左节点后又将左节点的两个子节点带入队列中依次遍历完整个二叉树。
//层序遍历
void TreeLevelOrder(BTNode* root)
{assert(root);Que q;QueueInit(q);if (root){QNodePush(q, root);}while (!QNodeEmpty(q)){BTNode* front QNodeFront(q);QNodePop(q);printf(%d , front-data);if (front-left){QNodePush(q, front-left);}if (front-right){QNodePush(q, front-right);}}QNodeDestroy(q);
}总结 二叉树由根节点、左子树和右子树组成每个子树也是一个二叉树。递归方法很适合处理这种具有递归结构的数据结构例如通过递归函数不断地遍历左右子树。递归的思想可以帮助我们分解复杂问题将大问题转化为相同结构的小问题从而简化解题过程。
