数据结构——二叉树

本章代码仓库：堆、二叉树链式结构

🍭1. 树

🧁1.1 树的概念

树是一种非线性的数据结构，由n个有限节点组成的一个具有层次关系的有限集。

在任意一颗非空的树中：

• 有且具有一个特定的节点称为root节点
• 除根节点外，其他节点被分成M个不互相交的有限集
• 每棵子树根节点有且仅有一个前驱节点，可以有0个或者多个后继节点
• 树是递归定义的

节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：B的度为4

叶节点或终端节点：度为0的节点称为叶节点（没有孩子）； 如上图：D、J、K、F、G、H、I

非终端节点或分支节点：度不为0的节点（有孩子）； 如上图：B、C、E

双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点

孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点

兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点

树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为4

节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；

树的高度或深度：树中节点的最大层次； 如上图：树的高度为4

堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：G、H互为堂兄弟节点

节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先

子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙

森林：由m（m>0）棵互不相交的树的集合称为森林；

🧁1.2 树的结构

树的结构如果用线性结构，就会蛮复杂，假设我们知道树的度为5，那我们就可以定义一个指针数组来表示每层的节点

#define N 5
struct TreeNode
{struct TreeNode* children[N];	//指针数组
};

在一般情况下，我们都是不知道树的度，如果采用线性结构，十分不便

struct TreeNode
{SeqList sl;	//存节点指针int val;
}

所以在实际中，一般采用孩子兄弟表示法

typedef int DateType;
struct TreeNode
{struct TreeNode* _firstChild;	//第一个孩子节点struct TreeNode* _pNextBrother;	//兄弟节点DateType _val;	//数据
};

树在数据结构中并不常用，树在实际中的典型应用就是文件系统，一层一层的

将Code文件看作根节点，下面的cpp、remake-c、linux等就能看作是它的孩子节点

然后这些文件里面又包含了其他文件，层层推进

🍬2. 二叉树

🍫2.1 二叉树的概念

二叉树可以看作一个进行了“计划生育”的树

二叉树的特点：

• 每个节点至多有两颗子树（不存在度大于2的节点）
• 左子树右子树有顺序，次序不可颠倒（好比人的左右手），即使某个节点只要一棵子树，也要区分是左子树还是右子树

🍫2.2 特殊的二叉树

1. 满二叉树

   满二叉树就是所有的分支节点都有左右子树，并且所有叶子都在同一层

   假设二叉树的深度为K，则总节点数则为2^k-1

   

2. 完全二叉树

   完全二叉树从根节点开始，从左到右依次填充节点，直到最后一层，最后一层的节点可以不满，但节点都尽量靠左排列

   满二叉树定是完全二叉树（正方形也是一种特殊的长方形）

   

🍫2.3 二叉树的性质

1. 一颗非空二叉树第i层至多有**2^i-1**个结点

2. 深度为k的二叉树至多有2^k-1 个结点

3. 对于任何一颗二叉树，如果终端叶子节点为n₀，度为2的结点数为n₂，则n₀ = n₂ + 1

4. 有n个结点的满二叉树的深度h = log₂(n+1)

   高度为h的完全二叉树，结点数量范围：[2^h-1，2^h-1]

5. 对于具有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.4 二叉树的存储结构

二叉树的存储结构可分为顺序存储和链式存储：

1. 顺序存储

   顺序存储就是用数组来存储，这一般适用于完全二叉树，因为这样不会造成空间的浪费

   这在物理上是一个数组，但在逻辑上是一颗二叉树

   

2. 链式存储

   顾名思义，采用链表来表示这颗二叉树

   

   typedef int DateType;
   struct TreeNode
   {struct TreeNode* _lChild;	//左孩子struct TreeNode* _rChild;	//右孩子DateType _val;	//数据
   };
   

🍯3. 堆

堆是一颗完全二叉树，堆中的每个节点都满足堆序性质，即在最大堆中，每个节点的值都大于或等于其子节点的值；在最小堆中，每个节点的值都小于或等于其子节点的值。

🍼3.1 堆的实现

下面以大根堆为例：

🥛接口声明

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#define CAPACITY 4typedef int HPDateType;
typedef struct Heap
{HPDateType* val;int _size;int _capacity;
}HP;//初始化
void HeapInit(HP* php);
//插入数据
void HeapPush(HP* php, HPDateType x);
//删除堆顶元素
void HeapPop(HP* php);
//获取堆顶元素
HPDateType HeapTop(HP* php);
//是否有元素
bool HeapEmpty(HP* php);
//获取当前堆的元素数量
int HeapSize(HP* php);
//销毁
void HeapDestroy(HP* php);void AdjustUp(HPDateType* val, int child);
void AdjustDown(HPDateType* val, int sz, int parent);
void Swap(HPDateType* x1, HPDateType* x2);

🥛接口实现

#define _CRT_SECURE_NO_WARNINGS 1
#pragma warning(disable:6031)
#include"Heap.h"//初始化
void HeapInit(HP* php)
{assert(php);php->val = (HPDateType*)malloc(sizeof(HPDateType) * CAPACITY);if (php->val == NULL){perror("malloc fail");exit(-1);}php->_size = 0;php->_capacity = CAPACITY;
}
//交换元素
void Swap(HPDateType* x1, HPDateType* x2)
{HPDateType tmp = *x1;*x1 = *x2;*x2 = tmp;
}
//向上调整 前提子树是堆
void AdjustUp(HPDateType* val, int child)
{int parent = (child - 1) / 2;while (child > 0){if (val[child] > val[parent]){Swap(&val[child], &val[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}
//向下调整 前提：子树都是堆
void AdjustDown(HPDateType* val, int sz, int parent)
{//默认左孩子大int child = parent * 2 + 1;//至多叶子结点结束while (child < sz){//不越界 选出更大的孩子if (child+1<sz && val[child] < val[child+1]){child++;}if (val[child] > val[parent]){Swap(&val[child], &val[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
//插入数据
void HeapPush(HP* php, HPDateType x)
{assert(php);if (php->_size == php->_capacity){//扩容HPDateType* tmp = realloc(php->val, sizeof(HPDateType) * php->_capacity * 2);if (tmp == NULL){perror("realloc fail");exit(-1);}php->val = tmp;php->_capacity *= 2;}php->val[php->_size] = x;php->_size++;AdjustUp(php->val, php->_size - 1);
}
//删除堆顶元素
void HeapPop(HP* php)
{assert(php);assert(!HeapEmpty(php));Swap(&php->val[0], &php->val[php->_size - 1]);php->_size--;AdjustDown(php->val, php->_size, 0);
}
//获取堆顶元素
HPDateType HeapTop(HP* php)
{assert(php);return php->val[0];
}
//是否有元素
bool HeapEmpty(HP* php)
{assert(php);return php->_size == 0;
}
//获取当前堆的元素数量
int HeapSize(HP* php)
{assert(php);return php->_size;
}
//销毁
void HeapDestroy(HP* php)
{free(php->val);php->val = NULL;php->_size = 0;php->_capacity = 0;
}

🍼3.2 堆排序

🥛堆排序实现

堆排序分为两个步骤：

1. 建堆

   排升序：建大堆

   排降序：建小堆

2. 堆删除的思想进行排序

如果排升序，堆顶元素是最大的，将其与最后一个元素交换，这就是堆的删除操作，但我们不需要将这个数据删除，交换完不管它即可，这样最后一个元素就是最大的，然后再向下调整，再找出最大的元素，以此反复，则可完成升序的排序。

使用堆排序，不需要手搓一个数据结构堆出来，我们只需要建堆和模拟删除操作即可

//排升序 建大堆
void HeapSort(int* pa, int sz)
{//向上调整 建堆 O(N*logN)//for (int i = 0; i < sz; i++)//{//	AdjustUp(pa, i);//}//向下调整 O(N)for (int i = (sz - 1 - 1) / 2; i >= 0; --i){AdjustDown(pa, sz, i);}//向下调整排序 O(N*logN)for (int i = 0; i < sz; i++){Swap(&pa[0], &pa[sz - 1 - i]);AdjustDown(pa, sz - 1 - i, 0);}}

🥛堆排序时间复杂度

建堆操作可以采用向上调整，也可以采用向下调整，但是向下调整的效率是高于向上调整的

☕向下调整时间复杂度

向下调整是从第h-1层开始的

层数	结点数	向下移动层数
1	2^0	h-1
2	2^1	h-2
3	2^2	h-3
h-1	2^(h-2)	1

调整次数：

T(N) = 2^h-1 * 1 + 2^h-2 * 2 + 2^h-3 * 3 + … + 2² * (h-3) + 2¹ * (h-2) + 2⁰ * (h-1)

化简得：T(N) = 2^h -1 - h

高度为h的满二叉树结点个数为：N = 2^h - 1

这样即可推出时间复杂度为：N - log₂(N+1)，N和logN不在一个量级，则时间复杂度为O(N)

过程示例：

☕向上调整时间复杂度

向上调整建堆是从第二层开始调整的

层数	结点数	向上移动层数
2	2^1	1
3	2^2	2
h-1	2^(h-2)	h-2
h	2^(h-1)	h-1

调整次数：

T(N) = 2¹ * 1 + 2² * 2 + … + 2^h-1 * (h-2) + 2^h-1 * (h-1)

化简得：T(N) = -2^h + 2 + 2^h * h - 2^h = 2^h * h - 2^h * 2 + 2

高度为h的满二叉树结点个数为：N = 2^h - 1

推出时间复杂度为：(N+1)*log₂(N+1) - 2*(N+1) + 2，N和logN不在一个量级，则时间复杂度为O(N*logN)

过程示例：

这里也很好比较：

向上调整建堆时，结点数多的地方，调整次数多；

而向下调整建堆时，结点数多的地方，调整次数少，所以采用向下调整建堆时，效率会高于向上调整

☕调堆时间复杂度

建完堆直接，我们只能保证栈顶元素是最大/最下的，要完成排序，还需要调堆

调堆采用的是删除堆顶元素的逻辑，N个元素，每次调整的时间复杂度为：O(logN)，则整个堆排序时间复杂度为：N*log(N)

🍼3.3 Top-K

在现实的世界中，大部分只关注前多少多少，例如：我国排名前十的大学、一个专业学生成绩的前五等等。

这些都是排序，如果数据量较大，数据可能不会一下子就全部加载到内存当中，那我们就可以采用Top-K的思路解决：

用数据集合中的前k个来建堆，然后再用剩余的N-K个元素依次与堆顶元素比较

• 前k个最大元素，建小堆
• 前k个最小元素，建大堆

例如要在十万个数据当中找出5个最大/最小的数据，只需要建一个存储5个元素的堆

以前5个最大元素为例，那就是建小堆，那堆顶元素则是最小的，每次只需将堆顶元素和数据进行对比，如果大于堆顶元素，则替换掉堆顶元素，然后进堆，这样就一直保证，堆顶元素是这个堆中最小的元素

场景模拟：

一万个小于一万的随机数，找出前k个最大元素

void Print_TopK(const char* file, int k)
{int* topk = (int*)malloc(sizeof(int) * 5);if (topk == NULL){perror("malloc fail");exit(-1);}FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen fail");exit(-1);}//读取前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);}//将剩余元素与堆顶元素比较，大于堆顶元素则替换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);topk = NULL;fclose(fout);
}
//造数据
void CreateDate()
{int n = 10000;srand((int)time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen fail");exit(-1);}for (size_t i = 0; i < n; i++){int x = rand() % 10000;fprintf(fin, "%d\n", x);}fclose(fin);
}

🍾4. 链式二叉树结构实现

🍷4.1 手搓链式

堆属于一种线性二叉树，对于链式二叉树，本次采用手搓的方式创建

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("malloc fail");exit(-1);}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);BTNode* node8 = BuyNode(8);node1->left = node2;node1->right = node4;;node2->left = node3;node3->right = node7;node7->left = node8;node4->left = node5;node4->right = node6;return node1;
}

🍷4.2 二叉树遍历

🍻前序遍历

前序遍历也叫做先序遍历，访问顺序：根 -> 左子树 -> 右子树

//前序遍历:根 左子树 右子树
void PreOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}printf("%d ", root->data);PreOrder(root->left);PreOrder(root->right);
}

🍻中序遍历

中序遍历访问顺序：左子树 -> 根 -> 右子树

//中序遍历：左子树 根 右子树
void InOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}

🍻后序遍历

后序遍历访问顺序：左子树 -> 右子树 -> 根

//后序遍历：左子树 右子树 根
void PostOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);
}

🍻层序遍历

层序遍历与前三种不一样，层序遍历采用队列的方式实现：

首先根节点进队列，当遍历根节点之后，根节点出队列的同时把左右孩子带进去

然后再两个孩子依次出队，同时带入孩子的孩子，依次反复

void LevelOrder(BTNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);printf("%d ", front->data);if(front->left)QueuePush(&q, front->left);if (front->right)QueuePush(&q, front->right);}QueueDestroy(&q);
}

🍷4.3 二叉树结点个数

统计左子树和右子树的结点，然后再加上自己的一个

//树的结点树
int TreeSize(BTNode* root)
{return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

🍷4.4 树的深度

这里每次都要记录每次统计的结点个数，不然每次每层都得重新统计(如：注释代码块)

//树的深度
int TreeHeight(BTNode* root)
{if (root == NULL){return 0; }//记录深度int left = TreeHeight(root->left)+1;int right = TreeHeight(root->right)+1;printf("%d %d\n", left, right);return left>right?left:right;//return root==NULL?0: TreeHeight(root->left) > TreeHeight(root->right) ? TreeHeight(root->left)+1 : TreeHeight(root->right)+1;
}

🍷4.5 K层结点个数

//K层结点个数
int TreeKLevel(BTNode* root, int k)
{if (root == NULL)return 0;if (k == 1)return 1;int leftChild = TreeKLevel(root->left, k - 1);int rightChild = TreeKLevel(root->right, k - 1);return leftChild + rightChild;}

🍷4.6 查找值为x的结点

//查找值为x的结点
BTNode* TreeFind(BTNode* root, BTDataType x)
{if (root == NULL)return NULL;if (root->data == x)return root;//记录结点BTNode* leftNode = TreeFind(root->left, x);BTNode* rightNode = TreeFind(root->right, x);if (leftNode)return leftNode;else if (rightNode)return rightNode;return NULL;
}

root->left) > TreeHeight(root->right) ? TreeHeight(root->left)+1 : TreeHeight(root->right)+1;
}

## 4.5 K层结点个数```c
//K层结点个数
int TreeKLevel(BTNode* root, int k)
{if (root == NULL)return 0;if (k == 1)return 1;int leftChild = TreeKLevel(root->left, k - 1);int rightChild = TreeKLevel(root->right, k - 1);return leftChild + rightChild;}

🍷4.6 查找值为x的结点

//查找值为x的结点
BTNode* TreeFind(BTNode* root, BTDataType x)
{if (root == NULL)return NULL;if (root->data == x)return root;//记录结点BTNode* leftNode = TreeFind(root->left, x);BTNode* rightNode = TreeFind(root->right, x);if (leftNode)return leftNode;else if (rightNode)return rightNode;return NULL;
}