商城网站的主要模块,饭店的网站建设进行评价,昆明优化官网服务,7k7k网页游戏官网八#xff0c;树与二叉树
树
概念与结构
树是⼀种⾮线性的数据结构#xff0c;它是由 n#xff08;n0#xff09; 个有限结点组成⼀个具有层次关系的集合。把它叫做树是因为它看起来像⼀棵倒挂的树#xff0c;也就是说它是根朝上#xff0c;⽽叶朝下的。
• 有⼀…八树与二叉树
树
概念与结构
树是⼀种⾮线性的数据结构它是由 nn0 个有限结点组成⼀个具有层次关系的集合。把它叫做树是因为它看起来像⼀棵倒挂的树也就是说它是根朝上⽽叶朝下的。
• 有⼀个特殊的结点称为根结点根结点没有前驱结点。
• 除根结点外其余结点被分成 M(M0) 个互不相交的集合 T1、T2、……、Tm 其中每⼀个集合Ti(1 i m) ⼜是⼀棵结构与树类似的⼦树。每棵⼦树的根结点有且只有⼀个前驱可以有 0 个或多个后继。因此树是递归定义的。
树形结构中⼦树之间不能有交集否则就不是树形结构
⼦树是不相交的如果存在相交就是图了
除了根结点外每个结点有且仅有⼀个⽗结点
⼀棵N个结点的树有N-1条边
树的相关术语 ⽗结点/双亲结点若⼀个结点含有⼦结点则这个结点称为其⼦结点的⽗结点 如上图A是B的⽗结点
⼦结点/孩⼦结点⼀个结点含有的⼦树的根结点称为该结点的⼦结点 如上图B是A的孩⼦结点
结点的度⼀个结点有⼏个孩⼦他的度就是多少⽐如A的度为6F的度为2K的度为0
树的度⼀棵树中最⼤的结点的度称为树的度 如上图树的度为 6
叶⼦结点/终端结点度为 0 的结点称为叶结点 如上图 B、C、H、I… 等结点为叶结点
分⽀结点/⾮终端结点度不为 0 的结点 如上图 D、E、F、G… 等结点为分⽀结点
兄弟结点具有相同⽗结点的结点互称为兄弟结点(亲兄弟) 如上图 B、C 是兄弟结点
结点的层次从根开始定义起根为第 1 层根的⼦结点为第 2 层以此类推
树的⾼度或深度树中结点的最⼤层次 如上图树的⾼度为 4
结点的祖先从根到该结点所经分⽀上的所有结点如上图 A 是所有结点的祖先
路径⼀条从树中任意节点出发沿⽗节点-⼦节点连接达到任意节点的序列⽐如A到Q的路径为A-E-J-QH到Q的路径H-D-A-E-J-Q
⼦孙以某结点为根的⼦树中任⼀结点都称为该结点的⼦孙。如上图所有结点都是A的⼦孙
森林由 mm0 棵互不相交的树的集合称为森林
树的表示
树有很多种表⽰⽅式如双亲表⽰法孩⼦表⽰法、孩⼦双亲表⽰法以及孩⼦兄弟表⽰法等。我们这⾥就简单的了解其中最常⽤的孩⼦兄弟表⽰法
struct TreeNode
{ struct TreeNode* child; // 左边开始的第⼀个孩⼦结点 struct TreeNode* brother; // 指向其右边的下⼀个兄弟结点 int data; // 结点中的数据域
};二叉树
概念与结构
在树形结构中我们最常⽤的就是⼆叉树⼀棵⼆叉树是结点的⼀个有限集合该集合由⼀个根结点 加上两棵别称为左⼦树和右⼦树的⼆叉树组成或者为空。
⼆叉树具备以下特点
1⼆叉树不存在度⼤于 2 的结点
2⼆叉树的⼦树有左右之分次序不能颠倒因此⼆叉树是有序树
注意对于任意的⼆叉树都是由以下⼏种情况复合⽽成的 满⼆叉树
⼀个⼆叉树如果每⼀个层的结点数都达到最⼤值则这个⼆叉树就是满⼆叉树。也就是说如果⼀个⼆叉树的层数为 K 且结点总数是 2k − 1 则它就是满⼆叉树。
完全⼆叉树
完全⼆叉树是效率很⾼的数据结构完全⼆叉树是由满⼆叉树⽽引出来的。对于深度为 K 的有 n 个
结点的⼆叉树当且仅当其每⼀个结点都与深度为K的满⼆叉树中编号从 1 ⾄ n 的结点⼀⼀对应时称之为完全⼆叉树。要注意的是满⼆叉树是⼀种特殊的完全⼆叉树。
⼆叉树性质
根据满⼆叉树的特点可知
1若规定根结点的层数为 1 则⼀棵⾮空⼆叉树的第i层上最多有 2i−1 个结点
2若规定根结点的层数为 1 则深度为 h 的⼆叉树的最⼤结点数是 2h − 1
3若规定根结点的层数为 1 具有 n 个结点的满⼆叉树的深度 h log2 (n 1) ( log
以2为底 n1 为对数)
⼆叉树存储结构
顺序结构
链式结构
实现顺序结构的二叉树
⼀般堆使⽤顺序结构的数组来存储数据堆是⼀种特殊的⼆叉树具有⼆叉树的特性的同时还具备其他的特性。
堆
小堆小根堆堆顶是堆里最小的数据
大堆小根堆堆顶是堆里最大的数据
堆的性质
堆中某个结点的值总是不⼤于或不⼩于其⽗结点的值
堆总是⼀棵完全⼆叉树。
⼆叉树性质
对于具有 n 个结点的完全⼆叉树如果按照从上⾄下从左⾄右的数组顺序对所有结点从
0开始编号则对于序号为 i 的结点有
1若 i0 i 位置结点的双亲序号 (i-1)/2 i0 i 为根结点编号⽆双亲结点
2若 2i1n 左孩⼦序号 2i1 2i1n 否则⽆左孩⼦
3若 2i2n 右孩⼦序号 2i2 2i2n 否则⽆右孩⼦
堆的实现
堆底层结构为数组
头文件Heap.h
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h//堆的结构
typedef int HPDataType;
typedef struct Heap
{HPDataType* arr;int size; //有效数据个数int capacity; //空间大小
}HP;
//初始化
void HPInit(HP* php);
//销毁
void HPDestory(HP* php);
//打印
void HPPrint(HP* php);
//入堆
void HPPush(HP* php, HPDataType x);
//判断堆是否为空
bool HPEmpty(HP* php);
//向下调整
void AdjustDowm(HPDataType* arr, int parent, int n);
//出堆
void HPPop(HP* php);
//取堆顶元素
HPDataType* HPTop(HP* php);实现Heap.c
#define _CRT_SECURE_NO_WARNINGS
#includeHeap.h//初始化
void HPInit(HP* php)
{assert(php);php-arr NULL;php-size php-capacity 0;
}//销毁
void HPDestory(HP* php)
{assert(php);if (php-arr)free(php-arr);php-arr NULL;php-size php-capacity 0;
}//打印
void HPPrint(HP* php)
{assert(php);for (int i 0; i php-size; i){printf(%d , php-arr[i]);}printf(\n);
}//交换
void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}//调整
void AdjustUp(HPDataType* arr,int child)
{int parent (child - 1) / 2;while (child 0){//控制小堆大堆if (arr[child] arr[parent]){Swap(arr[child], arr[parent]);child parent;parent (child - 1) / 2;}else{break;}}
}//入堆
void HPPush(HP* php, HPDataType x)
{assert(php);//判断空间if (php-size php-capacity){int newcapacity php-capacity 0 ? 4 : 2 * php-capacity;HPDataType* tmp (HPDataType*)realloc(php-arr,sizeof(HPDataType) * newcapacity);if (tmp NULL){perror(HPPush()::realloc fail);exit(1);}php-arr tmp;php-capacity newcapacity;}//插入php-arr[php-size] x;//调整向上调整AdjustUp(php-arr,php-size - 1);php-size;
}//判断堆是否为空
bool HPEmpty(HP* php)
{assert(php);return php-size 0;
}//向下调整
void AdjustDowm(HPDataType* arr,int parent,int n)
{int child 2 * parent 1;while (child n){//控制大堆小堆//保证右孩子同样不越界if (child 1 n arr[child] arr[child 1]){child;}if (arr[child] arr[parent]){Swap(arr[child], arr[parent]);parent child;child 2 * parent 1;}else{break;}}}//出堆
//出的是堆顶元素
//1堆顶元素与最后一个size-1元素交换
//2调整向下调整假设成大堆比较左右孩子较大的与父结点比较。
void HPPop(HP* php)
{//首先堆不能为空assert(!HPEmpty(php));//先交换Swap(php-arr[0], php-arr[php-size - 1]);--php-size;//调整AdjustDowm(php-arr,0,php-size);
}//取堆顶元素
HPDataType* HPTop(HP* php)
{assert(!HPEmpty(php));return php-arr[0];
}测试文件test.c
#define _CRT_SECURE_NO_WARNINGS
#includeHeap.hvoid test()
{HP hp;HPInit(hp);HPPush(hp, 15);HPPush(hp, 10);HPPush(hp, 56);HPPush(hp, 70);HPPush(hp, 45);HPPrint(hp);//HPPop(hp);//HPPop(hp);//HPPop(hp);//HPPrint(hp);while (!HPEmpty(hp)){int top HPTop(hp);printf(%d , top);HPPop(hp);}HPDestory(hp);
}int main()
{test();return 0;
}堆排序
//交换
void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}//向上调整
void AdjustUp(HPDataType* arr,int child)
{int parent (child - 1) / 2;while (child 0){//控制小堆大堆if (arr[child] arr[parent]){Swap(arr[child], arr[parent]);child parent;parent (child - 1) / 2;}else{break;}}
}//向下调整
void AdjustDowm(int* arr,int parent,int n)
{int child 2 * parent 1;while (child n){//控制大堆小堆//保证右孩子同样不越界if (child 1 n arr[child] arr[child 1]){child;}//大堆小堆if (arr[child] arr[parent]){Swap(arr[child], arr[parent]);parent child;child 2 * parent 1;}else{break;}}}//堆排序(借助堆的思想实现)
void HPSort2(int* arr, int n)
{建堆,向下调整,升序大堆降序小堆//assert(arr);//for (int i (n - 1 - 1) / 2; i 0; i--)//{// AdjustDowm(arr, i, n);//}建堆,向上调整assert(arr);for (int i 0; i n; i){AdjustUp(arr, i);}//堆排序int end n - 1;while (end 0){Swap(arr[0],arr[end]);AdjustDowm(arr, 0, end);end--;}
}int main()
{test();int arr[] { 2,3,5,1,9,7,5,8,6,0 };int n sizeof(arr) / sizeof(arr[0]);for (int i 0; i n; i){printf(%d , arr[i]);}printf(\n);HPSort2(arr, n);for (int i 0; i n; i){printf(%d , arr[i]);}printf(\n);return 0;
}我们可以发现建堆时使用向上向下调整算法都可以那么哪种更好一点呢
从时间复杂度来进行比较向上调整算法建堆的时间复杂度为O(n ∗ log2 n) 向下调整算法建堆的时间复杂度为O(n)所以一般使用向下调整算法建堆
下面是分析过程
向上调整算法建堆时间复杂度
向下调整算法建堆时间复杂度
TOP-K问题
n k
