树、二叉树与堆

一、树的基本知识

二、二叉树的基本知识

三、堆

   堆的基本知识

   初始准备

   初始化和销毁堆

   堆为空

   向上和向下调整堆

   插入和删除数据

   取出堆顶数据

   堆的数据个数

   建堆时间复杂度

   全部代码

   堆排序

四、TOP-K问题

五、二叉树的链式存储

一、树的基本知识

树是一种非线性结构，像是一颗倒挂着的树，根朝上，叶朝下，最上面的节点称为根节点，如下图的A

注意：树形结构中，子树之间不能有交集，否则就不是树形结构，如下图

** **

节点的度：一个节点含有的子树的个数称为该节点的度

如第一张图的A，有2个子树，度就为2

叶节点或终端节点：度为0的节点称为叶节点

如第一张图的D、E、F、G都是叶节点

双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点

如第一张图的C就是G的父节点

孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点

如第一张图的B、C都是A的孩子节点

树的高度或深度：树中节点的最大层次

如将根节点视为第一层，树的高度就为3

节点的祖先：从根到该节点所经分支上的所有节点

如第一张图的A是所有节点的祖先

树的表示方法

最常用的是孩子兄弟表示法

根只要指向第一个节点，剩下的节点就可以依次连接，如下图

二、二叉树的基本知识

概念：由一个根节点加上两棵别称为左子树和右子树的二叉树组成(或者为空)，如下图

二叉树特点：

不存在度大于2的节点

二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

特殊的二叉树

完全二叉树

前h-1层都有左右节点(根节点除外)，第h层从左到右是连续存储的，不存在有右节点，没有左节点的情况

满二叉树

每层都有左右节点，所以满二叉树是特殊的完全二叉树

二叉树的性质

若规定根节点的层数为1，则一棵非空二叉树的第i层上最多2^(i-1)个节点

当其为满二叉树时，第i层节点数最多，即1、2、4...2^(i-1),是一个等比数列

若规定根节点的层数为1，则深度为h的二叉树的最大节点数是2^h-1

当其为满二叉树时，有最大节点数，即1、2、4...2^(h-1),是等比数列，求和为2^h-1

对任何一棵二叉树, 如果度为0其叶结点个数为 , 度为2的分支结点个数为 ,则有n0＝n2＋1

若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=log2(n+1)

二叉树的存储结构

可以用顺序结构和链式结构两种来存储

不过顺序结构只适用于完全二叉树，普通二叉树存储时，可能会造成大量空间浪费

如上图，存储时，有缺失，则必须空出来，否则会打乱结构

假设parent是父亲节点在数组中下标

leftchild = parent * 2 + 1

rightchild = parent * 2 + 2

假设孩子的下标是child，不管是左孩子还是右孩子

**parent = （child - 1) / 2 **

三、堆

堆的基本知识

概念：

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆

性质：

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

堆总是一棵完全二叉树

小堆：

大堆：

初始准备

为了存储的数据类型能够便于修改，所以用typedef 将其数据类型名修改

这里采用数组结构来存储堆，首先创建一个结构体，有3个成员，第一个是数组的起始地址(指针)，第二个是有效数据个数，第三个是已经开辟的数组大小(容量)，用typedef将其类型名简化

打印堆的数据

按照下标访问即可，就和静态数组一样

交换两个数

由于后面的向上和向下调整都得用到交换，所以用一个函数来实现，想使用时只需调用即可

初始化和销毁堆

将其后两个成员置为0，将指针置为NULL即可

销毁堆和初始化堆类似，只是要将开辟的空间用free释放

** 堆为空**

** 如果没有数据则就为空，这里采用bool类型，同时要引用头文件stdbool.h**

** 向上和向下调整堆**

** 以建立大堆为例，向上调整**

** **

如上图，如果子节点数据比父节点数据大，两者就交换，且把父节点下标赋值给孩子，父节点下标为（child-1）/ 2，否则就直接跳出循环

不能用parent>=0作循环判断条件,当child = 0时，parent = 0循环还是会继续，然后下一步才会跳出循环，可是并不算正常退出

2个参数，一个数组的起始地址，另一个是孩子节点的下标

以建立大堆为例，向下调整

首先得判断左右孩子节点数据哪个更大，父节点与大的那个交换，同时右孩子节点下标不能越界

再判断孩子节点数据是否比父节点数据大，大就交换，且将孩子节点下标赋值给父节点，孩子节点为2 * parent + 1，否则就跳出循环

**循环判断条件为孩子节点下标小于有效数据个数 **

有3个参数，一个是数组的起始地址，一个是有效数据个数，还有一个是父节点下标

** **

注意：对于向下调整，左右子树必须是一个堆，才能调整

插入和删除数据

插入数据时，首先得判断是否还有空间，没有就增容，同时要判断增容是否失败

插入数据后，有效数据个数要+1，然后再向上调整，保证是大堆或者小堆

删除堆顶数据后，不能挪动数据，否则会打乱堆结构

首先得判断堆是否为空

然后得交换堆顶数据与最后一个数据

再删除最后一个数据，即有效数据个数-1即可

最后还要向下调整堆，保证是大堆或者小堆

取出堆顶数据

首先判断堆是否为空，然后再取数据

堆的数据个数

全部代码

//头文件
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<time.h>

typedef int DataType;

typedef struct Heap
{
    DataType* a;
    int size;
    int capacity;
}HP;

//初始化堆
void HeapInit(HP* hp);
//销毁堆
void HeapDestroy(HP* hp);
//打印
void HeapPrint(HP* hp);
//交换2个数
void swap(DataType* px, DataType* py);
//插入数据进堆
void HeapPush(HP* hp, DataType x);
//删除数据出堆
void HeapPopTop(HP* hp);
//向上调整
void HeapAdjustUp(DataType* a,int child);
//向下调整
void HeapAdjustDown(DataType* a,int n,int parent);
//取出堆顶数据
DataType HeapTop(HP* hp);
//堆为空
bool HeapEmpty(HP* hp);
//堆的大小
int HeapSize(HP* hp);

//定义文件
#include"Heap.h"

void HeapInit(HP* hp)
{
    assert(hp);
    hp->a = NULL;
    hp->size = 0;
    hp->capacity = 0;
}

void HeapDestroy(HP* hp)
{
    assert(hp);
    free(hp->a);
    hp->a = NULL;
    hp->size = 0;
    hp->capacity = 0;
}

void HeapPrint(HP* hp)
{
    assert(hp);
    assert(!HeapEmpty(hp));
    int i = 0;
    for (i = 0; i < hp->size; i++)
    {
        printf("%d ", hp->a[i]);
    }
    printf("\n");
}

void swap(DataType* px, DataType* py)
{
    DataType* tmp = *px;
    *px = *py;
    *py = tmp;
}

void HeapPush(HP* hp, DataType x)
{
    assert(hp);
    if (hp->size == hp->capacity)
    {
        int newcapacity = hp->capacity == 0 ? 4 : 2 * hp->capacity;
        DataType* tmp = (DataType*)realloc(hp->a, sizeof(DataType) * newcapacity);
        if (tmp == NULL)
        {
            printf("realloc fail\n");
            exit(-1);
        }
        hp->a = tmp;
        hp->capacity = newcapacity;
    }
    hp->a[hp->size] = x;
    hp->size++;
    HeapAdjustUp(hp->a,hp->size-1);
}

void HeapAdjustUp(DataType* a,int child)
{
    assert(a);
    int parent = (child - 1) / 2;
    while (child > 0)
    {
        if (a[child] < a[parent])
        {
            swap(&a[child], &a[parent]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            break;
        }
    }
}

bool HeapEmpty(HP* hp)
{
    assert(hp);
    return hp->size == 0;
}

void HeapPopTop(HP* hp) 
{
    assert(hp);
    assert(!HeapEmpty(hp));
    swap(&(hp->a[0]), &(hp->a[hp->size - 1]));
    hp->size--;
    HeapAdjustDown(hp->a, hp->size, 0);
}

void HeapAdjustDown(DataType* a, int n, int parent)
{
    assert(a);
    int child = 2 * parent + 1;
    while (child < n)
    {
        if (child + 1 < n && a[child + 1] < a[child])
        {
            child++;
        }
        if (a[child] < a[parent])
        {
            swap(&a[child], &a[parent]);
            parent = child;
            child = 2 * parent + 1;
        }
        else
        {
            break;
        }
    }
}

DataType HeapTop(HP* hp)
{
    assert(hp);
    assert(!HeapEmpty(hp));
    return hp->a[0];
}

int HeapSize(HP* hp)
{
    assert(hp);
    return hp->size;
}

测试文件
void test1()
{
    HP hp;
    HeapInit(&hp);
    HeapPush(&hp, 17);
    HeapPush(&hp, 53);
    HeapPush(&hp, 62);
    HeapPush(&hp, 37);
    HeapPush(&hp, 65);
    HeapPush(&hp, 25);
    HeapPrint(&hp);
    int sz = HeapSize(&hp);
    printf("%d\n", sz);

    int Top = HeapTop(&hp);
    HeapPopTop(&hp);
    printf("%d\n", Top);
    sz = HeapSize(&hp);
    printf("%d\n", sz);

    Top = HeapTop(&hp);
    HeapPopTop(&hp);
    printf("%d\n", Top);
    sz = HeapSize(&hp);
    printf("%d\n", sz);

    Top = HeapTop(&hp);
    HeapPopTop(&hp);
    printf("%d\n", Top);
    sz = HeapSize(&hp);
    printf("%d\n", sz);
    HeapDestroy(&hp);
}
int main()
{
    test1();
    return 0;
}

建堆时间复杂度

如上图，把根节点所在层看为第一层，这里用满二叉树，方便计算，多几个节点不影响结果

采用的方法是错位相减法

堆排序

首先创建一个数组，并且赋值，再求数组数据个数

这里排升序，建大堆

然后再先将堆顶数据与最后一个数据交换，再有效数据-1，最后向下调整

最后打印数据即可

四、TOP-K问题

从n个数据中取出k个最大或者最小的数据，一般k远小于n

首先创建一个1000个数的数组，并且都赋值，其中有9个都大于10000

这里以取出前k个最大数据为例，建小堆

后面991个数，满足大于堆顶数据就删除堆顶数据，重新调整，换成新的堆顶数据

这里无论是插入数据还是删除堆顶数据，以及方法二的向下调整都是建小堆

五、二叉树的链式存储

二叉树是：

空树

非空：根节点，根节点的左子树、根节点的右子树组成的。

二叉树定义是递归式的

二叉树的遍历有：前序/中序/后序的递归结构遍历

前序遍历——访问根结点的操作发生在遍历其左右子树之前

**如上图，15 17 24 19 20 36 35 13 24 **

中序遍历——访问根结点的操作发生在遍历其左右子树之中（间）

如上图，19 24 20 17 36 15 13 35 24

后序遍历——访问根结点的操作发生在遍历其左右子树之后

如上图，19 20 24 36 17 13 24 35 15

递归实现前序遍历，下图是递归展开图，为了便于画图，所以减少了数据

前中后序遍历全部代码

//创建节点
BN* BuyBinaryNode(DataType x) 
{
    BN* newnode = (BN*)malloc(sizeof(BN));
    if (newnode == NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    newnode->data = x;
    newnode->leftchild = NULL;
    newnode->rightchild = NULL;
    return newnode;
}

//前序遍历
void prevorder(BN* bn)
{
    if (bn == NULL)
    {
        return NULL;
    }
    printf("%d ", bn->data);
    prevorder(bn->leftchild);
    prevorder(bn->rightchild);
}
//中序遍历
void inorder(BN* bn)
{
    if (bn == NULL)
    {
        return;
    }
    inorder(bn->leftchild);
    printf("%d ", bn->data);
    inorder(bn->rightchild);
}
//后序遍历
void postorder(BN* bn)
{
    if (bn == NULL)
    {
        return;
    }
    postorder(bn->leftchild);
    postorder(bn->rightchild);
    printf("%d ", bn->data);
}
void test3()
{
    BN* bn1 = BuyBinaryNode(15);
    BN* bn2 = BuyBinaryNode(17);
    BN* bn3 = BuyBinaryNode(35);
    BN* bn4 = BuyBinaryNode(24);
    BN* bn5 = BuyBinaryNode(36);
    BN* bn6 = BuyBinaryNode(13);
    BN* bn7 = BuyBinaryNode(24);
    BN* bn8= BuyBinaryNode(19);
    BN* bn9 = BuyBinaryNode(20);

    bn1->leftchild = bn2;
    bn1->rightchild = bn3;
    bn2->leftchild = bn4;
    bn2->rightchild = bn5;
    bn4->leftchild = bn8;
    bn4->rightchild = bn9;
    bn3->leftchild = bn6;
    bn3->rightchild = bn7;
    
    prevorder(bn1);
    //inorder(bn1);
    //postorder(bn1);
}

计算二叉树的节点个数

首先得判断根节点是否为空，为空就返回0

将所有节点都遍历一遍，为空就返回0，不为空就+1

计算二叉树叶子节点的个数

首先得判断根节点是否为空，为空就返回0

将所有节点都遍历一遍，如果左右孩子节点都为空，那么该节点就是叶子节点

计算二叉树第k层的节点个数

首先得判断根节点是否为空，为空就返回0

将根节点视为第一层，首先得判断k是否大于等于1，然后判断k是否为1，为1就返回1

可以转化成第k-1层的所有节点的左右孩子节点的总和

在二叉树中查找值为x的节点

首先得判断根节点是否为空，为空就返回空

如果等于该节点存储的数据等于x，那就返回该节点的地址，说明找到了

如果左孩子或右孩子节点等于空，那就返回空

上述都不满足，就返回空

为了避免在判断左右孩子节点是否为空，以及返回时，多次调用，所以用变量将其保存

求二叉树的高度或层数

首先得判断根节点是否为空，为空就返回0

通过判断左右子树那个大，就+1后返回哪个

为了减少函数在返回语句时的多次调用，所以用变量将其值保存起来

层序遍历

概念：自上而下，自左至右逐层访问树的结点的过程

这里得借用队列来实现

首先得判断根节点是否为空，为空则函数结束直接return

然后创建一个队列的结构体变量，并初始化，再把根节点插入队列中

然后创建一个变量，保存父节点，才能把左右孩子带进队列中

最后销毁队列即可

判断是否是完全二叉树

首先得创建一个队列的结构体变量，并初始化，然后把根节点插入队列中

然后判断保存队头节点并删除，以便能带入左右孩子节点，如果队头节点为空，就直接跳出循环

因为完全二叉树的最后一层是连续存储的，如果后面全是空，那就是完全二叉树，否则就不是

//层序遍历
void LevelOrder(BN* root)
{
    if (root == NULL)
        return;
    Queue q;
    QueueInit(&q);
    QueuePushBack(&q, root);
    while (!QueueEmpty(&q))
    {
        BN* Front = QueueTop(&q);
        QueuePopFront(&q);
        printf("%d ", Front->data);

        if (Front->leftchild)
            QueuePushBack(&q, Front->leftchild);
        if(Front->rightchild)
            QueuePushBack(&q, Front->rightchild);
    }
    printf("\n");
    QueueDestroy(&q);
}

//判断是否是完全二叉树
bool BinaryTreeComplete(BN* root)
{
    Queue q;
    QueueInit(&q);
    QueuePushBack(&q, root);
    BN* Front = NULL;
    while (!QueueEmpty(&q))
    {
        Front = QueueTop(&q);
        QueuePopFront(&q);

        if (Front == NULL)
        {
            break;
        }
        else
        {
            QueuePushBack(&q, root->leftchild);
            QueuePushBack(&q, root->rightchild);
        }
    }
    while (!QueueEmpty(&q))
    {
        Front = QueueTop(&q);
        QueuePopFront(&q);
        if (Front)
        {
            QueueDestroy(&q);
            return false;
        }
    }
    QueueDestroy(&q);
    return true;
}

二叉树销毁

首先得判断根节点是否为空，为空就return即可

然后把每个节点都遍历，自下而上的删除节点即可