j2ee网站开发免费教程,著名的网站制作公司,天津建设网站官网,专业的广州手机网站建设一. 树的概念 树在我们的日常生活中随处可见#xff0c;人们将生活中的树转换成存放数据的树形结构#xff0c;就成了数据结构中的“树”。 如上图所示#xff0c;自然界中的树有树根#xff0c;有树枝#xff0c;有树叶#xff0c;当我们将其转换成树形结构时#xf…一. 树的概念 树在我们的日常生活中随处可见人们将生活中的树转换成存放数据的树形结构就成了数据结构中的“树”。 如上图所示自然界中的树有树根有树枝有树叶当我们将其转换成树形结构时 只需将其倒转过来将树根树枝的岔口树枝的顶部画一个圆就成了一个完美的树形结构 树型结构是一种非线性的数据结构它是由NN0个结点组成的一个数据的集合我们称这种数据结构为“树”。 树的根部结点称为根结点根结点是没有前驱结点的 除了根结点外其余结点被分成互不相交的集合 每个集合都是结构与树类型相似的子树每棵子树的根结点有且仅有一个前驱结点后 继结点可以有0个或多个。 每棵子树是互不相交的如果相交则为“图”不为“树” 除了根结点外每个结点都只有一个父结点 假设一棵树有N个结点那么这条数有N-1条边 二. 树的相关术语
父结点如果一个结点有子节点那么这个结点是子节点的父节点
子结点 一个结点含有的子树的根结点称为该结点的子结点
结点的度一个结点有N个子结点那么这个结点的度为N
树的度最大的结点的度称为树的度
叶子结点度为0的结点
分支结点度不为0的结点
结点的层次从根开始定义根为第一层根的子结点为第二层以此类推
树的高度树中结点的最大层次 三. 二叉树的概念 二叉树是树的一种也是我们最常用的树形结构一棵二叉树是结点的一个有限集合该集合由一个根结点和两棵分别称为“左子树”和“右子树”的二叉树组成。 上图是一棵二叉树通过上图我们可知二叉树有以下特点 1. 二叉树的结点的度不大于2 2. 二叉树的子树有左右之分因此二叉树是有序树 3. 二叉树可以是空树可以只有根结点左子树可以为空右子树可以为空左右子树均在 四. 满二叉树 对于每个结点的度数都达到最大值我们称这种二叉树为满二叉树。 一棵树的层数为N最大结点数为2*N-1下图是一棵满二叉树层数为3最大节点数为7 五. 完全二叉树 完全二叉树是由满二叉树引出来的对于深度为K的有N个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从1到N的结点一一对应时称为完全二叉树。 注意满二叉树一定是完全二叉树但完全二叉树不一定是满二叉树 六. 顺序结构的二叉树
顺序结构的二叉树底层为数组但是只适合完全二叉树不然会造成空间的浪费
对于完全二叉树因为其结点都有连续对应的编号因此适合用数组存储数组的下标代替了结点的编号 对于非完全二叉树如果使用数组来实现有内存空间的浪费 七. 顺序结构二叉树的实现本文以小堆为例
我们一般用堆来实现顺序结构的数组堆其实是一种特殊的二叉树它有着二叉树的性质也有许多其他的特性同时堆也是一棵完全二叉树。
堆也分为大堆和小堆 大堆根结点存放的数据最大每个父结点都比其子结点要大 小堆根结点存放的数据最小每个父结点都比其子结点要小 子结点与父结点的关系 对于子结点 若子结点 i 在该堆中有效则其父结点对应的序号为(i-1)/2当i0时无 父结点因为i0时为根结点根结点没有父结点 对于父结点若父结点的序号为i, 左孩子序号为2*i1右孩子序号为2*i2 对于结点数位n的完全二叉树若2*i1n则无左孩子 若2*i2n,则无右孩子 都大于最大结点数了不可能还有子结点的总不能凭空加上去吧 1.堆的结构定义
堆的底层结构是数组和顺序表很相似其实在定义结构体中也是十分相似的
typedef int HPDataType;
//堆的定义
//堆的底层为数组
typedef struct Heap {HPDataType* arr;//指向动态开辟内存的地址int size;//堆的有效数据个数int capacity;//堆的最大容量
}HP; 2.堆的初始化
初始化操作与顺序表一致这里就不再赘述
void HPInit(HP* php) {assert(php);php-arr NULL;php-size php-capacity 0;
}
3.堆的销毁
销毁操作与顺序表一致不再赘述
void HPDestroy(HP* php) {assert(php);if (php-arr) {free(php-arr);}php-capacity php-size 0;php-arr NULL;
}
4.入堆 在入堆操作时是在堆尾进行插入的在插入前需要检查当前堆的空间是否足够容纳新数据空间不足的话需要先扩容再进行入堆。 因为堆分为大堆和小堆我们在入堆操作后新数据所在的位置不一定满足堆的性质这里我们所以我们需要将新数据向上调整直到新数据所处的位置满足堆的性质新数据调整完后更新堆的有效个数。
void HPPush(HP* php, HPDataType x) {assert(php);//检查空间是否不足if (php-capacity php-size) {//如果堆空间为0,扩容int newcapacity php-capacity 0 ? 4 : php-capacity * 2;HPDataType* ret (HPDataType*)realloc(php-arr, newcapacity*sizeof(HPDataType));if (ret NULL) {perror(relloc);exit(1);}php-arr ret;php-capacity newcapacity;}//在当前位置入堆php-arr[php-size] x;AdjustUp(php-arr,php-size);//堆的有效个数1,为什么要到最后才更新堆的有效个数//因为向上调整法需要传递新插入结点的下标插入堆后下标刚好是size//当然更新有效个数后再进行向上调整也是可以的修改向上调整函数的第二个参数就行 php-size;
}
那么对入堆数据的向上调整时是如何实现的呢 5.向上调整法堆的插入后需要调整
毫无疑问入堆的数据成为了某一个结点的子结点向上调整我们需要知道当前结点的父结点
利用当前结点在数组所对应的下标入堆对应的下标其实就是有效数据个数size 新结点入堆后开始进行向上调整当前结点与其父结点相比较 然后更新父结点与子结点因为我们建立的是小堆所以当子结点大于父结点时便不再需要继续向上调整
//交换函数
void Swap(HPDataType* x, HPDataType* y) {HPDataType tmp *x;*x *y;*y tmp;
}//向上调整算法,子求父 子-1/2
void AdjustUp(HPDataType* arr, int child) {int parent (child - 1) / 2;while (child 0) {//确保当前节点 child 有一个有效的父节点可以进行比较和调整。if (arr[child] arr[parent]) {Swap(arr[child], arr[parent]);//传址调用}else {break;}}
}向上调整法图示 6.出堆
对于堆而言出堆的结点是堆顶也就是树的根结点 你或许会想堆的底层结构为数组那么我们直接将数组下标为0的数据删除就好。那么真的可以这样操作吗
如下图假如我们直接将数组下标为0的结点直接出堆出堆后既不是大堆也不是小堆而且原本结点的父子关系也错误了 正确的出堆方法将堆顶的结点与堆底相调换再删除堆底结点再让新的堆顶结点向下调整
因为数组最后一位删除后堆的结构不会发生改变 堆顶和堆底相交换后删除新的堆底然后新的堆顶向下调整如果子结点比父结点大则两者向交换直到子结点比父结点小或者子结点处于非法范围 7.向下调整法堆的删除后需要调整
在小堆的出堆后要进行向下调整的结点毫无疑问是堆顶向下调整我们需要知道其最小的子结点当我们找到最小的子结点后将最小的子结点与父结点比较如果子结点比父结点小则交换然后更新父结点和子结点。否则不需要向下调整
//向下调整算法父求子父*2 1/2
void AdjustDown(HPDataType* arr, int parent, int n) {//n 是数组的大小int child parent*2 1;//假设左孩子最小while (child n)//孩子不能超过数组的界限{//找左右孩子中找最小的if (child 1 n arr[child] arr[child 1])//child 1 n检查是否有右孩子没有右孩子就不进入{child;}if (arr[child] arr[parent])//父比子大交换因为是形成小堆最小的要在堆顶{Swap(arr[child], arr[parent]);parent child;child parent * 2 1;}else{break;}}
}
8.堆的判空
返回堆的有效数据个数即可判断堆是否为空
//判空
bool HPEmpty(HP* php) {assert(php);return php-size0;
}
9.取堆顶数据
//取堆顶
HPDataType HPTop(HP* php)
{assert(php php-size);return php-arr[0];
}
八.全码
#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) {assert(php);php-arr NULL;php-size php-capacity 0;
}//销毁
void HPDestroy(HP* php) {assert(php);if (php-arr) {free(php-arr);}php-capacity php-size 0;php-arr NULL;
}//交换函数
void Swap(HPDataType* x, HPDataType* y) {HPDataType tmp *x;*x *y;*y tmp;
}
//向上调整算法,子求父 子-1/2
void AdjustUp(HPDataType* arr, int child) {int parent (child - 1) / 2;while (child 0) {//确保当前节点 child 有一个有效的父节点可以进行比较和调整。if (arr[child] arr[parent]) {Swap(arr[child], arr[parent]);}else {break;}}
}//向下调整算法父求子父*2 1/2
void AdjustDown(HPDataType* arr, int parent, int n) {//n 是数组的大小int child parent*2 1;//假设左孩子最小while (child n)//孩子不能超过数组的界限{//找左右孩子中找最小的if (child 1 n arr[child] arr[child 1])//child 1 n检查是否有右孩子没有右孩子就不进入{child;}if (arr[child] arr[parent])//父比子大交换因为是形成小堆最小的要在堆顶{Swap(arr[child], arr[parent]);parent child;child parent * 2 1;}else{break;}}
}//入堆
void HPPush(HP* php, HPDataType x) {assert(php);//检查空间是否不足if (php-capacity php-size) {//如果堆空间为0,扩容int newcapacity php-capacity 0 ? 4 : php-capacity * 2;HPDataType* ret (HPDataType*)realloc(php-arr, newcapacity*sizeof(HPDataType));if (ret NULL) {perror(relloc);exit(1);}php-arr ret;php-capacity newcapacity;}//在当前位置入堆php-arr[php-size] x;AdjustUp(php-arr,php-size);//堆的有效个数1,为什么要到最后才更新堆的有效个数//因为向上调整法需要传递新插入结点的下标插入堆后下标刚好是size php-size;}//出堆
void HPPop(HP* php) {//出堆出的是堆顶但是不能直接删除堆顶这样堆就混乱了//将堆顶元素和顶底交换然后删除堆底//最后向上调整算法向上调整assert(php);Swap(php-arr[0], php-arr[php-size - 1]);-- php-size;AdjustDown(php-arr, 0, php-size);}//判空
bool HPEmpty(HP* php) {assert(php);return php-size0;
}//取堆顶
HPDataType HPTop(HP* php)
{assert(php php-size);return php-arr[0];
}
