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

有一个特殊的结点，称为根结点，根节点没有前驱结点

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

因此，树是递归定义的。

如下图，A为整个树的根节点。而B，C，D可以看做子树的根节点，在下面分别长出三棵子树。

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

1.2 树的相关概念

节点的度：一个节点含有的子树的个数称为该节点的度；如上图：A的为6
叶节点或终端节点：度为0的节点称为叶节点；如上图：B、C、H、I...等节点为叶节点
非终端节点或分支节点：度不为0的节点；如上图：D、E、F、G...等节点为分支节点
双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；如上图：A是B的父节点
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；如上图：B是A的孩子节点
兄弟节点：具有相同父节点的节点互称为兄弟节点；如上图：B、C是兄弟节点
树的度：一棵树中，最大的节点的度称为树的度；如上图：树的度为6
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
树的高度或深度：树中节点的最大层次；如上图：树的高度为4
堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点
节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
森林：由m（m>0）棵互不相交的树的集合称为森林；

1.3 树的表示

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。

typedef int DataType;
struct Node
{
    struct Node* _firstChild1; // 第一个孩子结点
    struct Node* _pNextBrother; // 指向其下一个兄弟结点
    DataType _data; // 结点中的数据域
};

2、二叉树概念及结构

2.1 概念

一棵二叉树是结点的一个有限集合，该集合:

或者为空
由一个根节点加上两棵别称为左子树和右子树的二叉树组成

从上图可以看出：

二叉树不存在度大于2的结点
二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树注意：对于任意的二叉树都是由以下几种情况复合而成的：

2.2现实中的二叉树：

2.3 特殊的二叉树

满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是，则它就是满二叉树。
完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K 的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。

2.4 二叉树的性质

若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有个结点.
若规定根节点的层数为1，则深度为h的二叉树的最大结点数是 .
对任何一棵二叉树, 如果度为0其叶结点个数为 , 度为2的分支结点个数为 ,则有＝＋1
若规定根节点的层数为1，具有n个结点的满二叉树的深度，h= . (ps：是log以2 为底，n+1为对数)
对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：
若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子
若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子

3.二叉树的顺序结构及实现

3.2 堆的概念及结构

如果有一个关键码的集合K = { ，，，…， }，把它的所有元素按完全二叉树的顺序存储方式存储，在一个一维数组中，并满足： <= 且 <= ( >= 且 >= ) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆的性质：

堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。

3.3 堆的实现

3.2.1 堆的数据结构和接口

#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

// 二叉树 - 数据结构
typedef int HPDataType;
typedef struct Heap
{
    HPDataType* data;        // 堆的数组存储区（数组形态）
    size_t size;            // 数据数量
    size_t capacity;        // 数据容量
}Heap;



/*
 * - 堆的接口
 */


// - 堆初始化
void HeapInit(Heap* pHead);

// - 堆销毁
void HeapDestroy(Heap* pHead);

// - 堆插入
void HeapPush(Heap* pHead, HPDataType data);

// - 堆删除
void HeapPop(Heap* pHead);

// - 向上调整小堆算法
void AdjustUp(HPDataType* data, int child);  

// - 向上调整大堆算法
void AdjustBUp(HPDataType* data, int child);   

// - 向下调整小堆算法
void AdjustDown(HPDataType* data, int size, int parent);

// - 向下调整大堆算法
void AdjustBDown(HPDataType* data, int size, int parent);

// 数据交换算法
void Swap(HPDataType* parent, HPDataType* child);  

// - 堆获取栈顶数据
HPDataType HeapGetTop(Heap* pHead);

// - 获取堆中数据个数
size_t HeapGetSize(Heap* pHead);

// - 堆打印
void HeapPrint(Heap* pHead);
// - 堆判空
bool HeapEmpty(Heap* pHead);

3.2.2 初始化

void HeapInit(Heap* pHeap)
{
    // 断言：保护形参指针。
    assert(pHeap);

    // 结构体数组、记录参数初始化。
    pHeap->data = NULL;
    pHeap->size = pHeap->capacity = 0;
}

3.2.3 堆向上调整算法

// 二叉树 - 堆插入 - 交换节点数据
void Swap(HPDataType* child, HPDataType* parent)
{
    HPDataType pTemp = *child;
    *child = *parent;
    *parent = pTemp;
}


// 二叉树 - 堆插入 - 调整顺序（小堆）
void AdjustUp(HPDataType* data, int child)
{
    // 求父节点
    int parent = (child - 1) / 2;
    // 调整多次的情况
    while (child > 0)
    {
        if (data[child] < data[parent])
        {
            Swap(&data[child], &data[parent]);
            // 交换完成，父亲的位置给孩子。
            child = parent;
            parent = (child - 1) / 2;   // 继续计算父亲的位置。
        }
        else
        {
            // 如果如果说孩子小于父亲，说明就没有必要调整顺序了。
            break;
        }
    }
}


// 二叉树 - 堆插入 - 调整顺序（大堆）
void AdjustBUp(HPDataType* data, int child)
{
    // 求父节点
    int parent = (child - 1) / 2;
    // 调整多次
    while (child > 0)
    {
        if (data[child] > data[parent])
        {
            Swap(&data[child], &data[parent]);
            child = parent;
            parent = (child - 1) / 2; // 继续找父亲节点。
        }
        else
        {
            // 如果说孩子大于父亲，就不进行交换了。
            break;
        }
    }
}

3.2.4 堆插入

// 二叉树 - 堆插入
void HeapPush(Heap* pHeap, HPDataType data)
{
    // 断言：保护形参指针。
    assert(pHeap);

    // 检查容量
    if (pHeap->size == pHeap->capacity)
    {
        // 扩容
        int newCapacity = pHeap->capacity == 0 ? 4 : pHeap->capacity * 2;
        HPDataType* pTemp = (HPDataType*)realloc(pHeap->data, newCapacity * sizeof(HPDataType));
        if (pTemp == NULL)
        {
            perror("HeapPush realloc fail!");
            exit(-1);
        }
        // 扩容成功 - 记录新容量。
        pHeap->data = pTemp;
        pHeap->capacity = newCapacity;
    }

    // 数据存入
    pHeap->data[pHeap->size] = data;
    ++pHeap->size;

    // 向上调整算法
    AdjustUp(pHeap->data, pHeap->size - 1);
}
// 最后的打印的数据是：
10 15 19 25 18 34 65 49 27 37 28   -> 与上面进行对比，是可以对上的。

3.2.5 堆向下调整算法

删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。

// 二叉树 - 堆删除 - 调整顺序（小堆）
void AdjustDown(HPDataType* data, int size, int parent)
{
    // 求出根节点（父亲）下的最小的子节点。
    int minChild = parent * 2 + 1;  // 随便假设一个
    // 多次调整
    while (minChild < size)
    {
        // 求证
        if (data[minChild] > data[minChild + 1] && minChild + 1 < size)
        {
            minChild++; // 这里就找出了父节点下的最小节点。
        }

        if (data[parent] > data[minChild])
        {
            Swap(&data[parent], &data[minChild]);
            parent = minChild;
            minChild = parent * 2 + 1; // 继续求小的子节点。
        }
        else
        {
            break;  // 不需要找的时候直接跳出循环
        }
    }
}

// 二叉树 - 堆删除 - 调整顺序（大堆）
void AdjustBDown(HPDataType* data, int size, int parent)
{
    // 求出根节点（父亲）下的最小的子节点。
    int maxChild = parent * 2 + 1;  // 随便假设一个
    // 多次调整
    while (maxChild < size)
    {
        // 求证
        if (data[maxChild] < data[maxChild + 1] && maxChild + 1 < size)
        {
            maxChild++; // 这里就找出了父节点下的最小节点。
        }

        if (data[parent] < data[maxChild])
        {
            Swap(&data[parent], &data[maxChild]);
            parent = maxChild;
            maxChild = parent * 2 + 1; // 继续求小的子节点。
        }
        else
        {
            break;  // 不需要找的时候直接跳出循环
        }
    }
}

3.2.6 堆顶的删除

// 二叉树 - 堆顶删除
void HeapPop(Heap* pHeap)
{
    // 断言：保护形参指针。
    assert(pHeap);
    assert(!HeapEmpty(pHeap));  // 数据不为空

    // 交换堆顶和最后一个数据
    Swap(&pHeap->data[0], &pHeap->data[pHeap->size - 1]);
    // 删除最后一个数据。
    pHeap->size--;
    // 向下调整
    AdjustDown(pHeap->data,pHeap->size,0);
}

3.2.7 取堆顶数据

// 二叉树 - 取堆顶数据
HPDataType HeapTop(Heap* pHeap)
{
    // 断言：保护形参指针。
    assert(pHeap);
    assert(!HeapEmpty(pHeap));  // 数据不为空
    return pHeap->data[0];
}

3.2.8 取堆中的数据个数

// 二叉树 - 取堆中的数据个数
int HeapSize(Heap* pHeap)
{
    // 断言：保护形参指针。
    assert(pHeap);
    return pHeap->size;
}

3.2.9 堆判空

// 二叉树 - 堆判空
bool HeapEmpty(Heap* pHeap)
{
    // 断言：保护形参指针。
    assert(pHeap);
    return pHeap->size == 0;
}

3.2.10 打印

void HeapPrint(Heap* pHeap)
{
    // 断言：保护形参指针。
    assert(pHeap);
    // 遍历打印。
    for (int i = 0; i < pHeap->size; i++)
    {
        printf("%d ",pHeap->data[i]);
    }
    printf("\n");
}

3.2.11 堆内存销毁

// 二叉树 - 堆内存销毁。
void HeapDestroy(Heap* pHeap)
{
    // 断言：保护形参指针。
    assert(pHeap);

    pHeap->size = pHeap->capacity = 0;

    free(pHeap->data);
    pHeap->data = NULL;

}

3.2.12 测试

// 二叉树 - 堆 测试
int main()
{
    Heap hp;

    int arr[] = { 15,18,19,25,28,34,65,49,27,37,10 };
    // int arr[] = { 65,100,70,32,50,60 };
    
    // 堆插入
    HeapInit(&hp);
    for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
    {
        HeapPush(&hp, arr[i]);
    }   
    HeapPrint(&hp);

    //HeapPop(&hp);
    //HeapPrint(&hp);

    //HeapPop(&hp);
    //HeapPrint(&hp);

    // 可以直接打印出升序和降序
    while (!HeapEmpty(&hp))
    {
        printf("%d ",HeapTop(&hp));
        HeapPop(&hp);
    }

    system("pause");

    HeapDestroy(&hp);
    return 0;
}

本文含有隐藏内容，请开通VIP 后查看

【数据结构与算法】【C】 - 二叉树（栈）

1.树概念及结构

1.1树的概念