一树的基础认知1树的概念及其术语树Tree是 nnn≥0n≥0个结点的有限集合。当 n0n0 时称为空树当 n0n0 时有且仅有一个根结点Root根结点没有前驱结点其余结点可分为 mmm0m0个互不相交的有限集合 T1,T2,...,TmT1​,T2​,...,Tm​每一个集合本身又是一棵树并且称为根的子树SubTree除根结点外每个结点有且仅有一个父结点。一棵 NN 个结点的树有 N−1N−1 条边其他术语术语含义结点的度一个结点含有的子树个数树的度树中所有结点度的最大值叶子节点终端节点度为 0 的结点分支节点度不为 0 的结点父节点双亲节点若一个结点含有子结点则该结点称为其子结点的父结点子节点孩子节点一个结点含有的子树的根结点兄弟节点具有相同父结点的结点节点的层次从根开始定义根为第 1 层树的深度高度树中结点的最大层次路径从树中任意节点出发沿父节点-子节点连接到达任意节点的序列祖先/子孙从根到某结点路径上的所有结点称为该结点的祖先反之称为子孙森林由 mmm0m0棵互不相交的树组成的集合2树的表示法孩子兄弟表示法树的结构比线性表复杂既要存储值域又要存储结点之间的关系。最常用的表示法是孩子兄弟表示法左孩子右兄弟typedef struct TreeNode { struct TreeNode* child; // 指向第一个孩子结点 struct TreeNode* brother; // 指向右边的下一个兄弟结点 int data; // 结点中的数据 } TreeNode;这种表示法的巧妙之处在于任何一棵多叉树都可以转化为一棵二叉树来存储3树形结构的实际应用最典型的应用就是文件系统。电脑中的文件夹和文件就是用树形结构来组织的——根目录下有多级子目录每个目录下又有文件和子目录层层嵌套。二二叉树1二叉树的定义二叉树Binary Tree是结点的一个有限集合该集合或者为空或者是由一个根结点加上两棵互不相交的、分别称为左子树和右子树的二叉树组成。二叉树的重要特点每个结点的度不大于 2二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树区分度为 2 的有序树 ≠ 二叉树。二叉树的子树是严格区分为“左”和“右”的即使只有一棵子树也要指明是左还是右。二叉树的五种基本形态空树、只有根结点、只有左子树、只有右子树、左右子树均存在。2两种特殊二叉树满二叉树一个二叉树如果每一层的结点数都达到最大值则这个二叉树就是满二叉树如果一个二叉树的层数为 KK且结点总数是 2K−12K−1则它就是满二叉树满二叉树的特点是所有叶子结点都在同一层所有分支结点都有两个孩子。完全二叉树对于深度为 KK 的、有 nn 个结点的二叉树当且仅当其每一个结点都与深度为 KK 的满二叉树中编号从 1 至 nn 的结点一一对应时称之为完全二叉树完全二叉树就是满二叉树“从最后一层的最右边开始连续删掉若干个结点”得到的结果3二叉树数学性质性质1若规定根结点的层数为 1则一棵非空二叉树的第 ii 层上最多有 2i−12i−1 个结点。性质2若规定根结点的层数为 1则深度为 hh 的二叉树的最大结点数是 2h−12h−1。性质3对任何一棵二叉树如果其叶子结点度为 0的个数为 n0n0​度为 2的结点个数为 n2n2​则有n0n214二叉树存储结构顺序存储数组使用数组来存储二叉树一般只适合表示完全二叉树。因为非完全二叉树用数组存储会造成大量的空间浪费。对于具有 n 个结点的完全二叉树按照从上至下、从左至右的数组顺序对所有结点从 0 开始编号则对于序号为 i 的结点有若 i0i0其双亲序号为 (i−1)/2(i−1)/2若 i0i0则为根结点若 2i1n2i1n其左孩子序号为 2i12i1否则无左孩子若 2i2n2i2n其右孩子序号为 2i22i2否则无右孩子链式存储二叉链用链表来表示二叉树每个结点由数据域和左右指针域组成typedef int BTDataType; typedef struct BinaryTreeNode { struct BinaryTreeNode* left; // 指向左孩子 struct BinaryTreeNode* right; // 指向右孩子 BTDataType val; // 数据域 } BTNode;链式结构又分为二叉链和三叉链。二叉链data left right用于普通二叉树三叉链多一个指向父结点的指针用于红黑树等高级数据结构。三堆1堆的性质堆是一种特殊的完全二叉树其物理存储结构是数组。堆具有以下性质堆中某个结点的值总是不大于或不小于其父结点的值堆总是一棵完全二叉树大堆大根堆任何一个父结点都比它的两个孩子大根是最大值。小堆小根堆任何一个父结点都比它的两个孩子小根是最小值。区分数据结构中的“堆”和操作系统虚拟进程地址空间中的“堆区”是两回事一个是数据结构一个是操作系统中管理内存的一块区域分段。2堆的代码实现typedef int HPDataType; typedef struct Heap { HPDataType* arr; // 动态数组 int size; // 当前有效元素个数 int capacity; // 数组最大容量 } HP; // 函数声明 void HPInit(HP* php); void HPDestroy(HP* php); void HPPush(HP* php, HPDataType x); void HPPop(HP* php); HPDataType HPTop(HP* php); bool HPEmpty(HP* php); int HPSize(HP* php);初始化与销毁void HPInit(HP* php) { assert(php ! NULL); php-arr NULL; php-size 0; php-capacity 0; } void HPDestroy(HP* php) { assert(php ! NULL); if (php-arr ! NULL) { free(php-arr); // 数组是一次性 malloc 的一次 free 即可 php-arr NULL; } php-size 0; php-capacity 0; // 注意不 free(php)因为 php 通常在栈上定义 }free(php-arr)一次释放整块连续内存不需要像链表那样逐个遍历释放。因为数组是连续内存malloc 一次申请free 一次释放。扩容函数void CheckCapacity(HP* php) { assert(php ! NULL); if (php-size php-capacity) { return; } int newCapacity (php-capacity 0) ? 4 : php-capacity * 2; HPDataType* tmp (HPDataType*)realloc(php-arr, newCapacity * sizeof(HPDataType)); if (tmp NULL) { perror(realloc fail); exit(-1); } php-arr tmp; php-capacity newCapacity; }realloc的返回值必须用临时变量接收防止扩容失败时原数据丢失。向上调整算法AdjustUp使用场景插入新元素后新元素可能破坏堆的性质需要让它“向上爬”到合适位置。核心逻辑新插入的结点与其父结点比较如果违反堆的规则大堆中孩子 父亲则交换继续向上比较直到满足堆的性质或到达根结点。void AdjustUp(HPDataType* arr, int child) { while (child 0) { // ⚠️ 条件必须是 child 0不能是 0 int parent (child - 1) / 2; if (arr[parent] arr[child]) { // 大堆父 子满足条件 break; } // 交换 HPDataType tmp arr[parent]; arr[parent] arr[child]; arr[child] tmp; child parent; // 继续向上 } }为什么循环条件是child 0而不是child 0如果写成child 0当child变为 0 后child--会变成 -1但-1 0为假循环退出——看起来没问题。但更关键的是child 0保证了在child 0时不会执行循环体避免计算parent (0 - 1) / 2 0导致的死循环风险。向上调整建堆的时间复杂度为O(Nlog⁡N)堆的插入Pushvoid HPPush(HP* php, HPDataType x) { assert(php ! NULL); CheckCapacity(php); int child php-size; // 新结点插入位置 php-arr[child] x; // 放入数据 php-size; // 先 size再调整 AdjustUp(php-arr, child); // 向上调整 }向下调整算法AdjustDown使用场景删除堆顶后将最后一个元素移到堆顶然后让它“向下沉”到合适位置。前提条件左右子树必须已经是堆核心逻辑大堆为例假设左孩子是较大的孩子如果右孩子存在且比左孩子大则改为指向右孩子假设法的精髓如果孩子比父亲大交换继续向下否则停止void AdjustDown(HPDataType* arr, int size, int parent) { int child parent * 2 1; // 先假设左孩子是较大的 while (child size) { // 如果右孩子存在且比左孩子大则改为右孩子 if (child 1 size arr[child 1] arr[child]) { child; } if (arr[child] arr[parent]) { HPDataType tmp arr[parent]; arr[parent] arr[child]; arr[child] tmp; parent child; child parent * 2 1; } else { break; } } }向下调整建堆的时间复杂度为O(N)堆的删除Popvoid HPPop(HP* php) { assert(php ! NULL); assert(php-size 0); // 1. 交换堆顶和最后一个元素 HPDataType tmp php-arr[0]; php-arr[0] php-arr[php-size - 1]; php-arr[php-size - 1] tmp; // 2. size--逻辑删除最后一个元素即原来的最大值 php-size--; // 3. 向下调整 AdjustDown(php-arr, php-size, 0); }3堆排序Heap Sort版本一借助堆结构空间复杂度 O(N)void HeapSort(int* a, int n) { HP hp; HPInit(hp); for (int i 0; i n; i) { HPPush(hp, a[i]); } int i 0; while (!HPEmpty(hp)) { a[i] HPTop(hp); HPPop(hp); } HPDestroy(hp); }版本二原地堆排序空间复杂度 O(1)void HeapSort(int* a, int n) { // 1. 向下调整建堆 O(N) // 从最后一个非叶子结点开始 for (int i (n - 1 - 1) / 2; i 0; i--) { AdjustDown(a, n, i); } // 2. 排序 O(N log N) int end n - 1; while (end 0) { Swap(a[0], a[end]); // 堆顶最大值放到末尾 AdjustDown(a, end, 0); // 调整剩余部分 end--; } }4Top-K 问题问题描述从海量数据中找出最大或最小的 K 个数。核心思路找最大的 K 个数用数据集合中前 K 个元素建小堆用剩余的 N−KN−K 个元素依次与堆顶元素比较如果比堆顶大则替换堆顶并向下调整void CreateNDate() { int n 100000; srand(time(0)); const char* file data.txt; FILE* fin fopen(file, w); for (int i 0; i n; i) { int x (rand() i) % 1000000; fprintf(fin, %d\n, x); } fclose(fin); } void topk(int k) { const char* file data.txt; FILE* fout fopen(file, r); int* minheap (int*)malloc(sizeof(int) * k); for (int i 0; i k; i) { fscanf(fout, %d, minheap[i]); } // 建小堆 for (int i (k - 1 - 1) / 2; i 0; i--) { AdjustDown(minheap, k, i); } int x 0; while (fscanf(fout, %d, x) ! EOF) { if (x minheap[0]) { minheap[0] x; AdjustDown(minheap, k, 0); } } for (int i 0; i k; i) { printf(%d , minheap[i]); } fclose(fout); }为什么找最大的 K 个数要建小堆因为小堆的堆顶是堆中最小的元素它就像一个“门槛”。新来的数只要比门槛高就踢掉门槛进来然后重新选出最小的当门槛。遍历完所有数据后堆里剩下的就是最大的 K 个数。Top-K 时间复杂度O(K(N−K)log⁡K) ≈ O(Nlog⁡K)四链式二叉树1二叉链结构体定义 手动建树typedef int BTDataType; typedef struct BinaryTreeNode { struct BinaryTreeNode* left; struct BinaryTreeNode* right; BTDataType val; } BTNode; BTNode* BuyBTNode(int val) { BTNode* newnode (BTNode*)malloc(sizeof(BTNode)); if (newnode NULL) { perror(malloc fail); return NULL; } newnode-val val; newnode-left NULL; newnode-right NULL; return newnode; } // 手动创建一棵测试树 BTNode* CreateTree() { BTNode* n1 BuyBTNode(1); BTNode* n2 BuyBTNode(2); BTNode* n3 BuyBTNode(3); BTNode* n4 BuyBTNode(4); BTNode* n5 BuyBTNode(5); BTNode* n6 BuyBTNode(6); BTNode* n7 BuyBTNode(7); n1-left n2; n1-right n4; n2-left n3; n4-left n5; n4-right n6; n5-left n7; return n1; }2四大遍历递归版遍历// 前序遍历根 → 左 → 右 void PreOrder(BTNode* root) { if (root NULL) { printf(N ); return; } printf(%d , root-val); PreOrder(root-left); PreOrder(root-right); } // 中序遍历左 → 根 → 右 void InOrder(BTNode* root) { if (root NULL) { printf(N ); return; } InOrder(root-left); printf(%d , root-val); InOrder(root-right); } // 后序遍历左 → 右 → 根 void PostOrder(BTNode* root) { if (root NULL) { printf(N ); return; } PostOrder(root-left); PostOrder(root-right); printf(%d , root-val); }层序遍历Level Order层序遍历需要借助队列FIFO实现从上到下、从左到右逐层访问void LevelOrder(BTNode* root) { if (root NULL) return; Queue q; QueueInit(q); QueuePush(q, root); while (!QueueEmpty(q)) { BTNode* front QueueFront(q); QueuePop(q); printf(%d , front-val); if (front-left) QueuePush(q, front-left); if (front-right) QueuePush(q, front-right); } QueueDestroy(q); }3二叉树属性计算递归分治结点个数int BinaryTreeSize(BTNode* root) { if (root NULL) return 0; return 1 BinaryTreeSize(root-left) BinaryTreeSize(root-right); }叶子结点个数int BinaryTreeLeafSize(BTNode* root) { if (root NULL) return 0; if (root-left NULL root-right NULL) return 1; return BinaryTreeLeafSize(root-left) BinaryTreeLeafSize(root-right); }第 K 层结点个数int BinaryTreeLevelKSize(BTNode* root, int k) { if (root NULL) return 0; if (k 1) return 1; return BinaryTreeLevelKSize(root-left, k - 1) BinaryTreeLevelKSize(root-right, k - 1); }二叉树深度/高度int BinaryTreeDepth(BTNode* root) { if (root NULL) return 0; int leftDepth BinaryTreeDepth(root-left); int rightDepth BinaryTreeDepth(root-right); return 1 (leftDepth rightDepth ? leftDepth : rightDepth); }求深度是1 max(左, 右)不是1 左 右。后者算的是结点总数查找值为 x 的结点BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { if (root NULL) return NULL; if (root-val x) return root; BTNode* leftResult BinaryTreeFind(root-left, x); if (leftResult ! NULL) return leftResult; // 左子树找到了短路返回 return BinaryTreeFind(root-right, x); }4判断是否为完全二叉树核心思想层序遍历的变种——把 NULL 也入队。遇到第一个 NULL 后检查队列中剩余的是否全是 NULL。bool BinaryTreeComplete(BTNode* root) { if (root NULL) return true; Queue q; QueueInit(q); QueuePush(q, root); while (!QueueEmpty(q)) { BTNode* front QueueFront(q); QueuePop(q); if (front NULL) { break; // 遇到第一个空节点停止继续入队 } QueuePush(q, front-left); QueuePush(q, front-right); } // 检查队列中剩余的是否全是 NULL while (!QueueEmpty(q)) { BTNode* front QueueFront(q); QueuePop(q); if (front ! NULL) { QueueDestroy(q); return false; } } QueueDestroy(q); return true; }遇到 NULL 时不能直接返回 false必须继续检查后面的节点5二叉树的销毁void BinaryTreeDestroy(BTNode** root) { if (root NULL || *root NULL) return; BinaryTreeDestroy(((*root)-left)); BinaryTreeDestroy(((*root)-right)); free(*root); *root NULL; // 将外部指针置空防止野指针 }