班级网站建设规划书,百度推广移动端网站,农村电子商务专业就业方向,海纳网站建设前言#xff1a;前面学习了顺序表#xff0c;队列#xff0c;栈#xff0c;链表#xff0c;我们知道他们都是一种线性表#xff0c;是一种线性结构#xff0c;而除此之外#xff0c;仍有许多我们还没认识的结构#xff0c;比如树形结构#xff0c;不同于线性结构前面学习了顺序表队列栈链表我们知道他们都是一种线性表是一种线性结构而除此之外仍有许多我们还没认识的结构比如树形结构不同于线性结构树形结构就如同他的名字结构相对更加复杂是一种倒着的树的数据结构。
目录
1什么是树
2.树的相关概念
3.树的定义
4.二叉树 特殊的二叉树
2.二叉树的存储方式
5.堆
结构体定义与函数接口
堆的初始化
堆的销毁
入堆
向上调整算法
向下调整算法
出堆 1什么是树
树是一种非线性的数据结构它是由n(n0)个有限节点组成一个具有层次关系的集合把它叫做书是因为它看起来像一颗倒挂着的树个人感觉也像树根部的形状也就是他是根朝上叶子朝下。
树结构拥有自己的一些独特性质
.有一个特殊的节点称为根节点根节点没有前驱节点
.除根结点外其余节点被分为MM0个互不相交的集合T1,T2,......Tm其中每个集合我们可以认为也是一个类似主树的子树每个子树的节点有且只有一个前驱可以有0或多个后继节点。
.树是递归定义的因为它的套娃结构大树里住着小树。
如下图一根秃了的倒着的树与树结构的对比 注意树型结构里面是不能出现子树相交的
不仅仅对于树形结构是这样树也不能出现一个枝干长到另一个枝干上可能存在变异。 2.树的相关概念
树的某些相关概念是以人类的血缘关系为样例所命名 我们知道树是一种非线性的数据结构它是由nn0个结点的有限集合。
当n0时称为空树。在任何一棵非空树中1. 有且只有一个特定的称为 根root 的结点2. 当n1时其余结点可分为mm0个 互不相交 的有限集其中每一个集合又是一棵树并且成为 根的子树subtree 。
结点的度结点拥有的子树数称为结点的 度Degree如上图D的度为3A度为2.
树的度 是树内各结点的度的最大值。如D为3
度为0的结点成为 叶节点Leaf 或者 终端结点 除根结点外分支结点也称为 内部结点 。如上图的G H I。
结点子树的根称为该结点的 孩子Child。如A的孩子B,C
相应的该结点称为孩子的 双亲Parent 。如D的双亲为B
同一个双亲之间的孩子之间互称为 兄弟Sibling。B与C互为兄弟
结点的 祖先 是指从根到该结点所经历的所有结点.
反之以该结点为根的子树中的任意一结点称为该节点的 子孙 。
树的层次从根开始根为第一层根的节点为第二层以此类推。
树的深度树中结点的最大层次称为树的 深度Depth 或者高度根据树中结点是否可以交换分为有序树和无序树。
堂兄弟节点双亲在同一层的节点互为堂兄弟。如D,E。
森林 是指的多棵互不相交的树。
路径和路径长度 树中两个结点之间的 路径 是由这两个结点之间所经过的结点序列构成的而 路径长度 是路径上所经过的 边的个数 。
3.树的定义
因为树有很多节点按照之前的链表他们定义结点的方法没接触前树我们可能这样定义
struct TreeNode
{int data;struct TreeNode*child1;struct TreeNode*child2;
//......
}
但其实不太可能。人们总结了许多定义树的结构的方法
1.如果明确了树的度那么可以定义。根据树的度来定义节点个数但是不太能表现树
2.用顺序表来存放孩子。
struct TreeNode
{int data;Seqlist childArr;
}
3.双亲表示法。每个位置只存储该节点的父节点用数组存放双亲的下标。
并查集这里就是只存储父亲的下标。 4.左孩子右兄弟方法比较牛的一种方法也是一种较优的方法每一个节点只存放他的第一个孩子节点和下一个兄弟节点。
struct TreeNode{struct TreeNode*firstchid;//第一个孩子节点struct TreeNode*nextbrother;//指向下一个兄弟节点int data;//节点的数据域} 对于森林一般是文件系统结构。
4.二叉树
概念一种特殊的树的结构一个二叉树是节点的一个有限集合
1.要么为空
2.有一个根节点加上两个子树左右子树组成。如图 我们可以看到
1.二叉树不存在度大于2的节点
2.二叉树有左右之分左边的节点叫左孩子右边的节点叫右孩子次序不能颠倒因此是一个有序树。 特殊的二叉树
1.满二叉树
概念一个二叉树如果每层结点数都达到最大值那么这个树就是满二叉树。也就是说如果一个二叉树的层数为K那么总结点数为2^k-1),等比求和公式可推导出第N层的节点数为2^(n-1). 2.完全二叉树
概念相对于满二叉树的最后一行最后一行不全满且结点依次从左到右就是一个完全二叉树。
若一个完全二叉树的层数为k那么他的k-1层以上的每一层都是满的。
满二叉树是一种特殊的完全二叉树。 若深度为h,节点范围【2^(h-1),2^h-1】.
2.二叉树的存储方式
1.可用二叉链表来表示有的地方是三叉链表多了一个结点指向前面的双亲。 2.可用数组来表示。 用数组存放右几个优点 对于这种存储比较适合完全二叉树来存储。因为若有一个双亲没有孩子节点对于数组这种下表表示双亲存在问题。
5.堆
知道以上的存储方法对于完全二叉树有一个叫做堆的结构堆本质就是一个完全二叉树
堆分两种1.大堆 2.小堆
除了是完全二叉树大堆需满足任何一个双亲都大于等于孩子对于小堆任何一个双亲都小于等于孩子。 我们实现堆就用数组来实现的这里以实现小堆为例
结构体定义与函数接口
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h
typedef int HPDATAtype;
typedef struct Heap
{HPDATAtype *a;int size;int capacity;
}HP;void Heapinit(HP* f);
void Heapdestroy(HP* f);
void Heappop(HP* f);
void Heappush(HP* f , HPDATAtype x);堆的初始化
void Heapinit(HP* f)
{//初始有4个空间assert(f);f-a NULL;f-size 0;f-capacity 0;
}
堆的销毁
void Heapdestroy(HP* f)
{assert(f-a);free(f-a);f-a NULL;
}
入堆
void Heappush(HP* f, HPDATAtype x)
{assert(f);if (f-capacity f-size){int newcapacity f-capacity 0 ? 4 : f-capacity*2;HPDATAtype* newnode (HPDATAtype*)malloc(newcapacity);if (newnode NULL){perror(扩容失败\n);return;}f-a newnode;f-capacity f-capacity*2;}f-a[f-size] x;f-size;//向上调整算法Adjustup(f-a, f-size - 1);//向下调整算法//Adjustdown(f-a, f-size - 1);
}
在这里在入堆之后也就是元素赋值到数组之后根据你对数组的调整也就是所说的向上调整算法和向下调整算法决定是小堆还是大堆。
向上调整算法
我们这里通过对树所对应的数组元素的关系寻找父亲。
void Adjustup(HPDATAtype*a, int child)
{//根据孩子zhaofuqinint parent (child - 1) / 2;while (child0){if ( a[child]a[parent]){HPDATAtype p a[child];a [child] a[parent];a[parent]p;child parent;parent (child - 1) / 2;}else {break;}}
}
向下调整算法
void Adjustdown(HPDATAtype* a, int child)
{//根据孩子找父亲int parent (child - 1) / 2;while (child 0){if (a[child] a[parent]){int tmp a[child];a[child] a[parent];a[parent] tmp; child parent;parent (child - 1) / 2;}else{break;}}}
出堆
出堆就是最后一个元素换到第一个元素在size--之后在进行调整。
void Heappop(HP* f){assert(f);//堆顶元素出堆,最小元素出堆assert(f-size);int tmp f-a[0];f-a[0] f-a[f-size - 1];f-a[f-size - 1] tmp;f-size--;//向上调整for (int i 0; i f-size; i){Adjustup(f-a, i);}
};
堆的应用
优先级队列的实现 堆排序算法 获取特定范围的值
