怎么建淘宝客网站,做设计怎么进公司网站,网络推广培训班4800块钱贵吗,高端的网站建设怎么做目录 一.树的概念
二、二叉树
1.二叉树的概念
2.特殊类型的二叉树
3.二叉树的性质
4.二叉树存储的结构
三、堆
1.堆的概念
2.堆的实现
Heap.h
Heap.c 一.树的概念 注意#xff0c;树的同一层中不能有关联#xff0c;否侧就不是树了#xff0c;就变成图了#xff…目录 一.树的概念
二、二叉树
1.二叉树的概念
2.特殊类型的二叉树
3.二叉树的性质
4.二叉树存储的结构
三、堆
1.堆的概念
2.堆的实现
Heap.h
Heap.c 一.树的概念 注意树的同一层中不能有关联否侧就不是树了就变成图了例如 由于B和C存在关联这就不是树了。
有关树的一些重要概念 二、二叉树
1.二叉树的概念
二叉树由一个根节点加上两棵别称为左子树和右子树的二叉树组成
它具有两个特点不存在度大于2的节点子树有左右之分次序不能颠倒故二叉树是有序树 各类型二叉树集合 2.特殊类型的二叉树
满二叉树所有非叶子节点都有两个子节点且所有叶子节点都在同一层
完全二叉树除了最后一层每一层都是满的且最后一层的叶子节点都尽可能靠左排列
二叉排序树左子树所有节点的值小于根节点的值右子树所有节点的值大于根节点的值且左右子树也分别是二叉排序树 3.二叉树的性质
1 对于具有n个节点的完全二叉树如果按照从上到下从左到右的顺序对所有节点从0开始编号则序号为i的节点有其双亲节点序号为i-1/2其左孩子节点序号为i*21,右孩子节点序号为i*22,注意i*21和i*22要小于n,合法性
2规定根节点层数为1具有n个节点的满二叉树深度为hlog2(n1)
(3)规定根节点层数为1第i层最大节点数为2^(i-1)
(4)规定根节点层数为1深度为h的二叉树的最大节点数为2^h-1
4.二叉树存储的结构
分为顺序存储结构和链式存储结构其中用顺序存储结构来实现完全二叉树就是接下来重点介绍的堆。
链式存储用链表来表示一棵二叉树即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。
顺序存储顺序结构存储就是使用数组来存储一般使用数组只适合表示完全二叉树因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组在逻辑上是一颗二叉树。
三、堆
1.堆的概念
堆可以看作一种特殊类型的完全二叉树分为大堆和小堆根节点最大的称为大堆根节点最小的称为小堆。
大堆谁大谁当爹但兄弟间无绝对大小关系
小堆谁小谁当爹但兄第间无绝对大小关系
2.堆的实现
升序建大堆
降序建小堆
接下来给出建小堆的代码实现 Heap.h #includestdlib.h
#includeassert.h
#includestdio.h
#includestdbool.htypedef int HDataType;
typedef struct Heap
{HDataType* arr;int size;int capacity;
}Heap;//堆的初始化
void HeapInit(Heap* obj);
// 堆的插入
void HeapPush(Heap* obj, HDataType x);
// 堆的删除
void HeapPop(Heap* obj);
// 取堆顶的数据
HDataType HeapTop(Heap* obj);
// 堆的数据个数
int HeapSize(Heap* obj);
// 堆的判空
bool HeapEmpty(Heap* obj);
// 堆的销毁
void HeapDestroy(Heap* obj); Heap.c #includeHeap.hvoid HeapInit(Heap* php)
{php-capacity php-size 0;php-arr NULL;
}//扩容
void Exp(Heap* obj)
{if (obj-size obj-capacity){int new_capeccity obj-capacity 0 ? 4 : obj-capacity * 2;HDataType* tem (HDataType*)realloc(obj-arr, sizeof(HDataType) * new_capeccity);if (tem NULL){assert(realloc);}obj-arr tem;obj-capacity new_capeccity;}
}//交换
void Swap(HDataType* child, HDataType* parent)
{HDataType tem *child;*child *parent;*parent tem;
}//向上调整
//这里假设是小堆进行调整
//如果是大堆将if处改为大于号即可
void UpAdjust(HDataType* p,int child)
{//通过计算找父母HDataType parent (child - 1) / 2;while (child 0){if (p[child] p[parent]){//交换Swap(p[child], p[parent]);//交换后将parent的位置给给child继续计算下一个parentchild parent;//把父母给孩子parent (child - 1) / 2;//得到新的父母}else{break;}}
}//插入
//先向堆尾插入元素再根据大堆还是小堆向上调整
void HeapPush(Heap* obj,HDataType x)
{assert(obj);Exp(obj);obj-arr[obj-size] x;obj-size;//这个时候我们需要向上UpAdjust(obj-arr, obj-size - 1);
}//向下调整
//这里假设是小堆
//如果是大堆将两个if处改为大于号即可
void DownAdjust(HDataType* p,int n,int parent)
{//计算出左孩子int child parent * 2 1;while (child n){if (child 1 n p[child 1] p[child]) {//如果右儿子小于左儿子直接到右儿子的位置child;//child1n是为了避免越界访问因为每次算出的是左孩子堆尾不一定是右孩子}if (p[child] p[parent])//如果childparent就交换,要把小的往上走{//这边操作一样算法不同Swap(p[child], p[parent]);parent child;//把孩子给父母child parent * 2 1;//得到新的孩子}else{break;}}
}//删除堆顶元素
//这里是小堆删的实际是最小元素
void HeapPop(Heap* obj)
{assert(obj);assert(obj-arr);assert(obj-size 0);//堆内无元素则不存在删的问题//1.先交换堆顶和堆尾的元素避免中间节点之间关系全部混乱Swap(obj-arr[0], obj-arr[obj-size - 1]);//2.删obj-size--;//3.这里我们假设的是小堆而当前交换后显然不是小堆故向下调整将堆中次小元素调到堆顶DownAdjust(obj-arr, obj-size, 0);
}//获取堆顶元素
HDataType HeapTop(Heap* obj)
{assert(obj);return obj-arr[0];
}//获取堆中数据的个数
int HeapSize(Heap* obj)
{assert(obj);return obj-size;
}//判空
bool HeapEmpty(Heap* obj)
{assert(obj);return obj-size 0;
}//堆的销毁
void HeapDestroy(Heap* obj)
{assert(obj);assert(obj-arr);free(obj-arr);obj-arr NULL;obj-capacity obj-size 0;
} test.c cl:以上代码和顺序表的实现是很相似的最大区别是堆独有的特点也就是建堆堆尾插入元素时进行向上调整堆顶删除元素时进行向下调整这两步是最关键的算法是保证堆的特点大小堆)的关键。
