网站建设意义,夏津网站开发,手表交易网站,互联网销售是做什么的✨Blog#xff1a;#x1f970;不会敲代码的小张:)#x1f970; #x1f251;推荐专栏#xff1a;C语言#x1f92a;、Cpp#x1f636;#x1f32b;️、数据结构初阶#x1f480; #x1f4bd;座右铭#xff1a;“記住#xff0c;每一天都是一個新的開始#x1… ✨Blog不会敲代码的小张:) 推荐专栏C语言、Cpp️、数据结构初阶 座右铭“記住每一天都是一個新的開始” 本章内容《树和二叉树》的介绍✨ 1.树的概念及结构
树是一种非线性的数据结构它是由nn0个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的。
有一个特殊的结点称为根结点根节点没有前驱结点除根节点外其余结点被分成M(M0)个互不相交的集合T1、T2、……、Tm其中每一个集合Ti(1 i m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱可以有0个或多个后继因此树是递归定义的 树形结构中子树之间不能有交集否则就不是树形结构 目录 1.树的概念及结构树的表示树在实际中的运用 2.二叉树概念及结构满二叉树和完全二叉树二叉树的存储结构二叉树顺序表存储 3.堆的概念用顺序存储完成堆的实现创捷堆需要的结构初始化销毁堆交换两个数向上调整插入向下调整删除返回堆顶判空堆的大小 树的表示
树结构相对线性表就比较复杂了要存储表示起来就比较麻烦了既然保存值域也要保存结点和结点之间的关系实际中树有很多种表示方式如双亲表示法孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。
typedef int DataType;
struct Node
{struct Node* _firstChild1; // 第一个孩子结点struct Node* _pNextSibling; // 指向其下一个兄弟结点DataType _data; // 结点中的数据域
};树在实际中的运用
下图可以看得出Linux使用的就是树形结构父亲节点可以有n个孩子
2.二叉树概念及结构
一棵二叉树是结点的一个有限集合该集合: 1.或者为空 2.由一个根节点加上两棵别称为左子树和右子树的二叉树组成 从上图可以看出 1.二叉树不存在度大于2的结点 2.二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树
注意对于任意的二叉树都是由以下几种情况复合而成的
满二叉树和完全二叉树
满二叉树一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉树。也就是说如果一个二叉树的层数为K且结点总数是 则它就是满二叉树。完全二叉树完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为K的有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
二叉树的存储结构
二叉树一般可以使用两种结构存储一种顺序结构一种链式结构。
二叉树顺序表存储
顺序结构存储就是使用数组来存储一般使用数组只适合表示完全二叉树因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储关于堆我们后面的章节会专门讲解。二叉树顺序存储在物理上是一个数组在逻辑上是一颗二叉树。 顺序表存储二叉树只适用于完全二叉树否则会有空间上的浪费
3.堆的概念
如果有一个关键码的集合把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中将根节点最大的堆叫做最大堆或大根堆根节点最小的堆叫做最小堆或小根堆。
用顺序存储完成堆的实现
一个数组我们可以看作一个二叉树但还不是堆所以使用向上/下调整成一个堆。
建堆 升序建大堆 降序建小堆利用堆删除思想来进行排序 建堆和堆删除中都用到了向下调整因此掌握了向下调整就可以完成堆排序。 表示二叉树的值在数组位置中父子的下标关系 parent (child-1)/2 leftchild parent * 2 1 rightchild parent * 2 2
创捷堆需要的结构
typedef int HpDatatype;
typedef struct Heap
{HpDatatype* data;//元素int size;//长度int capcity;//容量
}Heap;初始化
//初始化
void HeapInit(Heap* php)
{assert(php);php-data (HpDatatype*)malloc(sizeof(HpDatatype) * 4);if (php-data NULL){perror(malloc fail);return;}php-size 0;php-capcity 4;}销毁堆
//销毁堆
void HeapDestroy(Heap* php)
{assert(php);free(php-data);php-data NULL;php-size 0;php-capcity 0;}交换两个数
//交换两个数
void Swap(HpDatatype* p1, HpDatatype* p2)
{HpDatatype tmp *p1;*p1 *p2;*p2 tmp;
}向上调整
时间复杂度N*logN
//向上调整
void AdjustUp(HpDatatype* a, int child)
{int parent (child - 1) / 2;while (child 0){if (a[child] a[parent]){Swap(a[child], a[parent]);child parent;parent (child - 1) / 2;}else{break;}}
}插入
//插入
void HeapPush(Heap* php, HpDatatype x)
{assert(php);if (php-capcity php-size){HpDatatype* tmp (HpDatatype*)realloc(php-data, sizeof(HpDatatype) * php-capcity * 2);if (tmp NULL){perror(malloc fail);return;}php-data tmp;php-capcity * 2;}php-data[php-size] x;php-size;AdjustUp(php-data, php-size-1);
}向下调整
时间复杂度O(N)
//向下调整
void AdjustDown(HpDatatype* a, int n, int parent)
{int child parent * 2 1;if (child1 n a[child] a[child 1]){child;}while (child n){if (a[parent] a[child]){Swap(a[parent], a[child]);parent child;child parent * 2 1;}else{break;}}
}删除
//删除
void HeapPop(Heap* php)
{assert(php);//assert(!HeapEmpty(php-data));Swap(php-data[0], php-data[php-size - 1]);php-size--;AdjustDown(php-data, php-size, 0);
}返回堆顶
//返回堆顶
HpDatatype HeapTop(Heap* php)
{assert(php);return php-data[0];
}判空
//判空
bool HeapEmpty(Heap* php)
{assert(php);return php-size 0;
}堆的大小
//堆的大小
int HeapSize(Heap* php)
{return php-size;
}
