2.2堆的操作
1.堆的调整（向上调整和向下调整两种）
对于堆的调整相当于是对数组的一种调整，将数组的首地址传进来，要调整的数组的长度，相当于是退出的循环条件，向下传给进来parent（root），向上传给child（size-1），然后再用一个表示另外一个。将参数传进来之后进行比较，先比较两个孩子，找出小的那个，然后交换较小孩子和双亲节点，在比较左右孩子的时候要保证右孩子也存在才可以进行比较，就是child+1<size,原因就是这里是堆，是完全二叉树
交换之后再将双亲节点往下走一个。注意，这里的调整每次只是调整堆顶元素。
/调整树相当与调整一个数组，将地址元素传进来之后我们不知道它有多少个节点，所以将元素的个数也传进来，调整的对象就是parent void AdjustDown(DataType array[], int size, int parent) { int child = parent * 2 + 1;//child标记parent的左孩子，树是完全二叉树，先有左再有右孩子 while (child < size) { //在保证有右孩子的时候，找两个孩子之中较小的孩子，要不会使得数组越界 //因为是完全二叉树，所以可以使用child+1<size进行表示 if (child + 1 < size && array[child + 1] < array[child]) { child += 1;//这里就是标记较小的孩子 } //检测parent是否满足堆的特性,不满足就进行交换 if (array[child] < array[parent]) { //交换双亲和孩子的大小，保证较小的在上边 //要交换两个元素的大小需要传入的是地址 Swap(&array[parent], &array[child]); //将双亲往下移动 parent = child; child = parent * 2 + 1; } else return; } }
//向上调整 void AdjustUp(DataType array[], int size, int child) { int parent = (child - 1) / 2; while (child) { if (array[child] < array[parent]) { Swap(array[child], array[parent]); child = parent; parent = (child - 1) / 2; } } }
2.堆的构建
堆的构建就是将数组中的元素传进来，将它的逻辑结构变成我们需要的堆的结构
将传入的数组使用堆中的数组进行接收，为其开辟空间，然后将数组拷贝进来，，注意memcpy的使用方法，第一个参数的是要拷贝到的地方，第二个参数是从哪拷贝，第三个参数是拷贝多少个字节。
然后重置堆的空间和有效元素个数，最后进行调整，注意要向上调整，因为这里不能确定除了堆顶元素以外其他的子树都满足完全二叉树，所以要从倒数第一个非叶子节点开始调整，用一个循环让他保证每次调整完之后都是拿到了最大或者最小的元素，类似冒泡排序
/先将输入的这些元素拷贝到堆中的数组之中 void HeapCreat(Heap* hp, DataType* a, int n) { hp->array = (DataType*)malloc(sizeof(DataType) * n); if (hp->array == NULL) { assert(0); return; } hp->CapaCity = n; memcpy(hp->array, a, sizeof(DataType) * n);//注意这个函数拷贝的时候第三个参数就是拷贝的是字节的大小 hp->size = n; //对堆进行调整 // 这个的调整方式就是需要保证除了叶子节点其他的都满足堆的特性，所以要先要求后边为堆 //因为不能保证每次调整的时候都是完全二叉树，所以需要从下边的倒数第一个非叶子节点开始往上调整 //最后一个叶子节点的下标是n-1，求他的双亲就是(n-1-1）/2 for (int root = (n - 2) / 2;root >= 0;root--) { //每次减去1就是往上进行调整每一棵树，最后0就是调整n AdjustDown(hp->array, hp->size, root); } }
3.其他基础操作
1.检查堆的空间是否足够 //与顺序表中的类似，，都是使用二倍开辟，然后将元素拷贝进去 void CheckHeap(Heap *hp) { assert(hp); if (hp->CapaCity == hp->size) { int newCapaCity = hp->CapaCity * 2; DataType* temp = (DataType*)malloc(sizeof(DataType) * newCapaCity); if (temp == NULL) { assert(0); printf("空间申请失败！！！"); return; } memcpy(temp, hp->array, sizeof(DataType) * hp->size); free(hp->array); hp->array = temp; hp->CapaCity = newCapaCity; } } //堆的插入 void HeapPush(Heap* hp, DataType x) { assert(hp); CheckHeap(hp); hp->array[hp->size] = x; hp->size++; AdjustUp(hp->array, hp->size, hp->array[hp->size]); } //堆的插入就是将元素插入后再次调整，保证堆的结构完整 //插入到最后一个元素，然后再往上调 //堆的删除 void HeapPop(Heap* hp) { if (HeapEmpty(hp)) { return; } //堆中有元素 //进行交换 Swap(&hp->array[0], &hp->array[hp->size - 1]); //堆中的元素个数减一 hp->size--; //将堆顶的元素往下调 AdjustDown(hp->array, hp->size, 0); } //将堆顶元素删除，再进行调整，再将个数减一 //删除的方法是将最后一个元素和堆顶的元素进行交换，然后size--，最后一个元素就访问不到了，之后再进行调整 //获取堆顶元素 DataType HeapTop(Heap* hp) { assert(hp); return hp->array[0]; } //比较简单，就是将数组的第一个元素a[0]输出就行 //堆中数据的个数 int HeapSize(Heap* hp) { assert(hp); return hp->size; } //就是将堆中的个数输出就行 //堆的判空 int HeapEmpty(Heap* hp) { assert(hp); return 0 == hp->size;//如果堆元素的个数为0的话就会返回真 } //直接就是判断堆元素个数是否为0
4.堆排序
/堆的排序就是 /* 1.建堆 升序就是建大堆，将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。 因为利用堆排序的思想就是建立堆之后1利用堆删除的思想，将堆顶最大的或者最小的元素与最后一个 叶子节点交换位置，如：建立大堆的话就是将最大的元素放到了最后边，实现了升序的功能 调整好之后将堆顶元素与最后一个元素进行交换位置，然后让size-1； */ Heap* LessSort(int array[], int size) { //实现利用堆思想从小到大排序，就是要把大的元素放到后边，所以建大堆 int lastNodeLeaf = (size - 2) / 2; for (int root = lastNodeLeaf;root >= 0;root--) { AdjustDown(array, size, root); } //利用堆删除的思想进行排序 int end = size - 1; while (end) { swap(&array[0], &array[end]); AdjustDown(array, end, 0); end--; } }
/*5.Top-k问题
* 因为数据量可能太大导致无法运行或者需要时间太长，这时候如果要求前k个最大的或者最小的元素
* 先把前k个元素进行加建堆，如果是要进行求前k个最大的元素，就i要建小堆，把较小的元素放到首位然后
* 与n-k中较大的元素进行替换，然后再进行调整，保证每一次替换出去的都是最小的哪一个
* 前k给最小的也是一样的，只不过要建一个大堆，保证每次换出去的都是较大的哪一个元素
*/
二叉树的基本操作：
在二叉树的基本操作中，有很多都是运用递归的思想
所有的基本操作都是基于二叉树的基本概念：
1.空树（空树也是树）
2.根以及左子树以及右子树，概念是递归的
1.二叉树的遍历
所谓二叉树的遍历是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点中操作一次
// 二叉树前序遍历 //假设现在就是遍历之后打印输出，使用递归，出口是为空树的时候 void PreOrder(BTNode* root) { if (NULL == root) return; printf("%d", root->data); PreOrder(root->left);//遍历左边就是把二叉树当做一个新的树进行操作 PreOrder(root->right); }
遍历之后的结果是；123456
下面使用三张图来解释这个操作
二叉树的高度：
注意概念，一个是空树就返回0，不是空树就是左子树和右子树
哪个子树的高度大就给哪个高度加一
直接求高度不好求，如果能知道子树的高度，在较高的子树基础上+1，就是二叉树的高度
int BInaryTreeHeight(BTNode* root) { if (NULL == root) return 0; int LeftHeight = BInaryTreeHeight(root->left); int RightHeight = BInaryTreeHeight(root->left); return LeftHeight > RightHeight ? LeftHeight + 1 : RightHeight + 1; }
这个就是加了一个比较，判断哪一个高度较大，然后进行+1；
求第k层中的节点的个数
1.// 二叉树第k层节点个数 /* * 思路： * 树是空树就返回0 k也不能小于0 * 直接求不好求，想想是否可以转化为子问题，即到其子树中求，应用递归找到它的k-1层 */ int BinaryTreeLevelKSize(BTNode* root, int k) { if (root == NULL || k <= 0) return 0; //如果k等于1，就返回节点总数1 if (k == 1) return 1; //root存在，而且大于1.就要去root子树中求k-1中求节点个数 return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1); }
//发现二叉树的定义是递归的，所以求树的时候直接考虑根节点和其两个子树的就差不多
其他基础操作：
// 二叉树节点个数 int BinaryTreeSize(BTNode* root) { if (root == NULL) return 0; return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right); } // 二叉树叶子节点个数 //叶子节点的个数就是求左子树中的叶子节点个数加上右子树中叶子节点的个数 //直接求不好求如果知道左子树中叶子节点的个数加上右子树叶子节点的个数就行 int BinaryTreeLeafSize(BTNode* root) { if (root == NULL) return 0; //这里代表它已经不是空节点了，再加上一个判断，判断是叶子节点,然后让他返回一个1 if (NULL == root->left && root->right) return 1; return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right); } // 二叉树第k层节点个数 /* * 思路： * 树是空树就返回0 k也不能小于0 * 直接求不好求，想想是否可以转化为子问题，即到其子树中求，应用递归找到它的k-1层 */ int BinaryTreeLevelKSize(BTNode* root, int k) { if (root == NULL || k <= 0) return 0; //如果k等于1，就返回节点总数1 if (k == 1) return 1; //root存在，而且大于1.就要去root子树中求k-1中求节点个数 return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1); } // 二叉树查找值为x的节点 //或运算有短路原则，如果第一个表达式不成立才会往右子树中去 BTNode* BinaryTreeFind(BTNode* root, Datatype x) { if (root == NULL) return NULL; //再在子树中寻找是否有x if (root->data == x) { return root; } BTNode* ret; //用来接收寻找结果,用来判断接着往下走 ret = BinaryTreeFind(root->left, x); if (ret != NULL) return ret; //为NULL就是没找到，不为空说明找到了，ret发生改变了，直接返回就行 //如果左边没找到直接返回右边就行 return BinaryTreeFind(root->right, x); 或者也可以一步写 //BTNode* ret; //(ret = BinaryTreeFind(root->left, x) || ret == BinaryTreeFind(root->right, x)); //return ret; } //二叉树的高度 int BInaryTreeHeight(BTNode* root) { if (NULL == root) return 0; int LeftHeight = BInaryTreeHeight(root->left); int RightHeight = BInaryTreeHeight(root->left); return LeftHeight > RightHeight ? LeftHeight + 1 : RightHeight + 1; }
