网站推广策略和营销策略,建立平台需要多少钱,哪个网站做logo设计师,百度百度百度一下数概念及结构
数的分类
二叉树、多叉树
数的概念
树是一种非线性的数据结构#xff0c;它是由n(n0)个有限节点组成一个具有层次关系的集合。把它叫做树的原因是它看起来像一颗倒挂的树#xff0c;也就是说它是跟朝上#xff0c;而叶朝下的。
有一个特殊的节点…数概念及结构
数的分类
二叉树、多叉树
数的概念
树是一种非线性的数据结构它是由n(n0)个有限节点组成一个具有层次关系的集合。把它叫做树的原因是它看起来像一颗倒挂的树也就是说它是跟朝上而叶朝下的。
有一个特殊的节点称为根节点这个节点没有前驱节点。除根节点外其余节点被分成M(M0)个互不相交的集合T1、T2、……、Tm其中每一个集合Ti1im又是一颗结构与树类似的子树。每颗子树的根节点有且只有一个前驱可以有0个或多个后继节点。数是递归定义的。子树是不相交的 什么是递归 大问题-类似子问题-类似子问题
数的相关概念
结点的度 一个结点含有的子树的个数称为该结点的度。 叶结点或终端结点度为0的结点。 非终端结点或分支结点度不为0的结点。 双亲结点或父节点若一个结点含有子结点则这个结点称为其子结点。 孩子节点或父节点一个节点含有子树的根的节点称为该节点的子节点。 兄弟节点:具有相同父节点的节点称为兄弟节点。 树的度一个树中最大的节点的度称为树的度。 节点的层次从跟开始定义起根为第1层根的子节点为第二层。 树的高度或深度树中节点的最大层次。 堂兄弟节点双亲在同一层次的节点互为堂兄弟。 节点的祖先从根到该节点所经分支上的所有节点。 子孙以某节点为根的子树中任一节点都称为该节点的子孙。 森林由m(m0)颗互不相交的树的集合称为森林。
数的高度一般都是从1开始从0开始也可以。 扩展 数组下标为什么要从0开始因为这符合偏移量。 当前元素到第一个元素的偏移量第一个元素的下标自然就是0第二个元素的下标为1第n个元素的下标为n-1。 并查集里面就是多棵树。
数的存储
树结构相对线性表就比较复杂了要存储表示起来就比较麻烦了既要保存值域也要保存节点和节点之间的关系实际中树有很多的表示方式如双亲表示法、孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里简单的了解其中最常见的孩子兄弟表示法。
struct TreeNode
{int val;struct TreeNode* firstchild;struct TreeNode*nextbrother;
}数在实际中的运用表示文件系统的目录结构 文件系统就是一个树形结构。
还有一种双亲表示法只存储双亲的下标或指针。 两个结点在不在同一棵树如何判断 找根根相同就是在同一棵树。
二叉树概念及结构
概念
一颗二叉树是结点得一个有限集合该集合 1、或者为空 2、由一个根结点加上两颗别称为左子树和右子树得二叉树组成。 注意 1、二叉树最多两个孩子。 2、二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树。 注意 空树、只有根结点、只有左子树、只有右子树、左右子树均存在。
特殊的二叉树
满二叉树
每一层都是2^(i-1)个结点每一层都是满的就是满二叉树。 高度为h的满二叉树有多少个节点 F(h)2021…2(h-2)2^(h-1) 使用错位相减法可以得到下面的结果 F(h)2^h-1
完全二叉树
假设他的高度是h,前h-1层是满的最后一层不一定满从左到右是连续的。
二叉树的性质
1、若规定根节点的层数为1则一颗非空二叉树的第i层上最多有2^(i-1)个节点。 2、若规定根节点的层数为1则深度为h的二叉树的最大节点数是2^k-1. 3、在任何二叉树中度为0的叶子节点永远比度为2的多一个,只有一个节点时 n0n21。 完全二叉树特点 度为1的节点只有1个或者0个。如果节点的个数是偶数那么度为1的节点个数等于1反之则为0。
二叉树的存储结构
二叉树一般可以使用两种结构存储一种顺序结构一种链式结构。
顺序存储
顺序结构存储就是使用数组来存储一般使用数组只合适表示完全二叉树因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组在逻辑上是一颗二叉树。 以下是数组结构存储的特点
leftchildparent * 21;
rightchildparent*22;parent(child-1)/2;任意位置通过下标可以找到父亲或者孩子。 总结满二叉树和完全二叉树适合使用数组储存。
链式存储
二叉树的链式存储结构是指用链表来表示一颗二叉树即用链来指示元素的逻辑关系。通常的方法是每个链表中每个节点由三个域组成数据域和左右指针域左右指针分别用来表示给出该节点左孩子和右孩子所在的链节点的存储地址。
结构如下
typedef int BTDataType;
struct BinaryTreeNode
{struct BinaryTreeNode* left;struct BinaryTreeNode*right;BTDataType data;
}二叉树顺序结构及实现
普通的二叉树是不适合用数组来存储的因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。实现中我们通常把堆一种二叉树使用顺序结构的数组来存储需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事一个是数据结构一个是操作系统中管理内存的一块区域分段。
堆的概念
将根节点最大的堆叫做最大堆或大根堆根节点最小的堆叫做最小堆或者小堆根。 堆非线性结构完全二叉树 小堆树中任意一个父亲都孩子 大堆树中任意一个父亲都孩子
底层物理结构数组 逻辑结构完全二叉树 小堆底层数组是否升序呢不一定。 小堆的根是整棵树的最小值。可以解决的问题 1、topk问题 2、堆排序
堆的实现
堆的插入
插入数据之后还要保证数据是堆。
堆的定义
底层就是一个顺序表可以使用数组来存储。
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;堆的初始化HeapInit
1断言 2有两种方式第一种直接置空第二种开一个空间。
//初始化堆
void HeapInit(HP* php)
{assert(php);php-a NULL;php-size php-capacity 0;
}打印HeapPrint
1断言 2使用循环打印
//打印
void HeapPrint(HP* php)
{assert(php);for (int i 0; i php-size; i){printf(%d , php-a[i]);}printf(\n);
}释放空间HeapDestroy
1断言 2先释放数组
//释放空间
void HeapDestroy(HP* php)
{assert(php);free(php-a);php-a NULL;php-size php-capacity 0;
}向上调整AdjustUp
1先算出父节点 2使用child等于0来结束循环 3判断孩子节点是否小于父节点小于的话就交换同时要修改child和parent的大小 4反之则直接退出循环。
void AdjustUp(HPDataType* a, int child)
{//找到父节点int parent (child - 1) / 2;//当下标小于等于零的时候结束循环while (child0){if (a[child]a[parent]){//交换两个数Swap(a[child], a[parent]);child parent;parent (child - 1) / 2;}else{//直接跳出循环break;}}
}交换函数Swap
需要的参数就是两个指针。 根据传过来的指针直接交换就好。
void Swap(HPDataType* child, HPDataType* parent)
{int temp *child;*child *parent;*parent temp;
}插入数据HeapPush
1断言 2扩容 3使用realloc在堆上开辟空间。 4向上调整向上调整的时候是需要数组的指针和最后一个数的下标
//插入数据
void HeapPush(HP* php, HPDataType x)
{assert(php);//扩容if (php-sizephp-capacity){int newcapacity php-capacity 0 ? 4 : php-capacity * 2;HPDataType* temp (HPDataType*)realloc(php-a, sizeof(HPDataType) * newcapacity);if (tempNULL){perror(realloc fail);exit(-1);}//把创建的空间分配给aphp-a temp;//定义容器的大小php-capacity newcapacity;}php-a[php-size] x;php-size;AdjustUp(php-a,php-size-1);
}向下调整AdjustDown
需要的参数指向数组的指针元素的个数跟节点的下标。 1先找到孩子 使用循环来找孩子循环的结束条件就是孩子的下标小于元素个数 2比较两个孩子谁小一点 注意右孩子可能出现越界的情况这需要考虑 3再比较孩子节点和父节点上的值 如果比父节点上的值小那就交换再继续向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{int child parent * 2 1;while (childn){if (child1na[child1]a[child]){child;}if (a[child]a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}删除数据HeapPop
删除根比较有意义。 如果挪动覆盖第一个位置根关系全乱了。 1先交换 根和最后一个值交换再删除。 需要注意的是要控制size的大小因该控制在大于0 交换完之后size需要减1 2向下调整 传参数的时候要传3个参数数组元素个数根节点。 元素个数用来控制节点的最大下标。
//删除数据
void HeapPop(HP* php)
{//断言assert(php);assert(php-size0);//交换Swap(php-a[0], php-a[php-size - 1]);php-size--;//向下调整AdjustDown(php-a,php-size,0);
}堆顶的数据HeapTop
只需要堆的指针 1断言 是否为空指针是否为空堆 2返回根
//取堆顶的数据
HPDataType HeapTop(HP* php)
{assert(php);assert(!HeapEmpty(php));return php-a[0];
}初始化数组HeapInitArray
需要的参数堆的指针数组指针开的空间大小 1断言 判断两个指针是否为空指针。 2给数组开空间 并判断空间是否开辟完成 3使用memcpy函数进行复制 4建堆
//初始化数组
void HeapInitArray(HP* php, int* a, int n)
{assert(php);assert(a);php-a (HPDataType*)malloc(sizeof(HPDataType)*n);if (php-aNULL){perror(malloc fail);exit(-1);}php-size n;php-capacity n;memcpy(php-a, a, sizeof(HPDataType) * n);for (int i 0; i n; i){AdjustUp(php-a, i);}
}判空HeapEmpty
只需要堆的指针 1断言 看指针是否为空 2返回size是否等于0
//判空
bool HeapEmpty(HP* php)
{assert(php);return php-size 0;
}
使用堆排序HeapSort
堆排序的特点就是数组有序 缺点需要写有一个堆。 向上调整。 排升序建大堆。 堆顶跟最后一个位置交换最大的数据就排好了剩下数据向下调整选出次大的代价是logN。合计是N* logN
//void HeapSort(int* a, int n)
//{
// HP hp;
// //初始化
// HeapInit(hp);
//
// for (int i 0; i n; i)
// {
// HeapPush(hp, a[i]);
// }
//
// int i 0;
// while (!HeapEmpty(hp))
// {
// printf(%d , HeapTop(hp));
// a[i] HeapTop(hp);
// HeapPop(hp);
// }
//
// HeapDestroy(hp);
//}void HeapSort(int* a, int n)
{// 建堆 大堆or 小堆for (int i 1; i n; i){AdjustUp(a, i);}int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);--end;}}
void test2()
{int a[] { 2,3,5,7,4,6,8 };HeapSort(a, sizeof(a) / sizeof(int));
}向下调整建堆 向上调整 TopK问题
假设10亿个数据内存存不下数据在文件中找出最大的前k个。 1、读取文件的前100个数据在内存中建立小堆 2、再依次读取剩下数据跟堆顶数据比较大于堆顶就替换他进堆向下调整 3、所有的数据读完堆里面数据就是最大的前100个 核心 建立小堆、时间复杂度O(N* logK)、空间复杂度O(K)
void PrintTopK(const char* filename, int k)
{// 1. 建堆--用a中前k个元素建堆FILE* fout fopen(filename, r);if (foutNULL){perror(fopen fail);return;}int* minheap (int*)malloc(sizeof(int) * k);if (minheapNULL){perror(malloc fail);return;}for (int i 0; i k; i){fscanf(fout, %d, minheap[i]);}//前k个数建小堆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 (xminheap[0]){//替换进堆minheap[0] x;AdjustDown(minheap, k, 0);}}for (int i 0; i k; i){printf(%d , minheap[i]);}printf(\n);free(minheap);fclose(fout);
}//创建文件
void CreateNData()
{//造数据int n 1000000;srand(time(0));const char* file data.txt;FILE* fin fopen(file, w);if (finNULL){perror(fopen error);return;}for (int i 0; i n; i){int x (rand() i) % 1000000;fprintf(fin, %d\n, x);}fclose(fin);
}int main()
{//CreateNData();PrintTopK(data.txt, 5);return 0;
}二叉树链式结构及实现
二叉树的遍历递归遍历 普通的链式二叉树没有意义。 1、更复杂二叉树搜索树-AVL 红黑树以后打基础 2、很多二叉树的题是出这一块 这就是搜索二叉树左边比根小右边比根大。 搜索二叉树走中序就是排序。
前序遍历PrevOrder
1、先手动构建二叉树
typedef struct BinaryTreeNode
{struct BinaryTreeNode*left;struct BinaryTreeNode*right;int val;
}BTNode;BTNode*BuyNode(int x)
{BTNode*node(BTNode*)malloc(sizeof(BTNode));if(nodeNULL){perror(malloc fail);return;}node-valx;node-leftNULL;node-rightNUll;return node;
}2、手动链接
int main()
{BTNode* node1BuyNode(1);BTNode* node2BuyNode(2);BTNode* node3BuyNode(3);BTNode* node4BuyNode(4);BTNOde* node5BuyNode(5);BTNode* node6BuyNode(6);node1-leftnode2;node1-rightnode4;node2-leftnode3;node4-leftnode5;node4-rightnode6;return 0;
}3、根 左子树 右子树
void PrevOrder(BTNode*root)
{if(rootNULL){printf(NULL );return ;}printf(%d ,root-val);PrevOrder(root-left);PrevOrder(root-right);
}中序遍历InOrder
先左子树 根 右子树
void InOrder(BTNode*root)
{if(rootNULL){printf(NULL );return ;}InOrder(root-left);printf(%d ,root-val);InOrder(root-right);
}后序遍历PostOrder
先左子树 右子树 根
void PostOrder(BTNode*root)
{if(rootNULL){printf(NULL);return ;}PostOrder(root-left);PostOrder(root-right);printf(%d ,root-val);
}二叉树节点个数TreeSize
方法一简单的方式就是遍历一遍。 方法二当前节点的个数等于左子树右子树自己 1、当前为空的时候返回0 2、反之就返回左子树右子树1
int TreeSize(BTNode* root)
{return rootNULL?0:TreeSize(root-left)TreeSize(root-right)1;
}叶子节点个数TreeLeafSize
1、空-0 2、叶-1 3、左子树右子树
int TreeLeafSize(BTNode*root)
{if(rootNULL){return 0;}if(root-leftNULLroot-rightNULL){return 1;}return TreeLeafSize(root-left)TreeLeafSize(root-right);
}第k层的节点个数TreeLevel
1、当前树的第k层左子树的第k-1层右子树的第k-1层
int TreeLevel(BTNode*root,int k)
{if(rootNULL){return 0;}if(k1){return 1;}return TreeLevel(root-left,k-1)TreeLevel(root-right,k-1);
}二叉树的销毁TreeDestroy
1、子问题 2、返回条件最小规模的子问题 3、使用后序遍历的思想进行销毁
void TreeDestroy(BTNode* root)
{if (rootNULL){return;}TreeDestroy(root-left);TreeDestroy(root-right);free(root);
}二叉树查找值为X的节点TreeFind
BTNode* TreeFind(BTNode* root, int x)
{//如果是空者返回空指针if (rootNULL){return NULL;}//如果找到了就返回当前节点的指针if (root-valx){return root;}//定义一个指针来接受返回的地址BTNode* ret NULL;//返回左边retTreeFind(root-left, x);//看左边是否为空不为空就说明找到了直接返回给上一级地址if (ret){return ret;}ret TreeFind(root-right, x);//看右边是否为空不为空就说明找到了直接返回给上一级地址if (ret){return ret;}//要是走到这个位置也没有返回说明没有找到值return NULL;
}
层序遍历LevelOrder
上一层带下一层 先进先出。
void LevelOrder(BTNode* root)
{//首先初始化Que q;QueueInit(q);if (root){QueuePush(q, root);}while (!QueueEmpty(q)){//取头的数据BTNode* front QueueFront(q);printf(%d , front-val);//带入左右子树if (front-left){QueuePush(q, front-left);}if (front-right){QueuePush(q, front-right);}QueuePop(q);}printf(\n);
}优先遍历
深度优先遍历DFS
前序遍历
广度优先遍历BFS
层序遍历配合队列
