1. 树

1.1 树的概念与结构

树是⼀种非线性的数据结构，它是由 n（n>=0） 个有限结点组成⼀个具有层次关系的集合。把它叫做树是因为它看起来像⼀棵倒挂的树，也就是说它是根朝上，而叶朝下的。

• 有⼀个特殊的结点，称为根结点，根结点没有前驱结点。

• 除根结点外，其余结点被分成 M(M>0) 个互不相交的集合 T1、T2、……、Tm ，其中每⼀个集合 Ti(1 <= i <= m) 又是⼀棵结构与树类似的子树。每棵子树的根结点有且只有⼀个前驱，可以有 0 个或多个后继。因此，树是递归定义的。

 树形结构中，子树之间不能有交集，否则就不是树形结构。

非树形结构：

1.2树相关术语

 

1.3 树的表示

1.4 树形结构实际运用场景

2. 二叉树

2.1 概念与结构

 

第一个是空树（度为0），第二个叫只有根节点的二叉树，第三个叫做只有左子树的二叉树，第四个叫做只有右子树的二叉树，第五个叫做左右子树都存在的二叉树。

2.2 特殊的二叉树

2.2.1 满二叉树

 

3. 实现顺序结构二叉树

3.1 堆的概念与结构

堆具有以下性质：

• 堆中某个结点的值总是不大于或不小于其父结点的值；

• 堆总是⼀棵完全二叉树。

• 小堆堆顶是堆最小值

• 大 堆堆顶是堆最大值

•  存储在数组中的元素不一定是有序的 

//定义堆的结构——数组    堆的底层是使用顺序结构数组来实现的
typedef int HPDataType;
typedef struct Heap
{
    HPDataType* arr;
    int size;//有效的数据个数
    int capacity;//空间大小
}HP;

//堆的初始化

void HPInit(HP* php);

堆的销毁
void HPDestroy(HP* php);

堆数据的插入
void HPPush(HP* php, HPDataType x);

//判断链表是否为空

//判断空间是否足够

实现到堆的数据插入之后，不确定是不是真的符合大、小堆存储，这时候就要进行堆的向上调整算法。在这之间，还要用到两个变量交换的函数Add。（只需要比较父结点和左孩子结点，若父结点大于左孩子结点，就交换位置）。

接下来是出堆，而出堆指的就是删除堆顶数据，当我们直接删除堆顶数据时，会导致堆乱套（后一个位置移动到前一个位置处，堆的底层是顺序表），所以不能直接删除堆顶数据。因此，我们必须采取其他的办法。

方法：

最后一个结点的数据和堆顶数据交换，这时让size--；而堆顶数据（交换后为最后一个结点）能直接被删除，而删除后的堆顺序不一定符合大、小堆，所以我们要用到向下调整算法。

//去堆顶
void HPPop(HP* php);

在出堆中，我们必须要保证父结点的值和左右孩子中最小的值去交换（向下调整算法）。

//出堆顶
HPDataType HPTop(HP* php);

//打印元素判断代码是否正确

附源代码： 

Heap.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//定义堆的结构——数组    堆的底层是使用顺序结构数组来实现的
typedef int HPDataType;
typedef struct Heap
{
    HPDataType* arr;
    int size;//有效的数据个数
    int capacity;//空间大小
}HP;

void HPInit(HP* php);
void HPDestroy(HP* php);
void HPPush(HP* php, HPDataType x);
//去堆顶
void HPPop(HP* php);
//判空
bool HPEmpty(HP* php);
//出堆顶
HPDataType HPTop(HP* php);

void Swap(int* x, int* y);

 Heap.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
void HPInit(HP* php)
{
    assert(php);
    php->arr = NULL;
    php->capacity = php->size = 0;
}

void HPDestroy(HP* php)
{
    assert(php);
    if (php->arr)
    {
        free(php->arr);
    }
    php->arr = NULL;
    php->capacity = php->size = 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)//不需要等于，child只要走到根节点的位置，根节点没有父节点不需要交换
    {
        if (arr[child] < arr[parent])
        {
            Swap(&arr[parent], &arr[child]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            break;
        }
    }
}
void HPPush(HP* php, HPDataType x)
{
    assert(php);
    //判断空间是否足够
    if (php->capacity == php->size)
    {
        //扩容
        int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
        HPDataType* tmp = (HPDataType*)realloc(php->arr, newCapacity * sizeof(HPDataType));
        if (tmp == NULL)
        {
            perror("realloc fail!");
            exit(1);
        }
        php->arr = tmp;
        php->capacity = newCapacity;
    }
    php->arr[php->size] = x;
    AdjustUp(php->arr, php->size);
    php->size++;
}
void AdjustDown(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[parent] > arr[child])
        {
            Swap(&arr[child], &arr[parent]);
            parent = child;
            child = 2 * parent + 1;
        }
        else
        {
            break;
        }
    }
}

void HPPop(HP* php)
{
    assert(php && php->size);
    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->size == 0;
}
HPDataType HPTop(HP* php)
{
    assert(php && php->size);//堆顶的元素不能为空
    return php->arr[0];
}

text.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
void text01()
{
    HP hp;
    HPInit(&hp);
    int arr[] = { 17,20,10,13,19,15 };

    for (int i = 0; i < 6; i++)
    {
        HPPush(&hp, arr[i]);
    }
    while (!HPEmpty(&hp))
    {
        printf("%d ", HPTop(&hp));
        HPPop(&hp);
    }
    HPDestroy(&hp);
}
int main()
{
    text01();
    return 0;
}