关键词：
文章目录
口令：此乃何物？
前言
经过两周的努力奋战，博主呕心沥血地总结了数据结构中树与二叉树的所有基本操作，包括堆的实现，链式二叉树等等并含有完整的测试代码，不要问博主应得什么，要问博主为大家做了什么（泪目），全文有大约两万字，在总结的过程中还发现了写递归程序的一种快速方法，欢迎大家点赞收藏。
树
什么是树
树是一种数据结构，它是由n(n≥1)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。我们用树的逻辑结构来表示一下它：
这就表示了一棵树，其中每一个节点都会存储一定的信息，这里A为树根。
我们可以发现树其实是递归进行定义的，任何一棵树都可以分成根节点和子树。
树的基本概念
1.节点的度：一个节点含有子树的个数我们称之为该节点的度，比如A的度为3，D的度为1，J的度为2。
2.叶节点：度为0的节点，在这棵树中有K,F,G,H,I,L,M。
3.分支节点：度不为0的节点。即除了叶子节点之外的节点都可以称为分支节点。
4.父节点：一个节点为其子节点的父节点。
5.兄弟节点：具有相同父节点的节点。
6.树的度：一棵树中最大节点的度称为树的度。
7.节点的层次：根为第一层，其子节点为第二层，以此类推空树的高度为0。
8.树的高度或深度：一棵树中节点的最大层次。
9.堂兄弟节点：双亲在同一层的非兄弟节点称为堂兄弟节点，这里的G和H就为堂兄弟节点。
10.节点的祖先：从根到该节点经过的所有节点称为该节点的祖先。
11.子孙：以某节点为根的任意子树上的所有顶点称为该节点的子孙。
12.森林：不相交的树的集合。比如并查集就是多棵树的集合。
树的实现方式
树的实现方式有很多种，目前公认最好的实现方式是：左孩子右兄弟表示法。
就是每一个树的节点中，存储两个指针，分别指向它的最左侧的孩子节点和它的向右一位的兄弟节点，如果没有左孩子或者右兄弟的话则对应的指针指向空，注意是右兄弟而不是堂兄弟。
定义节点的方式为：
struct Node
struct Node* firstchild;//指向左孩子
struct Node* nextbrother;//指向右兄弟
int data//用于存放数据
实现方式的逻辑结构如下图： 
但其实我们直接应用普通的树的情况并不多，所以我们考虑树的一种应用更广泛的特殊情况即：二叉树。
二叉树
什么是二叉树
最大的度为2的树，注意是最大的树，二叉树中也可以有度为0和1的节点。
两种特殊的二叉树
满二叉树
所有非叶子节点的度为2，所有叶子节点都在最后一层。
完全二叉树
完全二叉树满足两个特点：
1.前n-1层都是满的
2.最后一层不满但是从左到右是连续的。
这两棵树就是完全二叉树。
这两棵树中前一棵树没有满足最后一层从左到右是连续的，后一棵没有满足最后一层之前都是满的。
二叉树的性质
- 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个结点.
- 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h- 1.
- 对任何一棵二叉树, 如果度为0其叶结点个数为 n0, 度为2的分支结点个数为 n2,则有n0＝n2＋1
- 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=log2(n+1). (ps：log2(n+1)是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否则无右孩子
二叉树的存储
对于一般的树来说，左孩子右兄弟的存储方法是最优的，但是对于二叉树来说，杀鸡焉用宰牛刀，由于一个节点最大的度就为2，不如存储它的两个子节点的地址作为二叉树节点的结构。
节点的定义：
struct TreeNode
struct TreeNode* leftchild;//左孩子节点
struct TreeNode* rightchild;//右孩子节点
int data;
它的逻辑结构为下图：
堆
什么是堆
堆是一种特殊的二叉树，是一种数据的存储方式，我们在数据结构中所说的栈和堆与操作系统中的栈和堆是两种完全不同的概念。堆是一个完全二叉树。
堆的分类及特点
堆分为大堆和小堆：
大堆：树中任何一棵子树中，父节点的data值都大于等于其子节点的data值。
小堆：树中任何一棵子树中，父节点的data值都小于等于其子节点的data值。
堆的作用
数据结构中引入堆这个概念可以解决两类问题：
1.堆排序：是一种常用的排序算法。
2.topK问题：即在一组数中寻找最大的前K个数。下面要使用大堆实现，所以要寻找一组数中最小的十个数。
堆的实现
堆的插入（建立大堆）
void HeapPush(HP* hp, DataType x)
assert(hp);
if (hp->size == hp->capacity)
int newcapacity = (hp->size == 0) ? 4 : hp->capacity * 2;
DataType* tmp = (DataType*)realloc(hp->a, sizeof(DataType)*newcapacity);
if (tmp == NULL)
printf("realloc fail\\n");
exit(-1);
else
hp->a = tmp;
hp->capacity = newcapacity;
//如果空间不够进行扩容
hp->a[hp->size] = x;
hp->size++;//将元素插入末尾
Adjustup(hp->a, hp->size - 1);//进行向上调整。
由于我们是使用顺序表来建立的堆，堆的物理结构实际上就是连续存储的数组，我们将它看成堆。
堆插入一共分为两个步骤：
1.将要插入的元素插入堆的末尾。
2.使用向上调整算法进行调整。
将插入元素放入末尾很容易，下面我们来实现向上调整算法，向上调整算法即将插入元素后的结构再一次调整成堆。
void Adjustup(DataType* a, int child)
assert(a);
int parent = (child - 1) / 2;
while (child > 0)//当child小于0的时候停止
if (a[parent] < a[child])
Swap(&a[parent], &a[child]);
child = parent;
parent = (parent - 1) / 2;//比较父亲节点与孩子节点如果父亲比孩子小则交换
else
break;//当父节点大于子节点的时候停止
我们根据流程图来理解这一段代码。
1.首先我们将要插入的节点插入堆的末尾。并记录它的下标为child，并将其父亲节点的下标记为parent。
2.比较child和parent的值，由于建立的是大堆，所以当父亲节点的值小于孩子节点时，两者交换位置。
3.更新child的值为parent，更新parent的值为新child的父亲节点，继续进行比较。
4.当父亲节点与孩子节点重合（即新插入的节点是堆顶），或者当父亲节点大于孩子节点的时候，循环停止进行。
注意根据孩子节点找父亲节点的方式在二叉树的性质中提到过，即parent=2*child+1。
以上就是向上调整算法，实际上就是把末尾的元素向上进行调整使结构仍为一个堆。
这是插入后的效果。
堆的删除
void HeapPop(HP* hp)
assert(hp);
assert(!HeapEmpty(hp));
Swap(&(hp->a[0]), &(hp->a[hp->size-1]));//交换堆顶元素与最后一个元素
hp->size--;
Adjustdown(hp->a, hp->size,0);//向下调整算法，构成一个新的堆
堆的删除一共分为两步：
1.将堆顶元素与最后一个元素互换位置，并将堆的大小-1（为了排除堆顶元素）。
2.利用向下调整算法将换到上面的最后一个元素进行向下调整使扔构成一个堆。
下面我们来实现向下调整算法。
void Adjustdown(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++;
//将child置为最大的孩子节点
if (a[child] > a[parent])
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
//当child大于parent时进行交换
else
break;
我们按照流程图来理解。
1.首先我们要删除的是99这个元素，在将99和34交换之后99就已经删除了，99不参与任何比较。
2.交换之后进行向下调整，使用parent记录34的坐标，使用child记录34的最大孩子的坐标，这里需要对两个孩子进行比较。
3.如果child记录的元素比parent大则交换，并将parent的值置为child，child置为新parent的最大孩子节点。
4.在当child超出数组范围的时候或者当孩子节点小于父亲节点的时候停止。否则循环继续进行。
这里就是堆删除的效果。
堆排序
堆最常用的功能就是进行排序，时间复杂度可以为O(NlogN)。
void HeapSort(DataType* a, int n)
int i;
for (i=(n-2)/2; i >= 0; i--)
Adjustdown(a, n, i);//第一次建立堆
for (int end = n - 1; end > 0; --end)
Swap(&a[end], &a[0]);
Adjustdown(a, end, 0);//每一次将堆顶元素与最后一个互换然后再重新建立堆
堆排序一共分为两步：
1.对所有有子节点或者子树的节点进行从左向右，从上向下进行向下调整。**向下调整的本质是找出一棵最小二叉树中节点的最大值。**所以最后调整之后建立了一个堆，堆顶点是这组数的最大值。
2.交换堆顶点与最后一个元素，在堆中对最后一个元素进行向下调整（不包含最后一个元素）。【这里和删除时一样的】，从而找出次大的数。
总结一下就是首先明确堆顶的元素是最大的，记录最大的元素，然后排除最大元素再建立一个堆，仍然找出最大元素，然后循环下去。
下面我们用流程图来理解一下。
下面对每一张图进行解释：
1.首先我们拿到了一组数：3,7,2,6,0,1,9,5,4,35，我们先把它们画成堆的形式。
2.从3这个节点开始，依次对6,9,7,0的位置（作为父节点）进行向下调整，成功建立一个堆。
3.将堆顶元素即最大元素35与最后一个元素0互换位置。
4.对0进行向下调整，找出堆顶元素即次大元素9，然后将它与末尾的4互换位置。然后再对4进行向下调整依次类推。
最后得到已经排好序的堆。本质其实就是把最大的元素依次插入到末尾。
最后建立的堆的结果如上图。
TopK问题
TopK问题是寻找一组数中最大的K个元素，但是博主建立的是大堆所以能找到最小的K个值，建立小堆找最大的K个值同理。
void HeapTopK(DataType* a, int n,int k)
HP hp;
HeapInit(&hp);
assert(a);
for (int i = 0; i < k; i++)
HeapPush(&hp, a[i]);
//前K个元素入堆
for (int i = k; i < n; i++)
if (a[i] < HeapTop(&hp))
HeapPop(&hp);
HeapPush(&hp, a[i]);
//将剩余的元素与堆顶元素进行比较，如果比它小就入堆
HeapPrint(&hp);
HeapDestroy(&hp);
TopK问题分为两步
1.首先建立一个大小为K的堆（可以利用堆插入），将这组数中前K个元素放入堆中，此时堆顶是这K个元素中的最大值。
2.将这组数中剩余的元素与堆顶的数比较，如果比堆顶的数小就将堆顶元素删除，将该元素入堆。依次循环下去。
我们用图来理解一下
假设要寻找3,7,2,6,0,1,9,5,4,35这组树的最小的四个数。
看这个例子，首先将这组数的前四个元素7,6,2,3放入堆中，然后将0与堆顶元素7进行比较，比7小，所以7出堆，0入堆，向下调整形成堆，
此时堆顶元素为6，然后用1与6进行比较，6出堆，1入堆，以此类推，可以得到最后堆中剩下的元素就是最小的4个元素。
堆的所有代码（已经过完整测试）
heap.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
#define DataType int
//构建堆的节点--顺序表
typedef struct Heap
int* a;
int size;
int capacity;
HP;
void HeapInit(HP* hp);//初始化
void HeapDestroy(HP* hp);//销毁堆
void HeapPrint(HP* hp);//打印堆
bool HeapEmpty(HP* hp);//判断堆空
int HeapSize(HP* hp);//堆的大小
DataType HeapTop(HP* hp);//取堆顶元素
void Swap(DataType* x, DataType* y);//交换两个元素
void HeapPush(HP* hp, DataType x);//堆插入建大堆
void Adjustup(DataType* a,int child);//向上调整算法
void HeapPop(HP* hp);//堆删除
void Adjustdown(DataType* a,int n, int parent);//向下调整算法
void HeapSort(DataType* a, int n);//堆排序
void HeapTopK(DataType* a, int n,int k);//TopK问题
heap.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"heap.h"
//堆的初始化
void HeapInit(HP* hp)
assert(hp);
hp->size = hp->capacity = 0;
hp->a = NULL;//将堆中元素的个数置为0，指向堆中元素的指针置为空
void HeapDestroy(HP* hp)
assert(hp);
free(hp->a);//顺序表建立堆，根据free()函数性质可以直接释放首元素从而释放整个堆
hp->size = hp->capacity = 0;//将堆中元素个数置为0
//打印整个堆
void HeapPrint(HP* hp)
assert(hp);
int i;
for (i = 0; i < hp->size; i++)
printf("%d ", hp->a[i]);
printf("\\n");
//判断堆空
bool HeapEmpty(HP* hp)
assert(hp);
return hp->size == 0;//当size为0返回true,当不为0返回false
//计算堆的大小
int HeapSize(HP* hp)
assert(hp);
return hp->size;
//得到堆顶元素
DataType HeapTop(HP* hp)
assert(hp);
assert(hp->a);//需要判断指向堆的指针，和堆中指向元素的指针都不为空
return hp->a[0];
//交换两个元素
void Swap(DataType* x, DataType* y)
DataType tmp=0;
tmp = *x;
*x = *y;
*y = tmp;
//堆的插入
void HeapPush(HP* hp, DataType x)
assert(hp);
if (hp->size == hp->capacity)
int newcapacity = (hp->size == 0) ? 4 : hp->capacity * 2;
DataType* tmp = (DataType*)realloc(hp->a, sizeof(DataType)*newcapacity);
if (tmp == NULL)
printf("realloc fail\\n");
exit(-1);
else
hp->a = tmp;
hp->capacity = newcapacity;
hp->a[hp->size] = x;
hp->size++;
Adjustup(hp->a, hp->size - 1);
//向上调整算法建立大堆
void Adjustup(DataType* a, int child)
assert(a);
int parent = (child - 1) / 2;
while (child > 0)
if (a[parent] < a[child])
Swap(&a[parent], &a[child]);
child = parent;
parent = (parent - 1) / 2;
else
break;
//删除堆顶元素
void HeapPop(HP* hp)
assert(hp);
assert(!HeapEmpty(hp));
Swap(&(hp->a[0]), &(hp->a[hp->size-1]));
hp->size--;
Adjustdown(hp->a, hp->size,0);
//向下调整
void Adjustdown(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++;树与二叉树
[toc]树的存储结构 树的存储结构有两种，线式存储和链式存储，灵活使用这两种存储结构，具有如下五种存储方式：双亲表示法，一种顺序(线式)表示法孩子表示法，一种链式表示法孩子链表表示法，结合线式存储和链式存... 查看详情
树与二叉树——定义
树形结构是一类重要的非线性结构数据结构。其中以树和二叉树最为常用，直观看来，树是以分支关系定义的层次结构。树的定义与基本术语 树的结构定义是一个递归定义，即在树的定义中又用到树的概念。除了树形表示外... 查看详情
树与二叉树
一树的基本术语 （1）结点、叶子、父结点、子结点、祖父结点、兄弟结点、子孙结点 （2）结点的度：结点拥有的子树的数量 （3）树的度：树中结点最大的树 （4）树的高度：树中结点的最大层次二二叉树的性... 查看详情
考研数据结构与算法树与二叉树(代码片段)
考研数据结构与算法（六）树与二叉树文章目录考研数据结构与算法（六）树与二叉树一、树的概念和基础术语1.1定义1.2基础术语1.3树的性质二、二叉树2.1二叉树定义2.2二叉树性质2.2.1满二叉树2.2.2完全二叉树2.2.3... 查看详情
树与二叉树（数据结构）
(1)树的基本性质1.树中的结点数等于所有结点的度数+1。2.树中结点的最大度数称为树的度。3.度为m的树中第i层上至多有mi-1个结点。4.高度为h的m叉树至多有（mh-1）/（m-1）个结点。5.具有n个结点的m叉树的最小高度math.ceil(logm[n(m-1)... 查看详情
树与二叉树之一--基本概念与存储结构
树的基本术语结点：结点不仅包含数据元素，而且包含指向子树的分支。结点的度：结点拥有的子树的个数或者分支的个数。树的度：树中各结点度的最大值。叶子结点：又叫终端结点，指度为0的结点。非终端结点：又叫分支... 查看详情
python数据结构系列☀️《树与二叉树-基础知识》——知识点讲解+代码实现☀️(代码片段)
...存储2.2.2链式存储2.3遍历二叉树大作业一：**二叉树的基本操作**2.4线索二叉树2.4.1线索二叉树的概念2.4.2构造线索二叉树2.4.3遍历线索二叉树大作业二ÿ 查看详情
B树与二叉树
】B树与二叉树【英文标题】：Btreesvsbinarytrees【发布时间】：2011-09-0620:31:50【问题描述】：如果我使用b树实现内存中(RAM)搜索操作，那么与二叉树相比，它在缓存或其他一些效果方面会更好吗？我所知道的是-binarysearchtress---O(logn)... 查看详情
数据结构之——树与二叉树
...的概念是学习树的关键所在，掌握了树的基本概念，学会树与二叉树，soeasy。我通过一棵树来了解树的基本概念，如下图 &nb 查看详情
王道数据结构5（树与二叉树）(代码片段)
树与二叉树一、树的基本概念（一）树的基本概念（二）树的基本术语（A）结点相关（B）树整体相关（三）树的表示形式（四）树的性质二、二叉树（一）二叉树的定义... 查看详情
树与二叉树之二--二叉树的性质与存储
二叉树的定义1）每个节点最多只有两颗子树，即二叉树中结点的度只能为0、1、2；2）子树有左右之分，不能颠倒。二叉树的五种基本状态：1）空二叉树2）只有根节点3）只有左子树，右子树为空4）只有右子树，左子树为空5）... 查看详情
树与二叉树
一、树1.树的定义非线性数据结构除根节点外，一个直接前驱，多个直接后继2.树的逻辑表示方法树形表示法3.树的基本术语结点的度、树的度、m次树分支结点、叶子结点路径、路径长度孩子结点、双亲结点、兄弟节点、子孙结... 查看详情
王道数据结构——树与二叉树(代码片段)
本文主要讲述了数据结构中树的基本概念，二叉树，树与森林以及树与二叉树的应用。知识框架如下图所示：树的基本概念树是N(N>=0)个结点的有限集合，N=0时，称为空树。而任何一棵非空树应该满足，有且仅有一个根结点，... 查看详情
树与二叉树
Atreeisafinitenonemptysetofelements,itisanabstractmodelofhierarchicalstructure. Application:OrganizationchartsFilesystemsProgrammingenvironments 名词解释：Root：根nodewithoutparentSiblings：兄弟节点&nbs 查看详情
重建二叉树与二叉树的层次遍历
数据结构实验之求二叉树后序遍历和层次遍历TimeLimit:1000ms Memorylimit:65536K 有疑问？点这里^_^题目描写叙述已知一棵二叉树的前序遍历和中序遍历，求二叉树的后序遍历。输入输入数据有多组，第一行是一个整数t(t<1... 查看详情
树与二叉树二叉树链式结构及实现--万字详解介绍(代码片段)
📝个人主页：@Sherry的成长之路🏠学习社区：Sherry的成长之路（个人社区）📖专栏链接：数据结构🎯长路漫漫浩浩，万事皆有期待文章目录一、链式存储：二、链式结构的遍历&#... 查看详情
数据结构树与二叉树的基本概念结构特点及性质(代码片段)
前言：本章内容主要是数据结构中树与二叉树的基本概念、结构特点及性质的引入。文章目录树的概念树的特点：树的常用术语：树的表示：代码创建：树在实际中的应用：二叉树的概念特殊的二叉树满二... 查看详情
树与二叉树
树1.基本概念： ①树是n(n>=0)个节点的集合T，当n==0时，称为空树；当n>0时，该集合满足以下条件 ②必有个根节点，他没有直接前驱，有零个或多个后继。 ... 查看详情