目录
堆的应用
1.堆排序:
1. 建堆
2.向下调整的时间复杂度
3.向上调整建堆的时间复杂度
二叉树链式结构的实现
遍历操作
其他操作
堆的应用
1.堆排序:
堆排序即利用堆的思想来进行排序,总共分为两个步骤:
1. 建堆
升序:建大堆
序:建大堆(如果建小堆的话,小堆不一定有序,只是堆顶最小,那下一个最小的数呢?如何依次选最小的数据?就算是选出来了之后,结点之间的关系就全乱了,无法继续利用优势,只能重新建堆O(N),选出次小的数据,效率太低了)建大堆直接交换堆顶和最后一个,进行向下调整即可
降序:建小堆
2.堆利用堆删除思想来进行排序
建堆和堆删除中都用到了向下调整,因此掌握了向下调整,就可以完成堆排序。回顾一下向下调整的过程:
这里的建堆,是直接用数组进行建堆,可以用向上调整算法进行建堆,也可以利用向下调整建堆,有什么区别?我们先来看代码的实现:
//建堆——a,利用向上调整建堆——O(N*logN)
//直接插入
/*for (int i = 1; i < n; i++)
{
AdjustUp(a, i);
}*/
//建完堆之后无序,我们排个序
//建堆——向下调整建堆(从最后一个节点的父亲开始,开始向下调整,直到根)——O(N)
for (int i = (n-1-1)/2; i>=0; i--)
{
AdjustDown(a, n, i);
}
两种的时间复杂度不一样:向上调整建堆的时间复杂度是O(N*logN);向下调整建堆的时间复杂度是O(N)。所以我们选用的是向下调整算法进行建堆,关于向下调整算法时间复杂度的推导过程:
2.向下调整的时间复杂度
因为堆是完全二叉树,而满二叉树也是完全二叉树,此处为了简化使用满二叉树来证明
(
时间复杂度本来看的 就是近似值,多几个节点不影响最终结果)
:
因此:建堆的时间复杂度为O(N)。
3.向上调整建堆的时间复杂度
了解完后我们下面来实现排序
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
//向下调整
void swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void adjustdown(int* a, int n, int parent)
{
//默认左孩子为最小值
int minchild = parent * 2 + 1;
while (minchild < n)
{
if (minchild + 1 < n && a[minchild] > a[minchild + 1])
{
minchild++;
}
if (a[minchild] < a[parent])
{
swap(&a[minchild], &a[parent]);
parent = minchild;
minchild = parent * 2 + 1;
}
else
{
break;
}
}
}
//建堆
void HeapSort(int* a, int n)
{
//建堆——a,利用向上调整建堆
//直接插入
/*for (int i = 1; i < n; i++)
{
AdjustUp(a, i);
}*/
//建完堆之后无序,我们排个序
//建堆——向下调整建堆(从最后一个节点的父亲开始,开始向下调整,直到根)
int i = 0;
for (i = (n - 1 - 1) / 2; i >= 0; i--)
{
adjustdown(a, n, i);
}
//选数
i = 1;
while (i < n)
{
swap(&a[0], &a[n - i]);
adjustdown(a, n - i, 0);
i++;
}
}
int main()
{
int a[] = { 15,1,19,25,8,34,65,4,27,7 };
HeapSort(a, sizeof(a) / sizeof(int));
for (int i = 0; i < sizeof(a) / sizeof(int); i++)
{
printf("%d ", a[i]);
}
printf("\n");
return 0;
}
这里建的是小堆所以是降序
二叉树链式结构的实现
在学习二叉树的基本操作前,需先要创建一棵二叉树,然后才能学习其相关的基本操作。为了降低学习成本,此处手动快速创建一棵简单的二叉树,这里以简单的实现为主。后续在来讨论其创建方式:
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
BTNode* CreatTree()
{
BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));
assert(n1);
BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));
assert(n2);
BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));
assert(n3);
BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));
assert(n4);
BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));
assert(n5);
BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));
assert(n6);
n1->data = 1;
n2->data = 2;
n3->data = 3;
n4->data = 4;
n5->data = 5;
n6->data = 6;
n1->left = n2;
n1->right = n4;
n2->left = n3;
n2->right = NULL;
n3->left = NULL;
n3->right = NULL;
n4->left = n5;
n4->right = n6;
n5->left = NULL;
n5->right = NULL;
n6->left = NULL;
n6->right = NULL;
return n1;
}
int main()
{
BTNode* root = CreatTree();
return 0;
}
这就大概搭建起了二叉树的框架,下面,来说一说其操作:
遍历操作
先序、中序、后序遍历递归操作:
//前序
void PreOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
printf("%d ", root->data);
PreOrder(root->left);
PreOrder(root->right);
}
//中序
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
InOrder(root->left);
printf("%d ", root->data);
InOrder(root->right);
}
//后续
void PostOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->data);
}
我们不难发现,二叉树的遍历操作通过递归实现非常地简单,实现并不难,但是你真的理解了吗函数怎么执行的(我们这里以前序遍历为例)
完整代码
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
BTNode* CreatTree()
{
BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));
assert(n1);
BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));
assert(n2);
BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));
assert(n3);
BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));
assert(n4);
BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));
assert(n5);
BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));
assert(n6);
n1->data = 1;
n2->data = 2;
n3->data = 3;
n4->data = 4;
n5->data = 5;
n6->data = 6;
n1->left = n2;
n1->right = n4;
n2->left = n3;
n2->right = NULL;
n3->left = NULL;
n3->right = NULL;
n4->left = n5;
n4->right = n6;
n5->left = NULL;
n5->right = NULL;
n6->left = NULL;
n6->right = NULL;
return n1;
}
//前序
void PreOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
printf("%d ", root->data);
PreOrder(root->left);
PreOrder(root->right);
}
//中序
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
InOrder(root->left);
printf("%d ", root->data);
InOrder(root->right);
}
//后续
void PostOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->data);
}
int main()
{
BTNode* root = CreatTree();
PreOrder(root);
printf("\n");
InOrder(root);
printf("\n");
PostOrder(root);
return 0;
}
其他操作
结点个数
//结点个数
int TreeSize(BTNode* root)
{
if (root == NULL)
return 0;
return TreeSize(root->left) +
TreeSize(root->right) + 1;
}
叶结点个数
//叶子结点个数
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);
}
高度
//高度
int TreeHeighrt(BTNode* root)
{
if (root == NULL)
{
return 0;
}
int left = TreeHeighrt(root->left);
int right = TreeHeighrt(root->right);
return left > right ? left + 1 : right + 1;
}
求第K层结点个数
//k层的结点数
int TreeLeveL(BTNode* root, int k)
{
assert(k > 0);
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}
return TreeLeveL(root->left, k - 1) + TreeLeveL(root->right, k - 1);
}
返回x所在的结点
//返回X所在的结点
BTNode* TreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
return NULL;
if (root->data == x)
return root;
//先去左树找
BTNode* left = TreeFind(root->left, x);
if (left != NULL)
return left;
//左树找不到,在去右树找
BTNode* right = TreeFind(root->right, x);
if (right != NULL)
return right;
return NULL;
}
完整代码
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
BTNode* CreatTree()
{
BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));
assert(n1);
BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));
assert(n2);
BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));
assert(n3);
BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));
assert(n4);
BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));
assert(n5);
BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));
assert(n6);
n1->data = 1;
n2->data = 2;
n3->data = 3;
n4->data = 4;
n5->data = 5;
n6->data = 6;
n1->left = n2;
n1->right = n4;
n2->left = n3;
n2->right = NULL;
n3->left = NULL;
n3->right = NULL;
n4->left = n5;
n4->right = n6;
n5->left = NULL;
n5->right = NULL;
n6->left = NULL;
n6->right = NULL;
return n1;
}
//前序
void PreOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
printf("%d ", root->data);
PreOrder(root->left);
PreOrder(root->right);
}
//中序
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
InOrder(root->left);
printf("%d ", root->data);
InOrder(root->right);
}
//后续
void PostOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->data);
}
//结点个数
int TreeSize(BTNode* root)
{
if (root == NULL)
return 0;
return TreeSize(root->left) +
TreeSize(root->right) + 1;
}
//叶子结点个数
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);
}
//高度
int TreeHeighrt(BTNode* root)
{
if (root == NULL)
{
return 0;
}
int left = TreeHeighrt(root->left);
int right = TreeHeighrt(root->right);
return left > right ? left + 1 : right + 1;
}
//k层的结点数
int TreeLeveL(BTNode* root, int k)
{
assert(k > 0);
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}
return TreeLeveL(root->left, k - 1) + TreeLeveL(root->right, k - 1);
}
//返回X所在的结点
BTNode* TreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
return NULL;
if (root->data == x)
return root;
//先去左树找
BTNode* left = TreeFind(root->left, x);
if (left != NULL)
return left;
//左树找不到,在去右树找
BTNode* right = TreeFind(root->right, x);
if (right != NULL)
return right;
return NULL;
}
int main()
{
BTNode* root = CreatTree();
PreOrder(root);
printf("\n");
InOrder(root);
printf("\n");
PostOrder(root);
printf("\n");
printf("Size:%d\n", TreeSize(root));
printf("LeafSize:%d\n", TreeLeafSize(root));
printf("LeafHeighrt:%d\n", TreeHeighrt(root));
printf("TreeLeveL:%d\n", TreeLeveL(root,3));
printf("Tree Find:%p\n", TreeFind(root, 8));
return 0;
}