1. 树1.1 树的概念与结构树是一种非线性的数据结构它是由 nn0 个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像⼀棵倒挂的树也就是说它是根朝上而叶朝下的。有一个特殊的结点称为根结点根结点没有前驱结点。除根结点外其余结点被分成 M(M0) 个互不相交的集合 T1、T2、……、Tm 其中每⼀个集合Ti(1 i m) 又是一棵结构与树类似的⼦树。每棵⼦树的根结点有且只有一个前驱可以有 0 个或多个后继。因此树是递归定义的。树形结构中子树之间不能有交集否则就不是树形结构非树形结构子树是不相交的如果存在相交就是图了图以后得课程会有讲解除了根结点外每个结点有且仅有⼀个父结点⼀棵N个结点的树有N-1条边1.2 树相关术语夫结点/双亲结点若一个结点含有⼦结点则这个结点称为其子结点的父结点 如上图A是B的父结点子结点/孩子结点一个结点含有的子树的根结点称为该结点的子结点 如上图B是A的孩子结点结点的度一个结点有几个孩子他的度就是多少比如A的度为6F的度为2K的度为0树的度一棵树中最大的结点的度称为树的度 如上图树的度为 6叶子结点/终端结点度为 0 的结点称为叶结点 如上图 B、C、H、I... 等结点为叶结点分支结点/非终端结点度不为 0 的结点 如上图 D、E、F、G... 等结点为分支结点兄弟结点具有相同父结点的结点互称为兄弟结点(亲兄弟) 如上图 B、C 是兄弟结点结点的层次从根开始定义起根为第 1 层根的子结点为第 2 层以此类推树的高度或深度树中结点的最大层次 如上图树的高度为 4结点的祖先从根到该结点所经分支上的所有结点如上图 A 是所有结点的祖先路径一条从树中任意节点出发沿父节点-子节点连接达到任意节点的序列比如A到Q的路径为A-E-J-QH到Q的路径H-D-A-E-J-Q子孙以某结点为根的子树中任⼀结点都称为该结点的子孙。如上图所有结点都是A的子孙森林由 mm0 棵互不相交的树的集合称为森林1.3 树的表示孩子兄弟表示法树结构相对线性表就比较复杂了要存储表示起来就比较麻烦了既然保存值域也要保存结点和结点之间的关系实际中树有很多种表示方式如双亲表示法孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法struct TreeNode { struct Node* child; // 左边开始的第⼀个孩⼦结点 struct Node* brother; // 指向其右边的下⼀个兄弟结点 int data; // 结点中的数据域 };1.4 树形结构实际运用场景文件系统是计算机存储和管理文件的一种方式它利用树形结构来组织和管理文件和文件夹。在文件系统中树结构被光泛应用它通过父结点和子结点之间的关系来表示不同层级的文件和文件夹之间的关联。2. 二叉树2.1 概念与结构在树形结构中我们最常用的就是二叉树一棵二叉树是结点的⼀个有限集合该集合由⼀个根结点加上两棵别称为左子树和右子树的二叉树组成或者为空。从上图可以看出二叉树具备以下特点1. 二叉树不存在度大于 2 的结点2. 二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树注意对于任意的二叉树都是由以下几种情况复合而成的2.2 特殊的二叉树2.2.1 满而叉树一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉树。也就是说如一个二叉树的层数为 K 且结点总数是 2 K− 1 则它就是满二叉树。2.2.2 完全二叉树完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为 K 的有 n 个结点的二叉树当且仅当其每⼀个结点都与深度为K的满二叉树中编号从 1 ⾄ n 的结点一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。普通二叉树 A / B \ C完全二叉树 A / \ B C / \ / D E F二叉树性质根据满二叉树的特点可知1若规定根结点的层数为 1 则⼀棵非空二叉树的第i层上最多有 2 i− 1 个结点2若规定根结点的层数为 1 则深度为 h 的⼆叉树的最⼤结点数是 2 ^ h− 13若规定根结点的层数为 1 具有 n 个结点的满二叉树的深度 h log2 (n 1) ( log以2为底 n1 为对数)2.3 二叉树存储结构二叉树⼀般可以使用两种结构存储⼀种顺序结构⼀种链式结构。2.3.1 顺序结构顺序结构存储就是使用数组来存储⼀般使用数组只适合表示完全二叉树因为不是完全⼆叉树会有空间的浪费完全⼆叉树更适合使用顺序结构存储。现实中我们通常把堆⼀种二叉树使用顺序结构的数组来存储需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事⼀个是数据结构⼀个是操作系统中管理内存的一块区域分段。2.3.2 链式结构二叉树的链式存储结构是指用链表来表示⼀棵二叉树即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链当前我们学习中⼀般都是二叉链。后面课程学到高阶数据结构如红黑树等会用到三叉链。3. 实现顺序结构二叉树⼀般堆使用顺序结构的数组来存储数据堆是一种特殊的二叉树具有二叉树的特性的同时还具备其他的特性。3.1 堆的概念与结构如果有一个关键码的集合K {k0 ,k1 ,k2 , ...kn−1 } 把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中并满足KiK2∗i1 KiK2∗i1 且KiK2∗i2 i 0、1、2... 则称为小堆(或大堆)。将根结点最大的堆叫做最大堆或大根堆根结点最小的堆叫做最小堆或小根堆。堆具有以下性质堆中某个结点的值总是不大于或不小于其父结点的值堆总是一棵完全二叉树。二叉树性质对于具有 n 个结点的完全二叉树如果按照从上至下从左至右的数组顺序对所有结点从0 开始编号则对于序号为 i 的结点有1. 若 i0 i 位置结点的双亲序号 (i-1)/2 i0 i 为根结点编号无双亲结点2. 若 2i1n 左孩子序号 2i1 2i1n 否则无左孩子3. 若 2i2n 右孩子序号 2i2 2i2n 否则无右孩子3.2 堆的实现堆底层结构为数组因此定义堆的结构为typedef int HPDataType; typedef struct Heap { HPDataType* a; int size; int capacity; }HP; //默认初始化堆 void HPInit(HP* php); //利⽤给定数组初始化堆 void HPInitArray(HP* php, HPDataType* a, int n); //堆的销毁 void HPDestroy(HP* php); //堆的插⼊ void HPPush(HP* php, HPDataType x); //堆的删除 HPDataType HPTop(HP* php); // 删除堆顶的数据 void HPPop(HP* php); // 判空 bool HPEmpty(HP* php); //求size int HPSize(HP* php); //向上调整算法 void AdjustUp(HPDataType* a, int child); //向下调整算法 void AdjustDown(HPDataType* a, int n, int parent);3.2.1 向上调整算法堆的插入将新数据插入到数组的尾上再进行向上调整算法直到满足堆。向上调整算法先将元素插入到堆的末尾,即最后⼀个孩子之后插入之后如果堆的性质遭到破坏将新插入结点顺着其双双亲往上调整到合适位置即可void AdjustUp(HPDataType* a, int child) { int parent (child - 1) / 2; while(child 0) { if (a[child] a[parent]) { Swap(a[child], a[parent]); child parent; parent (parent - 1) / 2; } else { break; } } } void HPPush(HP* php, HPDataType x) { assert(php); if (php-size php-capacity) { size_t newCapacity php-capacity 0 ? 4 : php-capacity * 2; HPDataType* tmp realloc(php-a, sizeof(HPDataType) * newCapacity); if (tmp NULL) { perror(realloc fail); return; } php-a tmp; php-capacity newCapacity; } php-a[php-size] x; php-size; AdjustUp(php-a, php-size-1); }计算向上调整算法建堆时间复杂度因为堆是完全二叉树⽽满二叉树也是完全二叉树此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值多几个结点不影响最终结果)分析第1层 2 ^ 0 个结点需要向上移动0层第2层 2 ^ 1 个结点需要向上移动1层第3层 2 ^ 2 个结点需要向上移动2层第4层 2 ^ 3 个结点需要向上移动3层......第h层 2 ^ (h−1) 个结点需要向上移动h-1层则需要移动结点总的移动步数为每层结点个数 * 向上调整次数第一层调整次数为0T(h) 2 ^ 1 ∗ 1 2 ^ 2 ∗ 2 2 3 ∗ 3 .. 2 ^h−2 ∗ (h− 2) 2 ^ (h−1) ∗ (h− 1) ①2 ∗T(h) 2 ^ 2 ∗ 1 2 ^ 3 ∗ 2 2 ^ 4 ∗ 3 .. 2 ^h−1 ∗ (h− 2) 2 ^h∗ (h− 1) ②② ⼀ ① 错位相减T(h) −2 ^ 1 ∗ 1 − (2 ^ 2 2 ^ 3 .. 2 ^ (h−2) 2 ^ (h−1) ) 2 ^h∗ (h− 1)T(h) −2 ^ 0 − 2 ^ 1 ∗ 1 − (2 ^ 2 2 ^ 3 .. 2 ^ (h−2) 2 ^ (h−1) ) 2 ^h∗ (h− 1) 2 ^ 0T(h) −(2 ^ 0 2 ^ 1 ∗ 1 2 ^ 2 2 ^ 3 .. 2 ^ (h−2) 2 ^ (h−1) ) 2 ^h∗ (h− 1) 2 ^ 0T(h) −(2 ^h− 1) 2 ^h∗ (h− 1) 2 ^ 0根据二叉树的性质n 2 ^h− 1 和hlog2 (n 1)T(n) −N 2 ^h∗ (h− 1) 2 ^ 0F(h) 2 ^h *(h− 2) 2F(n) (n 1)(log2 (n 1) − 2) 2由此可得向上调整算法建堆时间复杂度为O(n∗ log2n)3.2.2 向下调整算法堆的删除删除堆是删除堆顶的数据将堆顶的数据根最后⼀个数据⼀换然后删除数组最后⼀个数据再进行向下调整算法。向下调整算法有⼀个前提左右子树必须是⼀个堆才能调整。向下调整算法将堆顶元素与堆中最后一个元素进行交换删除堆中最后一个元素将堆顶元素向下调整到满足堆特性为止void AdjustDown(HPDataType* a, int n, int parent) { int child parent * 2 1; while (child n) { // 假设法选出左右孩⼦中⼩的那个孩⼦ if (child1 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 HPPop(HP* php) { assert(php); assert(php-size 0); Swap(php-a[0], php-a[php-size - 1]); php-size--; AdjustDown(php-a, php-size, 0); }计算向下调整算法建堆时间复杂度分析第1层 2 ^ 0 个结点需要向下移动h-1层第2层 2 ^ 1 个结点需要向下移动h-2层第3层 2 ^ 2 个结点需要向下移动h-3层第4层 2 ^ 3 个结点需要向下移动h-4层......第h-1层 2 ^ h−2 个结点需要向下移动1层则需要移动结点总的移动步数为每层结点个数 * 向下调整次数①T(h) 2 ^ 0 ∗ (h− 1) 2 ^ 1 ∗ (h− 2) 2 ^ 2 ∗ (h− 3) 2 ^ 3 ∗ (h− 4) .. 2 ^ (h−3) ∗ 2 2 ^ (h−2) ∗ 1②2 ∗T(h) 2 ^ 1 ∗ (h− 1) 2 ^ 2 ∗ (h− 2) 2 ^ 3 ∗ (h− 3) 2 ^ 4 ∗ (h− 4) ... 2 ^ (h−2) ∗ 2 2 ^ (h−1) ∗ 1② ⼀ ① 错位相减T(h) 1 −h 2 ^ 1 2 ^ 2 2 ^ 3 2 ^ 4 .. 2 ^ (h−2) 2 ^ (h−1)T(h) 2 ^ 0 2 ^ 1 2 ^ 2 2 ^ 3 2 ^ 4 .. 2 ^ (h−2) 2 ^ (h−1) −hT(h) 2 ^h− 1 −h根据二叉树的性质n 2h− 1 和hlog2 (n 1)T(n) n−log2 (n 1) ≈n向下调整算法建堆时间复杂度为O(n)3.3 堆的应用3.3.1 堆排序版本一基于已有数组建堆、取堆顶元素完成排序版本// 1、需要堆的数据结构 // 2、空间复杂度 O(N) void HeapSort(int* a, int n) { HP 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(N*logN) void HeapSort(int* a, int n) { // a数组直接建堆 O(N) for (int i (n-1-1)/2; i 0; --i) { AdjustDown(a, n, i); } // O(N*logN) int end n - 1; while (end 0) { Swap(a[0], a[end]); AdjustDown(a, end, 0); --end; } }堆排序时间复杂度计算分析第1层2^0个结点交换到根结点后需要向下移动0层第2层2^1个结点交换到根结点后需要向下移动1层第3层2^2个结点交换到根结点后需要向下移动2层第4层2^3个结点交换到根结点后需要向下移动3层......第h层2^h−1个结点交换到根结点后需要向下移动h-1层通过分析发现堆排序第⼆个循环中的向下调整与建堆中的向上调整算法时间复杂度计算⼀致此处不再赘述。因此堆排序的时间复杂度为O(nn∗ logn)即O(nlogn)堆排序时间复杂度为O(nlogn)3.3.2 TOP-K问题TOP-K问题即求数据结合中前K个最大的元素或者最小的元素一般情况下数据量都比较大。比如专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。对于Top-K问题能想到的最简单直接的方式就是排序但是如果数据量非常大排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决基本思路如下1用数据集合中前K个元素来建堆前k个最大的元素则建小堆前k个最小的元素则建大堆2用剩余的N-K个元素依次与堆顶元素来比较不满足则替换堆顶元素将剩余N-K个元素依次与堆顶元素比完之后堆中剩余的K个元素就是所求的前K个最小或者最大的元素void CreateNDate() { // 造数据 int n 100000; srand(time(0)); const char* file data.txt; FILE* fin fopen(file, w); if (fin NULL) { perror(fopen error); return; } for (int i 0; i n; i) { int x (rand()i) % 1000000; fprintf(fin, %d\n, x); } fclose(fin); } void topk() { printf(请输⼊k); int k 0; scanf(%d, k); const char* file data.txt; FILE* fout fopen(file, r); if (fout NULL) { perror(fopen error); return; } int val 0; int* minheap (int*)malloc(sizeof(int) * k); if (minheap NULL) { perror(malloc error); return; } for (int i 0; i k; i) { fscanf(fout, %d, minheap[i]); } // 建k个数据的⼩堆 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); }时间复杂度O(n) k (n−k)log2k4. 实现链式结构二叉树用链表来表示一棵⼆叉树即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩⼦和右孩⼦所在的链结点的存储地址 其结构如下typedef int BTDataType; // ⼆叉链 typedef struct BinaryTreeNode { struct BinTreeNode* left; // 指向当前结点左孩⼦ struct BinTreeNode* 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; }回顾二叉树的概念二叉树分为空树和非空二叉树非空二叉树由根结点、根结点的左子树、根结点的右子树组成的根结点的左子树和右子树分别又是由子树结点、子树结点的左子树、子树结点的右子树组成的因此二叉树定义是递归式的,后序链式二叉树的操作中基本都是按照该概念实现的。4.1 前中后序遍历二叉树的操作离不开树的遍历我们先来看看二叉树的遍历有哪些方式4.1.1 遍历规则按照规则⼆叉树的遍历有前序/中序/后序的递归结构遍历1前序遍历(Preorder Traversal 亦称先序遍历)访问根结点的操作发生在遍历其左右子树之前访问顺序为根结点、左子树、右子树2中序遍历(Inorder Traversal)访问根结点的操作发生在遍历其左右子树之中间访问顺序为左子树、根结点、右子树3后序遍历(Postorder Traversal)访问根结点的操作发生在遍历其左右子树之后访问顺序为左子树、右子树、根结点4.1.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; } InOrder(root-left); InOrder(root-right); printf(%d , root-val); }图解遍历以前序遍历为例函数递归栈帧图前序遍历结果1 2 3 4 5 6中序遍历结果3 2 1 5 4 6后序遍历结果3 1 5 6 4 14.2 结点个数以及高度等// ⼆叉树结点个数 int BinaryTreeSize(BTNode* root); // ⼆叉树叶⼦结点个数 int BinaryTreeLeafSize(BTNode* root); // ⼆叉树第k层结点个数 int BinaryTreeLevelKSize(BTNode* root, int k); //⼆叉树的深度/⾼度 int BinaryTreeDepth(BTNode* root); // ⼆叉树查找值为x的结点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x); // ⼆叉树销毁 void BinaryTreeDestory(BTNode** root);4.3 层序遍历除了先序遍历、中序遍历、后序遍历外还可以对⼆叉树进行序遍历。设二叉树的根结点所在层数为1层序遍历就是从所在二叉树的根结点出发首先访问第⼀层的树根结点然后从左到右访问第2层上的结点接着是第三层的结点以此类推自上而下自左至右逐层访问树的结点的过程就是层序遍历实现层序遍历需要额外借助数据结构队列// 层序遍历 void LevelOrder(BTNode* root) { Queue q; QueueInit(q); QueuePush(q, root); while (!QueueEmpty(q)) { BTNode* top QueueFront(q); printf(%c , top-data); QueuePop(q); if (top-_left) { QueuePush(q, top-_left); } if (top-_right) { QueuePush(q, top-_right); } } QueueDesTroy(q); }4.4 判断是否为完全二叉树// 判断⼆叉树是否是完全⼆叉树 bool BinaryTreeComplete(BTNode* root) { Queue q; QueueInit(q); QueuePush(q, root); while (!QueueEmpty(q)) { BTNode* top QueueFront(q); QueuePop(q); if (top NULL) { break; } QueuePush(q, top-_left); QueuePush(q, top-_right); } while (!QueueEmpty(q)) { BTNode* top QueueFront(q); QueuePop(q); if (top ! NULL) { QueueDesTroy(q); return false; } } QueueDesTroy(q); return true; }5. 二叉树算法题5.1 单值二叉树https://leetcode.cn/problems/univalued-binary-tree/description/5.2 相同的树https://leetcode.cn/problems/same-tree/description/基于上⼀道OJ题拓展学习对称二叉树https://leetcode.cn/problems/symmetric-tree/description/5.3 另一棵树的子树https://leetcode.cn/problems/subtree-of-another-tree/description/5.4 二叉树遍历前序遍历https://leetcode.cn/problems/binary-tree-preorder-traversal/description/课下完成剩下的遍历⽅式中序遍历https://leetcode.cn/problems/binary-tree-inorder-traversal/description/后序遍历https://leetcode.cn/problems/binary-tree-postorder-traversal/description/5.5 二叉树的构建及遍历https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef6. 二叉树选择题二叉树性质1对任何⼀棵二叉树, 如果度为 0 其叶结点个数为n0 , 度为 2 的分⽀结点个数为n2 ,则有n0 n2 1证明上述性质假设一个二叉树有 a 个度为2的节点 b 个度为1的节点 c 个叶节点则这个二叉树的边数是2ab另一方面由于共有 abc 个节点所以边数等于 abc-1结合上面两个公式2ab abc-1 即 a c-1根据二叉树的性质完成以下选择题1. 某⼆叉树共有 399 个结点其中有 199 个度为 2 的结点则该⼆叉树中的叶⼦结点数为 A 不存在这样的⼆叉树 B 200 C 198 D 199 2.在具有 2n 个结点的完全⼆叉树中叶⼦结点个数为 A n B n1 C n-1 D n/2 3.⼀棵完全⼆叉树的结点数位为531个那么这棵树的⾼度为 A 11 B 10 C 8 D 12 4.⼀个具有767个结点的完全⼆叉树其叶⼦结点个数为 A 383 B 384 C 385 D 386 答案 1.B 2.A 3.B 4.B链式二叉树遍历选择题1.某完全⼆叉树按层次输出同⼀层从左到右的序列为 ABCDEFGH 。该完全⼆叉树的前序序列为 A ABDHECFG B ABCDEFGH C HDBEAFCG D HDEBFGCA 2.⼆叉树的先序遍历和中序遍历如下先序遍历EFHIGJK;中序遍历HFIEJKG.则⼆叉树根结点为 A E B F C G D H 3.设⼀课⼆叉树的中序遍历序列badce后序遍历序列bdeca则⼆叉树前序遍历序列为____。 A adbce B decab C debac D abcde 4.某⼆叉树的后序遍历序列与中序遍历序列相同均为 ABCDEF 则按层次输出同⼀层从左到右 的序列为 A FEDCBA B CBAFED C DEFCBA D ABCDEF 1.A 2.A 3.D 4.A