1.树的概念及结构
1.1树的概念
树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。
- 有一个特殊的结点，称为根结点，根结点没有前驱结点；
- 除根结点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i<= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继
- 因此，树是递归定义的。
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 TreeNode
{struct TreeNode* firstChild1;//第一个孩子结点struct TreeNode* pNextBrother;//指向其下一个兄弟结点DataType data; //结点中的数据域
};2.二叉树概念及结构
2.1概念
一颗二叉树是结点的有限集合
1.为空；
2.由一个根节点加上两颗别称为左子树和右子树的二叉树组成；
注意：
1.二叉树不存在度大于2的结点；
2.二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树；
2.2 特殊的二叉树
1、满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是 ，则它就是满二叉树。
2、完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。（前k-1层都是满的，最后一层要求从左到右是连续的）
2.3 二叉树的性质
错位相减法求结点个数
1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有 2^（i-1）个结点；
2.若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h-1 ,最小节点数是2^(h-1) ; （2^(h-1)-1+1）
3.对任何一棵二叉树, 如果度为0其叶结点个数为N0 , 度为2的分支结点个数为N2 ,则有 N0＝N2 ＋1;
4.若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=log(n+1) . (ps： 是log以2为底，n+1为对数);
5.对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：
1. 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
2. 若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子
3. 若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子
2.4 二叉树的存储结构
1.顺序存储
顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。
2.链式存储
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关
系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来
给出该结点左孩子和右孩子所在的链结点的存储地址 。
3.二叉树的顺序结构及实现
3.1 二叉树的顺序结构
普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。
3.2 堆的概念及结构
堆是完全二叉树，根结点最大的堆叫做大根堆（最大堆），根结点最小的堆叫做小根堆（最小堆）。
堆的性质：
- 堆中某个节点的值总是不大于或不小于其父节点的值；
- 堆总是一棵完全二叉树
3.3 堆的实现
二叉树的规律：
我们用 parent、leftchild、rightchild，分别代表父亲节点、左右孩子节点的下标（物理结构是数组）。
根据规律得： leftchild = parent * 2 + 1 ，rightchild = parent * 2 + 2 。并且任一节点 i ，其父亲节点 parent = (i-1)/2 。
3.3.1 堆向上调整算法
向上调整算法可以调整除根结点以外的所有结点到根结点的路径（任一节点到根节点之间的路径唯一），其结果是，将这条路径上，最大或者最小的节点，放到根节点位置。
例如在堆中插入一个数据（一般都在末尾插入），就可以使用向上调整算法，将插入的数据放到正确的位置，使其结构任然是堆。
void Swap(HeapDataType* a, HeapDataType* b)
{int c = *a;*a = *b;*b = c;
}void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;//当child=0时，parent=（0-1）/2=0，parent不可能为负数，但程序还是可以跑起来//while(parent>=0) while (child>0){if (a[child] > a[parent]){Swap(&a[child],&a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}3.3.2 堆向下调整算法
向下调整算法可以调整除叶子结点外的所有结点到叶子结点的路径，其结果是将这条路径上最大/最小的数放到叶子结点处。
注意：该算法有个前提：左右子树必须是同一种堆，才可以调整。
每次调整根结点都是和左右孩子中较大（大堆）/较小（小堆）的交换
int array[] = {27,15,19,18,28,34,65,49,25,37};
向下调整算法实际上是调整的某一个节点 A，要这个节点的左右子树都是同种堆，调整之后，以原 A 位置的节点为根节点的树是一个堆。
void Swap(HeapDataType* a, HeapDataType* b)
{int c = *a;*a = *b;*b = c;
}// 左右子树都是大堆/小堆
void AdjustDown(HPDataType* a, int size, int parent)
{int child = parent * 2 + 1;while (child<size){//选出左右孩子较大的那个 默认左边大if (child + 1 < size && a[child + 1] > a[child]){child++;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}3.3.3 建堆
建堆的方法有两种：1.向上建堆；2.向下建堆;分别对应两种上面的两种算法。
如果我们从根结点开始建堆，但如果给定的数组形成的二叉树是乱序的，那么就实现不了建堆；所以我们只能从树的下方开始建堆，如果使用向上建堆的话就需要从叶子结点开始建，使用向下建堆的话就需要从叶子结点的根结点开始建。
void HeapInitArray(HP* php, int* a, int n)
{assert(php);php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);if (php->a == NULL){perror("malloc fail");return;}php->size = n;php->capacity = n;// 建堆-向下建堆for (int i = (n - 2) / 2; i >= 0; --i){//参数：数组，数组大小，根结点AdjustDown(php->a, php->size, i);}// 建堆-向上建堆for (int i = n-1 ; i >= 0; --i){//参数：数组，孩子结点AdjustUp(php->a, i);}
}3.3.4 建堆的时间复杂度
1.向上建堆--- O（NlogN）
向上建堆是从倒数第一行开始的，假设高度从1开始。
2.向下建堆--- O（N）
向下建堆是从倒数第二行开始的，假设高度从1开始。
总结：所以从时间复杂度的角度来看选择向下建堆比较好
#define _CRT_SECURE_NO_WARNINGS
#include"Heap.h"void HeapInit(HP* php)
{assert(php);php->a = (HPDataType*)malloc(sizeof(HPDataType) * 4);if (php->a == NULL){perror("HeapInit::malloc");return;}php->capacity = 4;php->size = 0;
}void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->capacity = php->size = 0;
}void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;//交换的p1、p2的值，没有改变函数外部的值//HPDataType* tmp = p1;//p1 = p2;//p2 = tmp;
}// 除了child这个位置，前面数据构成堆
void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;//当child=0时，parent=（0-1）/2=0，parent不可能为负数，但程序还是可以跑起来//while(parent>=0) while (child>0){if (a[child] > a[parent]){Swap(&a[child],&a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}void HeapPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType)* (php->capacity * 2 ));if (tmp==NULL){perror("HeapPush::realloc");return;}php->capacity *= 2;php->a = tmp;}php->a[php->size] = x;php->size++;AdjustUp(php->a,php->size-1);
}// 左右子树都是大堆/小堆
void AdjustDown(HPDataType* a, int size, int parent)
{int child = parent * 2 + 1;while (child<size){//选出左右孩子较大的那个 默认左边大if (child + 1 < size && 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 HeapPop(HP* php)
{assert(php);assert(!HeapEmpty(php));Swap(&(php->a[0]), &(php->a[php->size - 1]));php->size--;AdjustDown(php->a, php->size, 0);
}HPDataType HeapTop(HP* php)
{assert(php);assert(!HeapEmpty(php));return php->a[0];
}bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}int HeapSize(HP* php)
{assert(php);return php->size;
}#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int HPDataType;typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;void HeapInit(HP* php);
void HeapDestroy(HP* php);void HeapPush(HP* php, HPDataType x);
void HeapPop(HP* php);
HPDataType HeapTop(HP* php);
bool HeapEmpty(HP* php);
int HeapSize(HP* php);void AdjustUp(HPDataType* a,int child);
void AdjustDown(HPDataType* a,int n,int parent);int main()
{HP hp;HeapInit(&hp);HeapPush(&hp, 4);HeapPush(&hp, 18);HeapPush(&hp, 42);HeapPush(&hp, 12);HeapPush(&hp, 21);while (!HeapEmpty(&hp)){printf("%d ", HeapTop(&hp));HeapPop(&hp);}return 0;
}3.4 堆的应用
3.4.1 堆排序
堆排序即利用堆的思想来进行排序，总共分为两个步骤：
1. 建堆
升序：建大堆，最大的数就在根结点，然后再将根结点与最后一个结点交换，取出最后一个结点，再将新的堆进行向下调整，堆大小减一。
降序：建小堆，最小的数就在根结点，然后再将根结点与最后一个结点交换，取出最后一个结点，再将新的堆进行向下调整，堆大小减一。
2. 利用堆删除思想来进行排序
void Swap(HeapDataType* a, HeapDataType* b)
{int c = *a;*a = *b;*b = c;
}//排升序 -- 建大堆//排降序 -- 建小堆
void HeapSort(HeapDataType* a, int n)
{//向上调整,时间复杂度是 O（N*log(N)）// 每层节点少，调整次数少，节点多，调整次数多，且除了根节点，都要调整。//for (int i = 1;i < n;i++)//{// AdjustUp(a, i);//}//向下调整, 时间复杂度是 O(N)// 每层节点数量多，调整次数少，节点数量少，调整次数多。且跳过最后一层，接近一半的节点不要调整。for (int i = (n - 1 - 1) / 2;i >= 0;i--){AdjustDown(a, n, i);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}}int main()
{int a[10] = { 2, 1, 5, 7, 6, 8, 0, 9, 4, 3 }; // 对数组排序HeapSort(a, 10);return 0;
}
3.4.2 TOP-K问题
TOP-K问题：即求数据集合中前K个最大的元素或者最小的元素，一般情况下数据量都
比较大。（比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。）
对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：
1. 用数据集合中前K个元素来建堆
2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
void PrintTopK(const char* file,int k)
{//建堆，用前K个元素建小堆int* topk = (int*)malloc(sizeof(int) * k);if (topk == NULL){perror("PrintTopK::malloc");return;}FILE* fout = fopen(file, "r");if (fout == NULL){perror("PrintTopK::fopen");return;}//读出前K个数据建小堆for (int i = 0; i < k; i++){fscanf(fout, "%d", &topk[i]);}for (int i = (k-2)/2; i >=0 ; i--){AdjustDown(topk, k, i);}//将剩余的n-k个数据依次与栈顶元素比交，不满足则替换下一个int val = 0;int ret = fscanf(fout, "%d", &val);while (ret != EOF){if (val > topk[0]){topk[0] = val;AdjustDown(topk, k, 0);}ret = fscanf(fout, "%d", &val);}for (int i = 0; i < k; i++){printf("%d ", topk[i]);}printf("\n");free(topk);fclose(fout);
}void CreateNDate()
{//造数据int n = 1000;srand(time(0));const char* file = "data.text";FILE* fin = fopen(file, "w");if (fin == NULL){perror("CreateNDate::fopen");return;}for (size_t i = 0; i < n; i++){int x = rand() % 1000;fprintf(fin, "%d\n", x);}fclose(fin);
}int main()
{CreateNDate();//生成一次后可以屏蔽掉PrintTopK("data.text", 10);return 0;
}4.二叉树链式结构的实现
4.1 实现方式
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;BTNode* BuyNode(BTDataType x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("BuyNode::malloc");return NULL;}node->data = x;node->left = NULL;node->right = NULL;return node;
}BTNode* CreatTree()
{BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(5);BTNode* node6 = BuyNode(6);BTNode* node7 = BuyNode(7);node1->left = node2;node1->right = node3;node2->left = node4;node2->right = node5;node3->left = node6;node5->right = node7;return node1;
}4.2 遍历
二叉树链式结构遍历的本质其实就是递归，遍历的种类有四种：前序、中序、后序和层序，我们主要看前三种；
递归的两个必要条件：
1.要有终止条件；
2.每次递归都会接近这个终止条件；
4.2.1 前序遍历
前序遍历顺序：根、左子树、右子树
void PrevOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}printf("%d ",root->data);//打印根结点PrevOrder(root->left);//遍历左子树PrevOrder(root->right);//遍历右子树
}
4.2.2 中序遍历
中序遍历顺序：左子树、根、右子树
void PrevOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}PrevOrder(root->left);//遍历左子树printf("%d ", root->data);//打印根结点PrevOrder(root->right);//遍历右子树
}4.2.3 后序遍历
后续遍历顺序：左子树、右子树、根
//后序
void PrevOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}PrevOrder(root->left);//遍历左子树PrevOrder(root->right);//遍历右子树printf("%d ", root->data);//打印根结点
}4.2.4 层序遍历
层序遍历：按照层数 从上到下，每一层从左到右来遍历。
层序遍历，又被称作广度优先遍历。这样子的遍历方式，不是直接递归就可以实现的，而是要根据队列 “先入先出” 的特点，借助队列来完成。
核心思想：首先将第一个结点放入队列中，取出头结点的同时将头结点的左右孩子分别入队，一直到队列为空。
//层序遍历
void LevelOrder(BTNode* root)
{Queue q;QInit(&q);if (root){QPush(&q, root);}while (!QEmpty(&q)){BTNode* front = QFront(&q);QPop(&q);printf("%d ", front->data);if (front->left){QPush(&q, front->left);}if (front->right){QPush(&q, front->right);}}QDestroy(&q);
}4.3 节点个数以及高度
4.3.1 节点个数
三种方法：1.全局变量：每次引用的时候都需要重新清零；
2.传值（指针）：函数传参的时候需要多传一个参数；
3.递归：直接返回节点个数；
//节点个数
int size = 0;//全局变量
void TreeSize(BTNode* root)
{if (root == NULL){return;}++size;TreeSize(root->left);TreeSize(root->right);
}void TreeSize(BTNode* root, int* psize)
{if (root == NULL){return;}(*psize)++;TreeSize(root->left,psize);TreeSize(root->right,psize);
}int TreeSize(BTNode* root)
{return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}int main()
{BTNode* root = CreatTree();PrevOrder(root);printf("\n");TreeSize(root);printf("%d\n", size);//int size = 0;//TreeSize(root,&size);//printf("%d\n",size);//int size=TreeSize(root);//printf("%d\n",size);InOrder(root);printf("\n");TreeSize(root);printf("%d\n", size);PostOrder(root);printf("\n");return 0;
}4.3.2 节点的高度
递归思想：如果左子树的深度大于右子树，返回左子树深度+1，否则返回右子树深度+1（+1代表加上当前树的根节点所在层）。
//节点高度
int TreeHeight(BTNode* root)
{if (root == NULL){return 0;}int leftHeight = TreeHeight(root->left);int rightHeight = TreeHeight(root->right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}int main()
{BTNode* root = CreatTree();int height = TreeHeight(root);printf("%d\n", height);
}4.3.3 第K层节点个数
递归思想：一方面，要判断是否到了第k层，到了第k层就直接返回1，这样子第k层之下的就不用再遍历了，免做无用功；另一方面，也是要判断传入参数是否为空，如果为空直接返回0。
//第K层节点数
int TreeKLevel(BTNode* root, int k)
{assert(k);if (root == NULL){return 0;}if (k == 1){return 1;}return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1);
}int main()
{BTNode* root = CreatTree();int KLevel = TreeKLevel(root,2);printf("%d\n", KLevel);}4.3.4 叶子节点个数
//叶子节点个数
int TreeLeafSize(BTNode* root)
{if (root == NULL){return 0;}if (root->left == NULL && root->right == NULL)//叶子节点{return 1;}return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}int main()
{BTNode* root = CreatTree();int leftsize = TreeLeafSize(root);printf("%d\n", leftsize);}
