大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
目录
创新互联是一家集网站建设,太和企业网站建设,太和品牌网站建设,网站定制,太和网站建设报价,网络营销,网络优化,太和网站推广为一体的创新建站企业,帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿,时刻以成就客户成长自我,坚持不断学习、思考、沉淀、净化自己,让我们为更多的企业打造出实用型网站。1、二叉树的实现方式
顺序结构
链式结构
二、数组二叉树
顺序结构的实现
堆的实现
堆的插入和删除
三、链式二叉树
前面了解了二叉树的一些性质,现在我们将用代码实现二叉树。二叉树的分叉让人第一印象就是用链式结构来存储,但数组的顺序结构也能用来存储二叉树,下面就是两种方式的区别。
顺序结构顺序结构是用数组来存储,但是一般只储存完全二叉树,因为完全二叉树不会有空间的浪费
链式结构链式结构就很好理解了,每一个节点有三块区域,分别是左子树、右子树和数据。
二、数组二叉树 顺序结构的实现前面说了,顺序结构一般存储完全二叉树,现实中我们通常把堆存放在数组里,下面就简单的介绍一下堆
堆:堆一种完全二叉树。堆分为两类,大堆和小堆。大堆是每个父节点的数据都大于或等于两个子节点,小堆是每个父节点都小于或等于两个子节点
注意:只要父节点大于等于或小于等于两个子节点就可以,和父节点的兄弟节点没关系
堆的代码结构:
typedef int HPDataType;//数据类型
typedef struct Heap
{
HPDataType* a;//一个数组
int size;//当前数据个数
int capacity;//数组最多能存储的数据个数
}
堆的实现想要建堆,先要学会堆的向下调整。向下调整有一个前提,左右子树必须都是堆,才可以向下调整。
向下调整的思想(以小堆为例)
向下调整的代码:
void HPJestDown(HPDataType* a, int size, int parent)
{
assert(a);
int child = parent * 2 + 1;//找到第一个子节点
while (child< size)//子节点不能越界,越界说明该节点是叶子节点
{
//第一个子节点和第二个子节点比较
//这里是小堆所以要找子节点中最小的和父节点比较
//并且还要判断一下这个父节点有没有右子节点防止越界
if (child + 1< size && a[child]< a[child + 1])
{
child++;
}
//最小的子节点比父亲小则交换
if (a[parent]< a[child])
{
Swap(&a[parent], &a[child]);//一个交换数据的函数
parent = child;//从被交换的子节点开始继续向下排序
child = child * 2 + 1;//找到这个子节点的子节点
}
else//不符合条件就跳出循环,调整完毕
{
return;
}
}
}
但是在创建堆时,根节点的左右子树都不是堆,我们可以把所有叶子节点看成一个堆,从他们的父节点开始调整,一直调整到根节点,最后就是一个堆了。
我们发现,根节点下标*2+1是左子节点下标,根节点下标*2+2是右子节点下标,但是左子节点下标减1再除以2和右子节点减1再除以2都是父节点的下标,所以我们可以这样写
void HeapCreate(Heap* hp, HPDataType* a, int size)
{
assert(a);
hp->size = hp->capacity = size;
HPDataType* newcapacity = (HPDataType*)malloc(sizeof(HPDataType) * size);
if (newcapacity == NULL)
{
perror("realloc file");
}
hp->a = newcapacity;
memcpy(hp->a, a,sizeof(a)*size);
//先找到最后一个叶子节点的父节点
//因为size是数据个数,对应下标要先减1,再减1后除以2
int i = (size - 2) / 2;
//从这个节点从后往前全部调整一边,调整完堆就建好了
while (i >=0)
{
HPJestDown(hp->a, hp->size, i);
i--;
}
}
堆的插入和删除插入数据
当我们有新的数据要插入时,我们必须把数据放在最后,一是如果放在最前面,数组内所有的数据都要挪动一下,二是我们辛辛苦苦建的堆会被破坏掉。放在最后再向上调整,向上调整的思想和向下调整类似,保证上面是堆,符合条件交换,直到不符合条件或到根节点停止。这里直接放代码和图片了
//这个是向上排序
void HPJestUP(HPDataType* a, int child)
{
assert(a);
//因为是向上调整,所以要找父节点
int parent = (child - 1) / 2;
//等于0就是根节点不需要再调整了
while (child != 0)
{
if (a[parent]< a[child])
{
Swap(&a[parent], &a[child]);
child = parent;
parent = (parent - 1) / 2;
}
else
{
break;
}
}
}
//插入数据
void HeapPush(Heap* hp, HPDataType x)
{
assert(hp);
//判断是否需要扩容
if (hp->size == hp->capacity)
{
hp->capacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
HPDataType* newcapacity = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * hp->capacity);
if (newcapacity == NULL)
{
perror("realloc file");
}
hp->a = newcapacity;
}
//直接放在最后面
hp->a[hp->size] = x;
hp->size++;
HPJestUP(hp->a, hp->size - 1);
}
删除数据
删除堆的数据一般是删除堆顶的数据,删除其他地方的数据没有意义。在删除数据是,若是把后面所有的数据都往前挪一格,那我们的堆就被破坏掉了。我们可以把最后一个节点和堆顶交换一下,数据个数减1在把新的堆顶向下调整,这样我们堆既没有被破坏,也把堆顶删除了,在插入数据时会把后面的数据覆盖掉。
void HeapPop(Heap* hp)
{
assert(hp);
assert(!HeapEmpty(hp));
//只需要把第一个和最后一个交换就可以了
//如果只有一个数据的话,那就是自己交换了
Swap(&hp->a[0], &hp->a[hp->size - 1]);
hp->size--;
HPJestDown(hp->a, hp->size, 0);
}
我们可以发现,每次删除都会把堆中最小的数据放在最后面。在不插入新的数据情况下,一直删下去我们数组中的数据变成有序的了。但是删除的话,堆的有效元素个数会变,在插入数据时会被覆盖。但我们可以利用这个思路来完成排序,拿到一个数组时,先将其建堆,再用这个思路排序。
注意: 升序要建大堆,降序要建小堆
void HeapSort(int* a, int n)
{
assert(a);
int i = (n - 2) / 2;
//这里是建堆
while (i >= 0)
{
HPJestDown(a, n, i);
i--;
}
i = n - 1;
//头尾交换,然后再向下调整
while (i >= 0)
{
Swap(&a[0], &a[i]);
HPJestDown(a, i, 0);
i--;
}
}
三、链式二叉树关于链式二叉树,我们先学习对链式二叉树的四种遍历方式。在这之前,我们先看一下二叉树的结构
typedef int BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;//数据域
struct BinaryTreeNode* left;//左子树
struct BinaryTreeNode* right;//右子树
}BTNode;
前面三种我们可以用递归来完成,实现方式非常简单
// 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root)
{
printf("%d ", root->data);//先访问自己
BinaryTreePrevOrder(root->left);//再访问左子树
BinaryTreePrevOrder(root->right);//最后访问右子树
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
BinaryTreeInOrder(root->left);//再访问左子树
printf("%d ", root->data);//先访问自己
BinaryTreeInOrder(root->right);//最后访问右子树
}
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
BinaryTreePostOrder(root->left);//再访问左子树
BinaryTreePostOrder(root->right);//最后访问右子树
printf("%d ", root->data);//先访问自己
}
最后一个层序遍历,我们要借助队列来实现。在访问一个节点时,把它的两个子树放进去。
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
Queue* queue = QueueCreate();//创建一个队列
if (root)
{
QueuePush(queue, root);//树不为空时入队
}
while (!QueueEmpty(queue))
{
//取出队列里一个节点
BTNode* p = QueueFront(queue);
printf("%d ", p->data);
QueuePop(queue);
//左子树不为空入队
if (p->left)
{
QueuePush(queue, p->left);
}
//右子树不为空入队
if (p->right)
{
QueuePush(queue, p->right);
}
}
printf("\n");
QueueDestory(queue);
}
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧