目录
一:什么是树
【1】树的概念
【2】树的另外几个重要概念
【3】树的几种表示方法
二:什么是二叉树
【1】概念以及特点
【2】两种特殊的二叉树
【3】二叉树的性质
【4】二叉树的两种存储方式
三:堆的实现
一:什么是树
【1】树的概念
我们前面所学的顺序表，链表都属于线性结构，而树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
图解：
(1) 树有一个特殊的节点，叫根节点，在图中为结点A。
(2)除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以 有0个或多个后继。
(3)父子结点：例如A是B,C,D的父节点，而E，F是B的子节点。
(4)叶结点：没有子节点的结点，例如E,F,C,G,H。
注意：树的子树是不相交的，除了根结点以外别的结点有且只有一个父节点。
【2】树的另外几个重要概念
图解：
【3】树的几种表示方法
(1)利用顺序表存子节点的地址(结构复杂)
(2) 已经说明了树的度(最大结点的度)，设置一个指针数组来存储子节点的地址
(3)结构体数组存储
(4)左孩子右兄弟表示法(比较常用，结构也比较简单，逻辑相对清晰)
二:什么是二叉树
【1】概念以及特点
概念:
一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。
特点:
1. 每个结点最多有两棵子树，即二叉树不存在度大于2的结点。
2. 二叉树的子树有左右之分，其子树的次序不能颠倒。
【2】两种特殊的二叉树
1. 满二叉树：
所有叶子节点都在最后一层
所有分支节点都有两个孩子
2. 完全二叉树：
假设这个二叉树有N层，前N-1层必须满
最后一层可以不满，但是必须左向右连续
【3】二叉树的性质
1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个结点。
2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h- 1。
3. 对任何一棵二叉树, 如果度为0其叶结点个数为n0, 度为2的分支结点个数为 n2,则有n0＝n2＋1。
4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=LogN。
【4】二叉树的两种存储方式
(1)顺序结构存储(数组)
顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。
(2)链式结构存储
用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。
通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。
链式结构又分为二叉链和三叉链，目前一般都是二叉链，红黑树等高阶数据结构会用到三叉链。
三:堆的实现
堆是用数组实现的二叉树，并且一般用来实现完全二叉树。
堆分为大堆和小堆
大堆：父亲>=孩子
小堆：孩子>=父亲
本文实现的是大堆
堆的实现和顺序表类似，这里就不展开细讲，只讲主要的接口实现。
附上顺序表链接:https://blog.csdn.net/2301_76269963/article/details/129352041?spm=1001.2014.3001.5501
插入数据
(1)判断扩容，和顺序表一致。
(2)存储数据，和顺序表一致。
(3)在进行数据插入后我们要保证插入以后还是大堆，就必须进行父子关系的调整。
在考虑调整之前，我们观察一下父亲下标和孩子下标的关系
我们可以发现这样一个规律
父亲下标=（孩子下标-1）/2。
我们根据这个规律来设计调整函数，如果要插入的数据大于父亲，就调换两者，一直到小于父亲或者成为了根部节点。
代码：
全部代码：
Heap.h(必要头文件的包含，函数和结构体声明)
#pragma once#include <stdio.h>#include <assert.h>#include <stdlib.h>typedef int HPDataType;typedef struct Heap{//存储数据HPDataType* a;//有效数据个数int size;//容量int capacity;}HP;//初始化void HeapInit(HP* hp);//调整函数void AdjustUp(HPDataType* a,int child);//插入数据void HeapPush(HP* hp, HPDataType x);//打印数据void HeapPrint(HP* hp);//删除数据void HeapPop(HP* hp);
Heap.c(接口实现)
#define _CRT_SECURE_NO_WARNINGS 1#include "Heap.h"//初始化void HeapInit(HP* hp){//断言，不能传空的结构体指针assert(hp);hp->a = NULL;//初始化size和容量都为0hp->size = hp->capacity = 0;}//调整函数void AdjustUp(HPDataType* a, int child){//断言，不能传空指针assert(a);//找到父结点的下标int parent = (child - 1) / 2;//循环，以child到树根为结束条件while (child > 0){//如果父结点比child下，交换并更新if (a[child] > a[parent]){HPDataType tmp = a[child];a[child] = a[parent];a[parent] = tmp;child = parent;parent = (child - 1) / 2;}//如果父结点比child大，跳出循环else{break;}}}//插入数据void HeapPush(HP* hp, HPDataType x){if (hp->size == hp->capacity){//判断扩容多少int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;//扩容HPDataType* tmp =(HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity);//更新hp->capacity = newcapacity;hp->a = tmp;}//存储数据hp->a[hp->size] = x;hp->size++;//进行调整AdjustUp(hp->a, hp->size-1);}//打印数据void HeapPrint(HP* hp){//断言，不能传空的结构体指针assert(hp);int i = 0;for (i = 0; i < hp->size; i++){printf("%d ", hp->a[i]);}printf("\n");}//删除数据void HeapPop(HP* hp){//断言，不能传空的结构体指针assert(hp);//如果为空，不能删除，避免数组越界if (hp->size == 0)return ;//不为空，直接将size-1就行hp->size--;}
text.c(测试)
#define _CRT_SECURE_NO_WARNINGS 1#include "Heap.h"void text1(){HP hp;HeapInit(&hp);HPDataType a[] = { 70,30,56,25,15,10,75,100 };int i = 0;for (i = 0; i < sizeof(a) / sizeof(a[0]); i++){HeapPush(&hp, a[i]);}HeapPrint(&hp);}int main(){text1();}