网站dns设置,应该选用什么口罩,青岛官网seo方法,阿里云oss做网站备份堆的实现:SData/Heap/heap.c Hera_Yc/bit_C_学习 - 码云 - 开源中国
树
树的概念
树#xff1a;是一个非线性数据结构#xff0c;它是由n#xff08;n0#xff09;个有限结点组成一个具有层次关系的集合。
把它叫做树是因为它看起来像一棵倒挂的树#xff0c;也就…堆的实现:SData/Heap/heap.c · Hera_Yc/bit_C_学习 - 码云 - 开源中国
树
树的概念
树是一个非线性数据结构它是由nn0个有限结点组成一个具有层次关系的集合。
把它叫做树是因为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的。
有一个特殊的结点称为根结点根节点没有前驱结点。除根节点外其余结点被分成M(M0)个互不相交的集合T1、T2、……、Tm其中每一个集合Ti(1 i m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱可以有0个或多个后继因此树是递归定义的。
树形结构中子树之间不能有交集否则就不是树形结构。
树中不能构成回路不能有孤立的点。 如何理解树是递归定义的呢 相关概念 树的结构定义
链式表示 数组表示 二叉树
二叉树概念
一棵二叉树是结点的一个有限集合该集合:
或者为空。 由一个根节点加上两棵别称为左子树和右子树的二叉树组成。二叉树不存在度大于2的结点。二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树。
特殊的二叉树 满二叉树一个二叉树如果每一个层的结点数都达到最大值2则这个二叉树就是满二叉树。也就是说如果一个二叉树的层数为K。那么结点总数是(2^K - 1)则它就是满二叉树。完全二叉树完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。满二叉树是一种特殊的完全二叉树。假设有k层的完全二叉树前k-1层都是满的最后一层可以不满但必须是从左到右连续。 二叉树性质
1. 若规定根节点的层数为1则一棵非空二叉树的第i层上最多有2^(i-1)个结点。
2. 若规定根节点的层数为1则深度为h的二叉树的最大结点数是2^h -1。
3. 对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n2 ,则有n0n21。
即度为0叶子结点的数量 度为2的结点数量 1 。 3.在具有 2n 个结点的完全二叉树中叶子结点个数为 A n B n1 C n-1 D n/2 解析假设叶子结点右x个则度为2的结点右x-1个 总节点数 x (x - 1) 度为1的结点数量 所以总数量 2*n x(x-1)1 xn 4.二叉树的高度用于堆的选树、搜索二叉树、平衡搜索二叉树 二叉树存储
二叉树的逻辑结构是一棵树物理结构分为顺序存储和链式存储两种结构。
数组实现 ------------------------------------------------二叉树实现在文章末尾 ------------------------------------------------
堆
堆实际上就是数组形式存储的完全二叉树。(逻辑结构是完全二叉树物理结构是数组)
堆的作用堆排序效率高、选数等 向下调整算法
(向下调整算法是堆中最重要的算法堆、堆排序等都需要调整算法来支撑。
向下调整算法构建堆
前提是根节点的左右字数必须是大堆或者小堆。 //向下调整算法
//左右子树必须保证都是小堆或者大堆
static void AdjustDown(HPDataType* a, int n, int root)
{int parent root;int child parent * 2 1;//默认是左孩子更小while (childn){//找出左右孩子中小的一个if (child1n a[child 1] a[child]){child;}//如果孩子小于父亲则交换if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent*21;}else{break;}}
} 数组建堆
向下调整算法用于建堆
//arr是传入的数据 arr[n]
void HeapInit(Heap* php, HPDataType* arr, int n)
{assert(php);php-_a (HPDataType*)malloc(sizeof(HPDataType) * n);if (php-_a NULL){printf(%s\n, strerror(errno));return;}memcpy(php-_a, arr, sizeof(HPDataType) * n);//内存拷贝php-_size n;php-_capacity n;//数组建堆//利用的向下调整算法:// 从最下面的第一个非叶子结点开始调整,// 一层层完成小堆的构建//直到根节点,在对根节点向下调整int i 0;for (i(php-_size-1);i 0; i--){AdjustDown(php-_a, php-_size, i);}//
} 向上调整算法
向上调整算法用于入堆。 向上调整算法与向下调整类似不过是从子节点往父节点走。对于堆而言父节点和子节点的下标关系是必须掌握的。 void AdjustUp(HPDataType* arr,int n,int child)
{//从子节点往父结点调整//由child得出parentint parent (child-1)/2;while(child0){if(arr[child]arr[parent]){Swap(arr[child],arr[parent]); //childparent;parent(child-1)/2; //迭代向上}else{break;}}
}堆排序见排序与查找-CSDN博客。
入堆
void HeapPush(Heap* php, HPDataType x)
{assert(php);if (php-_size php-_capacity){php-_capacity * 2;HPDataType* tmp (HPDataType*)realloc(php-_a,sizeof(HPDataType) * (php-_size));if (tmp NULL){printf(%s\n, strerror(errno));return;}php-_a tmp;}php-_a[php-_size] x;AdjustUp(php-_a, php-_size, php-_size-1);}
与堆有关的OJ题:面试题 17.14. 最小K个数 - 力扣LeetCode典型的TopK问题 N个树中找出最大或最小的前K个数 排序 问题a、N*logN的效率能否进一步提高 b、假设N非常大内存不够排序建一个大小为K的堆来解决问题 eg找最大的前K个建一个大小为K的小堆比堆顶大则进堆(顶替掉堆顶的数据,然后向下调整)。 大堆性质堆顶的元素一定是最大的。找最小的K个数。小堆性质堆顶的元素一定是最小的。找最大的K个数。 解法一在leetcode/TopK/test_1.c · Hera_Yc/bit_C_学习 - 码云 - 开源中国
//建K大小的堆解法
void Swap(int* x, int* y) {int tmp *x;*x *y;*y tmp;
}void AdjustDown(int* arr, int n, int root) {int parent root;int child parent * 2 1;while (child n) // child不越界{if (child 1 n arr[child 1] arr[child]) // 大堆找更大的孩子{child;}if (arr[child] arr[parent]) // 大堆的父节点更大{Swap(arr[child], arr[parent]);parent child;child 2 * parent 1; // 向下迭代} else {break;}}
}int* smallestK(int* arr, int arrSize, int k, int* returnSize) {*returnSize k;if (k 0)return NULL;int* retArr (int*)malloc(sizeof(int) * k);*returnSize k;int i 0;// 建K个数的大堆for (i 0; i k; i) {retArr[i] arr[i];}for (i (k - 1 - 1) / 2; i 0; i--) {AdjustDown(retArr, k, i);} // 大堆建立完成K个数的大堆int j 0;for (j k; j arrSize; j) {if (arr[j] retArr[0]) {retArr[0] arr[j];AdjustDown(retArr, k, 0);}}return retArr;
} ------------------------------------------------堆到此结束 ------------------------------------------------
二叉树
伪树 在学习二叉树的基本操作前需先要创建一棵二叉树然后才能学习其相关的基本操作。由于现在对二叉树结构掌握还不够深入为了降低学习成本此处手动快速创建一棵简单的二叉树快速进入二叉树操作学习等二叉树结构了解的差不多时我们反过头再来研究二叉树真正的创建方式。
BTNode* BuyNode(BTDataType ch)
{BTNode* node (BTNode*)malloc(sizeof(BTNode));node-_data ch;node-_left NULL;node-_right NULL;return node;
}
//一个树的增删查改没有意义
//这里写一颗伪树
BTNode* A BuyNode(A);
BTNode* B BuyNode(B);
BTNode* C BuyNode(C);
BTNode* D BuyNode(D);
BTNode* E BuyNode(E);
BTNode* f BuyNode(f);
A-_left B;
A-_right C;
B-_left D;
B-_right E;
D-_left f;
学习二叉树的目的是为了掌握更加深层的数据结构因此会边学边补充 任何一个二叉树都要看作三个部分 1、根节点。2、左子树。3、右子树。 遍历 深度优先遍历先往深处走无路可走是退回来 访问其他结点。递归和栈实现。广度优先遍历一层层的走走完一层走下一层。队列实现。 树不同于其他的数据结构 简单的树的增删查改没有意义。单独的二叉树没有意义。平衡二叉树和搜索二叉树才有实际意义。 深度优先遍历
// 二叉树前序遍历
void PreOrder(BTNode* root);
// 二叉树中序遍历
void InOrder(BTNode* root);
// 二叉树后序遍历
void PostOrder(BTNode* root);
typedef char BTDataType;
typedef struct BinaryTree
{BTDataType _data;struct BinaryTree* _left;struct BinaryTree* _right;
}BTNode;
//前序
void PreOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}printf(%c , root-_data); //根PreOrder(root-_left); //左子树PreOrder(root-_right); //右子树
}
int TreeSize(BTNode* root)
{if (root NULL)return 0;elsereturn 1 TreeSize(root-_left) TreeSize(root-_right);
}
关于TreeSize如何返回值 广度优先遍历
广度优先遍历即层序遍历与递归无关通过队列的性质先进先出来实现。 结点个数
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
实现
int BinaryTreeSize(BTNode* root)
{if (root NULL)return 0;elsereturn 1 TreeSize(root-_left) TreeSize(root-_right);
}
int BinaryTreeLeafSize(BTNode* root)
{if (root NULL){return 0;}else if(root-_left NULL root-_right NULL){return 1;}else{return TreeLeafSize(root-_left) TreeLeafSize(root-_right);}
} // 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root NULL)return 0;if (k 1){return 1;}return BinaryTreeLevelKSize(root-_left, k - 1) BinaryTreeLevelKSize(root-_right, k - 1);
}查找
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root NULL)return NULL;if (root-_data x)return root;BTNode* node BinaryTreeFind(root-_left, x);if (node)return node;node BinaryTreeFind(root-_right, x);if (node)return node;return NULL;
}
销毁
// 二叉树销毁
void BinaryTreeDestory(BTNode* root);
// 二叉树销毁
void BinaryTreeDestory(BTNode* root)
{if (root NULL)return;BinaryTreeDestory(root-_left);BinaryTreeDestory(root-_right);free((root));//后序free不需要保存左和右root NULL;
}
判断一棵树是否是完全二叉树
// 判断二叉树是否是完全二叉树
//是返回1不是返回0
int BinaryTreeComplete(BTNode* root)
{//完全二叉树的层序遍历是两段非空结点空节点Queue q;QueueInit(q);if (root NULL)return 0;QueuePush(q, root);while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);if (front NULL){break;}QueuePush(q, front-_left);QueuePush(q, front-_right);}while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);if (front){QueueDestory(q);return 0;}}QueueDestory(q);return 1;
}
------------------------------------------本文二叉树到此结束-----------------------------------------------
到这里二叉树的学习进程仅有40%左右其余待补充.....
