目录
树：：
树的基本概念：
树的定义
树（tree） 是n（n>=0）个结点的有限集。n=0时称为空树。在任何一棵非空树中：
特点：：
1. 有且只有一个特定的称为 根（root） 的结点；
2. 当n>1时，其余结点可分为m（m>0）个 互不相交 的有限集，其中每一个集合又是一棵树，并且成为 根的子树（subtree）。
3. 树是一种一对多的结构。
结点分类：：
结点拥有的子树数称为结点的 度（Degree），树的度是树内各结点的度的最大值。
度为0的结点成为叶节点（Leaf）或者终端结点，除根结点外，分支结点也称为内部结点。
结点间的关系：：
结点子树的根称为该结点的孩子（Child），相应的该结点称为孩子的双亲（Parent），同一个双亲之间的孩子之间互称为兄弟（Sibling）。
结点的祖先是指从根到该结点所经历的所有结点，反之，以该结点为根的子树中的任意一结点称为该节点的子孙。
树的其他概念：：
树中结点的最大层次称为树的 深度（Depth） 或者高度。
根据树中结点是否可以交换分为有序树和无序树。
森林是指的多棵互不相交的树。
树的常见结构
1.双亲表示法：
通常采用数组或者顺序表的存储方式在存数据的同时将父亲节点的位置存储
图中的双亲表示的方法为：：（需要注意的是因为根节点没有父亲节点所以一般存储-1当父亲节点）
2：孩子表示法
3.最常用的孩子兄弟表示法：
二叉树
废话不说直接进入主题什么是二叉树？
理解度了之后就不用说也可以理解什么是二叉树：就是度最大为2的树就叫做二叉树
注意的是：度最大为2的树才叫二叉树！！！
特殊的二叉树：：
满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是2^K ，则它就是满二叉树。
完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树
文字晦涩，看图理解
关于二叉树的公式（考研学长学姐可以直接背诵使用）：
（1）非空二叉树叶子结点数 = 度为2的结点数 + 1 即，N0=N2+1（N0：度为0的节点数以此类推N1 N2）
（2）非空二叉树上第K层至多有2^(k-1) 个结点（K≥1）
（3）高度为H的二叉树至多有2^(H-1)个结点（H≥1）
（4）具有N个（N>0）结点的完全二叉树的高度为 ⌈log2(N+1)⌉或 ⌊log2N⌋+1(不知道怎么写以2为底的对数 请见谅)
（5）对完全二叉树按从上到下、从左到右的顺序依次编号1,2，...，N，则有以下关系：
① 当 i>1 时，结点 ii 的双亲结点编号为 ⌊i/2⌋ ，即当 i 为偶数时，其双亲结点的编号为 i/2 ，它是双亲结点的左孩子；当 i 为奇数时，其双亲结点的编号为 (i−1)/2 ，它是双亲结点的右孩子。
② 当 2i≤N 时，结点i的左孩子编号为 2i ，否则无左孩子。
③ 当 2i+1≤N 时，结点i的右孩子编号为 2i+1 ，否则无右孩子。
④ 结点 i所在层次（深度）为 ⌊log2i⌋+1 。（设根结点为第1层）
存储结构：：
二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构（普通二叉树由于存储的逻辑十分混乱并不建议使用普通二叉树存储）
顺序存储
顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，下面我们会说到。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树
链式存储
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链，当前我们使用的是二叉链
练练身手
了解完二叉树的性质之后，我们不妨来做几道选择题：
1.某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）
A 不存在这样的二叉树
B 200
C 198
D 199
答案：B。N0 = N2+1，既 N0=199+1 = 200
2.下列数据结构中，不适合采用顺序存储结构的是（ ）
A 非完全二叉树
B 堆
C 队列
D 栈
答案：A。根据存储结构自行理解
3.在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）
A n
B n+1
C n-1
D n/2
答案：A。总结点数n = N0+ N1+ N2;又 N2 = N0-1,既n= N0+ N1+ N0-1,因为在完全二叉树中， N1只有0个或者1个，代入选A
4.一棵完全二叉树的节点数位为531个，那么这棵树的高度为（ ）
A 11
B 10
C 8
D 12
答案：B 题目中讲到完全二叉树废话不说直接用公式
5.一个具有767个节点的完全二叉树，其叶子节点个数为（）
A 383
B 384
C 385
D 386
答案：B。完全二叉树！！！ 只有一个或没有N1——>>n = N2+N1+N0 N2=N0-1 767 = 2N0+N1-1 768 = 2N0+N1——>>所以N0 = 384；
堆
说到二叉树那必须要提堆（毕竟堆排很牛逼的）
首先堆是什么？
堆的概念：堆是一种完全二叉树，复习一下完全二叉树的定义，完全二叉树的形式是指除了最后一层之外，其他所有层的结点都是满的，而最后一层的所有结点都靠左边
再根据二叉树的父亲节点于孩子节点的关系可以分大堆小堆
大堆：父亲节点大于孩子节点 ；小堆：父亲节点小于孩子节点
搞一道题来深入理解
下列关键字序列为堆的是：（）
A 100,60,70,50,32,65
B 60,70,65,50,32,100
C 65,100,70,32,50,60
D 70,65,100,32,50,60
E 32,50,100,70,65,60
F 50,100,70,65,60,32
A：大堆 B 不是堆 C 不是堆 D 不是堆 E 不是堆 F 不是堆
解析：题目里面没有说具体是大堆还是小堆所以只要符合大堆或者小堆都可以
拿A举例 ：
由图可见父亲节点都大于孩子节点所以A是大堆
接下来如何去实现堆
Heap.h
#pragma once
typedef int HPDataType;
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<time.h>
typedef struct Heap
{
HPDataType* _a;
int _size;
int _capacity;
}HP;
// 堆的构建
void HPInit(HP* hp, HPDataType* a, int n);
// 堆的销毁
void HeapDestory(HP* hp);
// 堆的插入
void HeapPush(HP* hp, HPDataType x);
// 堆的删除
void HeapPop(HP* hp);
// 取堆顶的数据
HPDataType HeapTop(HP* hp);
// 堆的数据个数
int HeapSize(HP* hp);
// 堆的判空
int HeapEmpty(HP* hp);
void PrintTopK(int* a, int n, int k);
void TestTopk();
void heapsort(HPDataType* a, int n);Heap.c
#define _CRT_SECURE_NO_WARNINGS
#include"heap.h"
void swap(HPDataType* a, HPDataType* b)
{
HPDataType m = *a;
*a = *b;
*b = m;
}
void adjustup(HPDataType* a, int n, int child)
{
int parent = (child - 1) >> 1;
while (child > 0)
{
if (a[parent] > a[child])
{
swap(&a[parent], &a[child]);
child = parent;
parent = (child - 1) >> 1;
}
else
{
break;
}
}
}
void adjustdown(HPDataType* a, int n, int root)
{
/*assert(_a);
int child = parent * 2 + 1;
while (child < n)
{
if (child + 1 < n && _a[child] < _a[child + 1])
{
child++;
}
if (_a[child] > _a[parent])
{
swap(&_a[child], &_a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}*/
int parent = root;
int child = parent * 2 + 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 = parent * 2 + 1;
}
else
{
break;
}
}
}
void HPInit(HP* hp, HPDataType* a, int n)
{
assert(hp && a);
HPDataType* _hp = (HPDataType*)malloc(sizeof(HPDataType) * n);
if (_hp == NULL)
{
printf("malloc fail！");
exit(-1);
}
hp->_a = _hp;
hp->_capacity = hp->_size = n;
for (int i = 0; i < n; i++)
{
hp->_a[i] = a[i];
}
for (int i = (n - 2) / 2; i >= 0; --i)
{
adjustdown(hp->_a, hp->_size, i);
}
}
void HeapDestory(HP* hp)
{
assert(hp);
free(hp->_a);
hp->_a = NULL;
hp->_capacity = hp->_size = 0;
}
void HeapPush(HP* hp, HPDataType x)
{
assert(hp);
if (hp->_capacity == hp->_size)
{
int newcapacity = hp->_capacity == 0 ? 4 : hp->_capacity * 2;
HPDataType* a = (HPDataType*)realloc(hp->_a, sizeof(HPDataType) * newcapacity);
if (a == NULL)
{
printf("realloc fail");
exit(-1);
}
hp->_a = a;
}
hp->_a[hp->_size++] = x;
adjustup(hp->_a, hp->_size, hp->_size - 1);
}
void HeapPop(HP* hp)
{
assert(hp);
swap(&hp->_a[0], &hp->_a[hp->_size - 1]);
hp->_size--;
adjustdown(hp->_a, hp->_size, 0);
}
HPDataType HeapTop(HP* hp)
{
assert(hp);
return hp->_a[0];
}
int HeapSize(HP* hp)
{
return hp->_size;
}
int HeapEmpty(HP* hp)
{
return hp->_size == 0 ? 0 : 1;
}
void print(HP* hp)
{
assert(hp);
for (int i = 0; i < hp->_size; i++)
{
printf("%d ", hp->_a[i]);
}
printf("\n");
}
void PrintTopK(int* a, int n, int k)
{
HP hp;
assert(a);
HPInit(&hp, a, k);
for (int i = k ; i < n; i++)
{
if (a[i] > hp._a[0])
{
HeapPop(&hp);
HeapPush(&hp, a[i]);
}
}
for (int i = 0; i < k; i++)
{
printf("%d ", HeapTop(&hp));
HeapPop(&hp);
}
printf("\n");
}
void heapsort(HPDataType* a,int n)
{
HP hp;
HPInit(&hp, a, n);
for (int i = 0; i < n; i++)
{
//printf("%d ", HeapTop(&hp));
a[i] = HeapTop(&hp);
HeapPop(&hp);
}
}test.c
建堆：我这里建的小堆
堆的销毁
堆的插入：
堆顶数据删除：
取堆顶的数据 （取出最大或最小，获得次大次小）
topk问题 排名前k的数据
堆排：
215. 数组中的第K个最大元素 - 力扣（LeetCode）
来直接试试手
void swap(int* a,int* b)
{
int c = *a;
*a = *b;
*b = c;
}
void adjustdown(int* a,int k,int parent){
int child = parent * 2 + 1;
while(child < k){
if(child + 1<k && a[child]>a[child+1]){
child++;
}
if(a[child]<=a[parent]){
swap(&a[child],&a[parent]);
parent = child;
child = parent*2+1;
}
else{
break;
}
}
}
int findKthLargest(int* nums, int numsSize, int k){
int* a = (int*)malloc(sizeof(int)*k);
for(int i = 0;i < k;i++){
a[i] = nums[i];
}
for(int i = k;i >= 0;i--){
adjustdown(a,k,i);
}
for(int i = k;i<numsSize;i++)
{
if(nums[i]>a[0]){
a[0] = nums[i];
adjustdown(a,k,0);
}
}
return a[0];
}
关于二叉树的前中后序的爱恨情仇：
void BinaryTreePrevOrder(BTNode* root)
{
if (root)
{
putchar(root->_data);
BinaryTreePrevOrder(root->_left);
BinaryTreePrevOrder(root->_right);
}
}
void BinaryTreeInOrder(BTNode* root)
{
if (root)
{
BinaryTreeInOrder(root->_left);
putchar(root->_data);
BinaryTreeInOrder(root->_right);
}
}
void BinaryTreePostOrder(BTNode* root)
{
if (root)
{
BinaryTreePostOrder(root->_left);
BinaryTreePostOrder(root->_right);
putchar(root->_data);
}
}可以看出来其实好像就是因为输出的语句位置不同边有了前中后序的说法，这就得深入理解什么是递归；
但是这三种遍历是好可是遇见了左右子树高度差距大的二叉树便会有一系列问题
层序遍历
所以我们还有最牛的层序遍历，说白了就是一层一层往下遍历；
废话先不多说先看代码
void BinaryTreeLevelOrder(BTNode* root)
{
Queue qu;
BTNode* cur;
QueueInit(&qu);
QueuePush(&qu, root);
while (!empty(&qu))
{
cur = QueueTop(&qu);
putchar(cur->_data);
if (cur->_left)
{
QueuePush(&qu, cur->_left);
}
if (cur->_right)
{
QueuePush(&qu, cur->_right);
}
QueuePop(&qu);
}
QueueDestroy(&qu);
}那么这个层序遍历有什么用呢？
如果让你判断一个满二叉树是不是直接遍历算节点和高度的关系就OK了；但是要是判断是不是一个完全二叉树就发现有那么一点点困难，这时候就是层序的舞台；
int BinaryTreeComplete(BTNode* root)
{
Queue qu;
BTNode* cur;
int tag = 0;
QueueInit(&qu);
QueuePush(&qu, root);
while (!empty(&qu))
{
cur = QueueTop(&qu);
putchar(cur->_data);
if (cur->_right && !cur->_left)
{
return 0;
}
if (tag && (cur->_right || cur->_left))
{
return 0;
}
if (cur->_left)
{
QueuePush(&qu, cur->_left);
}
if (cur->_right)
{
QueuePush(&qu, cur->_right);
}
else
{
tag = 1;
}
QueuePop(&qu);
}
QueueDestroy(&qu);
return 1;
}部分概念及图片来源于网络