银川做网站最好的公司,芜湖企业,沧州网站设计公司价格,山西建设工程网#x1f381;#x1f381;创作不易#xff0c;关注作者不迷路#x1f380;#x1f380; C语言二叉树 【一】 前言一、数概念及结构1.数的概念1.2树的相关概念1.3树的表示 二、二叉树的概念及结构2.12.2二叉树的性质2.3二叉树的存储结构 三、二叉树的顺序结构实现3.1二叉树… 创作不易关注作者不迷路 C语言二叉树 【一】 前言一、数概念及结构1.数的概念1.2树的相关概念1.3树的表示 二、二叉树的概念及结构2.12.2二叉树的性质2.3二叉树的存储结构 三、二叉树的顺序结构实现3.1二叉树的顺序结构3.2堆的概念及结构3.3堆的实现3.3.1堆向下调整算法3.3.2堆的删除元素3.3.3堆的插入元素 四、源码 前言
在数据结构中二叉树作为步入实现复杂结构的门栏为后续的图排序衔接紧密因此我将详细讲解二叉树初定分为三至五篇文章讲解。 The Begin点点关注收藏不迷路 文章干货满满还请您细细品读
如果您觉得作者写得不错抑或对您有所帮助不妨给俺点个免费的赞和玩玩呢 关注作者不迷路后续将有更多原创内容更新哟 点点 点点 点点 点点 点点 点点
一、数概念及结构
1.数的概念 树是一种非线性的数据结构它是由nn0个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的。 有一个特殊的结点称为根结点根结点没有前驱结点除根结点外其余结点被分成M(M0)个互不相交的集合T1、T2、……、Tm其中每一个集合Ti(1 i m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱可以有0个或多个后继因此树是递归定义的。 注意树形结构中子树之间不能有交集否则就不是树形结构
1.2树的相关概念 结点的度一个结点含有的子树的个数称为该结点的度 如上图A的为6叶结点或终端结点度为0的结点称为叶结点 如上图B、C、H、I…等结点为叶结点双亲结点或父结点若一个结点含有子结点则这个结点称为其子结点的父结点 如上图A是B的父结点孩子结点或子结点一个结点含有的子树的根结点称为该结点的子结点 如上图B是A的孩子结点兄弟结点具有相同父结点的结点互称为兄弟结点 如上图B、C是兄弟结点树的度一棵树中最大的结点的度称为树的度 如上图树的度为6结点的层次从根开始定义起根为第1层根的子结点为第2层以此类推树的高度或深度树中结点的最大层次 如上图树的高度为4 1.3树的表示 树结构相对线性表就比较复杂了要存储表示起来就比较麻烦了既然保存值域也要保存结点和结点之间的关系实际中树有很多种表示方式如双亲表示法孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。 typedef int DataType;
struct Node
{struct Node* firstChild1; // 第一个孩子结点
struct Node* pNextBrother; // 指向其下一个兄弟结点DataType data; // 结点中的数据域
};代码的实际示例图如下 点点 点点 点点 点点 点点 点点
二、二叉树的概念及结构
2.1
这里我们主要介绍两种特殊的二叉树 满二叉树一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉树。也就是说如果一个二叉树的层数为K且结点总数是则它就是满二叉树。完全二叉树完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为K的有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。 2.2二叉树的性质 2.3二叉树的存储结构 二叉树一般可以使用两种结构存储一种顺序结构一种链式结构。 顺序存储 顺序结构存储就是使用数组来存储一般使用数组只适合表示完全二叉树因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储关于堆我们后面的章节会专门讲解。二叉树顺序存储在物理上是一个数组在逻辑上是一颗二叉树。 链式存储 二叉树的链式存储结构是指用链表来表示一棵二叉树即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链当前我们学习中一般都是二叉链后面课程学到高阶数据结构如红黑树等会用到三叉链。 typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{struct BinTreeNode* left; // 指向当前结点左孩子struct BinTreeNode* right; // 指向当前结点右孩子BTDataType data; // 当前结点值域
}// 三叉链
struct BinaryTreeNode
{struct BinTreeNode* parent; // 指向当前结点的双亲struct BinTreeNode* left; // 指向当前结点左孩子struct BinTreeNode* right; // 指向当前结点右孩子BTDataType data; // 当前结点值域
}
点点 点点 点点 点点 点点 点点
三、二叉树的顺序结构实现
3.1二叉树的顺序结构 普通的二叉树是不适合用数组来存储的因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事一个是数据结构一个是操作系统中管理内存的一块区域分段。 3.2堆的概念及结构 如果有一个关键码的集合K { k 0 k_0 k0 k 1 k_1 k1 k 2 k_2 k2… k n − 1 k_{n-1} kn−1}把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中并满足 K i K_i Ki K 2 ∗ i 1 K_{2*i1} K2∗i1 且 K i K_i Ki K 2 ∗ i 2 K_{2*i2} K2∗i2 ( K i K_i Ki K 2 ∗ i 1 K_{2*i1} K2∗i1 且 K i K_i Ki K 2 ∗ i 2 K_{2*i2} K2∗i2) i 012…则称为小堆(或大堆)。将根结点最大的堆叫做最大堆或大根堆根结点最小的堆叫做最小堆或小根堆。 堆的性质 堆中某个结点的值总是不大于或不小于其父结点的值堆总是一棵完全二叉树。 3.3堆的实现
3.3.1堆向下调整算法 现在我们给出一个数组逻辑上看做一颗完全二叉树。我们通过从根结点开始的向下调整算法可以把它调整成一个小堆。 向下调整算法有一个前提左右子树必须是一个堆才能调整。 通过示意图展现向下调整过程 // 左右子树都是大堆/小堆
void AdjustDown(HPDataType* a, int n, int parent)
{int child parent * 2 1;while (child n){// 选出左右孩子中大的那一个if (child 1 n a[child1] a[child]){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}3.3.2堆的删除元素
删除堆是删除堆顶的数据将堆顶的数据根最后一个数据一换然后删除数组最后一个数据再进行向下调整算法。 这里很多初学者都会有疑问为什么我们在删除根节点后不直接用他的儿子替代一次挪动这样不是更加方便吗 我想可以通过这张示意图来解答大家的困惑。首先我们发现挪动看似逻辑简单然而它带来了许多问题它直接改变了树的父子兄弟关系在这时候很有可能就不满足堆的概念了不再是顺序结构了。 void HeapPop(HP* php)
{
assert(php);
assert(!HeapEmpty(php));// 删除数据
Swap(php-a[0], php-a[php-size - 1]);
php-size--;
AdjustDown(php-a, php-size, 0);
}3.3.3堆的插入元素 先插入一个10到数组的尾上再进行向上调整算法直到满足堆。 // 除了child这个位置前面数据构成堆
void AdjustUp(HPDataType* a, int child)
{int parent (child - 1) / 2;//while (parent 0)while(child 0){if (a[child] a[parent]){Swap(a[child], a[parent]);child parent;parent (child - 1) / 2;}else{break;}}
}void HeapPush(HP* php, HPDataType x)
{assert(php);if (php-size php-capacity){HPDataType* tmp (HPDataType*)realloc(php-a, sizeof(HPDataType) * php-capacity*2);if (tmp NULL){perror(realloc fail);return;}php-a tmp;php-capacity * 2;}php-a[php-size] x;php-size;AdjustUp(php-a, php-size - 1);
}四、源码
heap.c
#include Heap.hvoid HeapInit(HP* php)
{assert(php);php-a (HPDataType*)malloc(sizeof(HPDataType)*4);if (php-a NULL){perror(malloc fail);return;}php-size 0;php-capacity 4;
}void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType x *p1;*p1 *p2;*p2 x;
}// 除了child这个位置前面数据构成堆
void AdjustUp(HPDataType* a, int child)
{int parent (child - 1) / 2;//while (parent 0)while(child 0){if (a[child] a[parent]){Swap(a[child], a[parent]);child parent;parent (child - 1) / 2;}else{break;}}
}void HeapPush(HP* php, HPDataType x)
{assert(php);if (php-size php-capacity){HPDataType* tmp (HPDataType*)realloc(php-a, sizeof(HPDataType) * php-capacity*2);if (tmp NULL){perror(realloc fail);return;}php-a tmp;php-capacity * 2;}php-a[php-size] x;php-size;AdjustUp(php-a, php-size - 1);
}// 左右子树都是大堆/小堆
void AdjustDown(HPDataType* a, int n, int parent)
{int child parent * 2 1;while (child n){// 选出左右孩子中大的那一个if (child 1 n a[child1] a[child]){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}void HeapPop(HP* php)
{assert(php);assert(!HeapEmpty(php));// 删除数据Swap(php-a[0], php-a[php-size - 1]);php-size--;AdjustDown(php-a, php-size, 0);
}HPDataType HeapTop(HP* php)
{assert(php);return php-a[0];
}bool HeapEmpty(HP* php)
{assert(php);return php-size 0;
}int HeapSize(HP* php)
{assert(php);return php-size;
}text.c
#define _CRT_SECURE_NO_WARNINGS 1
#include Heap.h//int main()
//{
// HP hp;
// HeapInit(hp);
// HeapPush(hp, 4);
// HeapPush(hp, 18);
// HeapPush(hp, 42);
// HeapPush(hp, 12);
// HeapPush(hp, 21);
// HeapPush(hp, 3);
// HeapPush(hp, 5);
// HeapPush(hp, 5);
// HeapPush(hp, 50);
// HeapPush(hp, 5);
// HeapPush(hp, 5);
// HeapPush(hp, 15);
// HeapPush(hp, 5);
// HeapPush(hp, 45);
// HeapPush(hp, 5);
//
// int k 0;
// scanf(%d, k);
// while (!HeapEmpty(hp) k--)
// {
// printf(%d , HeapTop(hp));
// HeapPop(hp);
// }
// printf(\n);
//
// return 0;
//}
heap.h#pragma once #includestdio.h #includeassert.h #includestdlib.h #includestdbool.h
// typedef int HPDataType; typedef struct Heap { HPDataType* a; int size; int capacity; }HP;
void HeapInit(HP* php); void HeapDestroy(HP* php);
void HeapPush(HP* php, HPDataType x); void HeapPop(HP* php); HPDataType HeapTop(HP* php); bool HeapEmpty(HP* php); int HeapSize(HP* php);
void AdjustUp(HPDataType* a, int child); void AdjustDown(HPDataType* a, int n, int parent); 如果您觉得写得不错还望赏个三连 以上就是关于的内容啦各位大佬有什么问题欢迎在评论区指正您的支持是我创作的最大动力 The End点点关注收藏不迷路
