数据结构学习记录：树 + 二叉树 + 堆 从原理到手撕代码

数据结构学习记录树 二叉树 堆 从原理到手撕代码本文适合数据结构入门、考研复习、秋招笔试面试、期末速成。全文理论代码OJ题选择题一站式整理可直接保存背诵。文章目录数据结构学习记录树 二叉树 堆 从原理到手撕代码前言一、树所有树形结构的基础1.1 树的概念与结构核心规则1.2 树的常用术语1.3 孩子兄弟表示法最常用二、二叉树最核心、最高频2.1 二叉树基本概念2.2 两种特殊二叉树2.3 二叉树重要性质2.4 二叉树存储结构1顺序存储2链式存储二叉链2.5 二叉树遍历递归版三、堆完全二叉树的经典应用3.1 堆的分类3.2 下标公式3.3 堆结构定义3.4 向上调整插入用3.5 向下调整删除/建堆用3.6 堆插入、删除3.7 堆的两大应用1堆排序2TOP-K 问题四、链式二叉树进阶高频操作4.1 创建二叉树4.2 层序遍历队列实现4.3 常用统计函数面试高频4.4 判断完全二叉树前言树形结构是非线性数据结构的核心从基础树到二叉树再到堆、堆排序、TOP-K问题层层递进、环环相扣。本文把课堂上的重点全部整理成博客版学完即可应对绝大多数考试与面试。一、树所有树形结构的基础1.1 树的概念与结构树是由n(n≥0)个有限结点组成的层次关系集合像一棵根朝上、叶朝下的倒挂树。核心规则有且仅有一个根结点没有前驱结点。除根外其余结点分成M(M0)个互不相交的子树。树是递归定义的。N 个结点 ⇔ N-1 条边。除根外每个结点有且仅有一个父结点。1.2 树的常用术语父/双亲结点有子结点的结点子/孩子结点子树的根结点结点的度孩子个数树的度所有结点度的最大值叶子结点度为 0 的结点分支结点度不为 0 的结点兄弟结点同一个父结点的结点层次根为第 1 层高度/深度最大层次数森林m(m0) 棵互不相交的树的集合1.3 孩子兄弟表示法最常用可以把普通树转为二叉树存储。// 孩子兄弟表示法structTreeNode{intdata;// 数据域structTreeNode*firstChild;// 第一个孩子structTreeNode*nextBrother;// 下一个兄弟};二、二叉树最核心、最高频2.1 二叉树基本概念每个结点最多 2 个子树左、右子树严格有序不能颠倒递归定义根 左子树 右子树2.2 两种特殊二叉树满二叉树每一层结点数都达到最大值。结点总数2ʰ - 1完全二叉树除最后一层外都满最后一层靠左连续。✅ 满二叉树是特殊的完全二叉树。2.3 二叉树重要性质第 i 层最多2ⁱ⁻¹个结点高度 h 最多2ʰ - 1个结点n₀ n₂ 1叶子数 度2结点数 1完全二叉树高度h ⌊log₂n⌋ 12.4 二叉树存储结构1顺序存储用数组适合完全二叉树常用于堆。2链式存储二叉链typedefintBTDataType;typedefstructBinaryTreeNode{BTDataType data;structBinaryTreeNode*left;structBinaryTreeNode*right;}BTNode;2.5 二叉树遍历递归版// 前序根 → 左 → 右voidPreOrder(BTNode*root){if(rootNULL){printf(N );return;}printf(%d ,root-data);PreOrder(root-left);PreOrder(root-right);}// 中序左 → 根 → 右voidInOrder(BTNode*root){if(rootNULL){printf(N );return;}InOrder(root-left);printf(%d ,root-data);InOrder(root-right);}// 后序左 → 右 → 根voidPostOrder(BTNode*root){if(rootNULL){printf(N );return;}PostOrder(root-left);PostOrder(root-right);printf(%d ,root-data);}三、堆完全二叉树的经典应用堆是数组实现的完全二叉树满足堆序性质。3.1 堆的分类大根堆父 ≥ 孩子堆顶最大小根堆父 ≤ 孩子堆顶最小3.2 下标公式双亲(i - 1) / 2左孩子2 * i 1右孩子2 * i 23.3 堆结构定义typedefintHPDataType;typedefstructHeap{HPDataType*a;intsize;intcapacity;}HP;3.4 向上调整插入用voidAdjustUp(HPDataType*a,intchild){intparent(child-1)/2;while(child0){if(a[child]a[parent]){HPDataType tmpa[child];a[child]a[parent];a[parent]tmp;childparent;parent(child-1)/2;}else{break;}}}3.5 向下调整删除/建堆用voidAdjustDown(HPDataType*a,intn,intparent){intchildparent*21;while(childn){if(child1na[child1]a[child]){child;}if(a[child]a[parent]){HPDataType tmpa[child];a[child]a[parent];a[parent]tmp;parentchild;childparent*21;}else{break;}}}3.6 堆插入、删除// 插入voidHPPush(HP*php,HPDataType x){assert(php);if(php-sizephp-capacity){intnewCapacityphp-capacity0?4:php-capacity*2;HPDataType*tmp(HPDataType*)realloc(php-a,newCapacity*sizeof(HPDataType));if(tmpNULL){perror(realloc fail);return;}php-atmp;php-capacitynewCapacity;}php-a[php-size]x;AdjustUp(php-a,php-size-1);}// 删除堆顶voidHPPop(HP*php){assert(php);assert(php-size0);HPDataType tmpphp-a[0];php-a[0]php-a[php-size-1];php-a[php-size-1]tmp;php-size--;AdjustDown(php-a,php-size,0);}3.7 堆的两大应用1堆排序升序 → 建大堆降序 → 建小堆时间复杂度O(n log n)voidHeapSort(int*a,intn){// 建堆 O(n)for(inti(n-1-1)/2;i0;--i){AdjustDown(a,n,i);}intendn-1;while(end0){Swap(a[0],a[end]);AdjustDown(a,end,0);--end;}}2TOP-K 问题求海量数据前 K 大/小。前 K 大 → 建小堆前 K 小 → 建大堆时间复杂度O(n log k)四、链式二叉树进阶高频操作4.1 创建二叉树BTNode*BuyBTNode(BTDataType val){BTNode*newnode(BTNode*)malloc(sizeof(BTNode));newnode-dataval;newnode-leftNULL;newnode-rightNULL;returnnewnode;}BTNode*CreateTree(){BTNode*n1BuyBTNode(1);BTNode*n2BuyBTNode(2);BTNode*n3BuyBTNode(3);BTNode*n4BuyBTNode(4);BTNode*n5BuyBTNode(5);BTNode*n6BuyBTNode(6);BTNode*n7BuyBTNode(7);n1-leftn2;n1-rightn4;n2-leftn3;n4-leftn5;n4-rightn6;n5-leftn7;returnn1;}4.2 层序遍历队列实现// 队列实现略voidLevelOrder(BTNode*root){if(!root)return;Queue q;QueueInit(q);QueuePush(q,root);while(!QueueEmpty(q)){BTNode*frontQueueFront(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 常用统计函数面试高频// 总结点个数intBinaryTreeSize(BTNode*root){returnrootNULL?0:BinaryTreeSize(root-left)BinaryTreeSize(root-right)1;}// 叶子结点数intBinaryTreeLeafSize(BTNode*root){if(!root)return0;if(!root-left!root-right)return1;returnBinaryTreeLeafSize(root-left)BinaryTreeLeafSize(root-right);}// 第k层结点数intBinaryTreeLevelKSize(BTNode*root,intk){assert(k1);if(!root)return0;if(k1)return1;returnBinaryTreeLevelKSize(root-left,k-1)BinaryTreeLevelKSize(root-right,k-1);}// 树高度intBinaryTreeDepth(BTNode*root){if(!root)return0;intleftBinaryTreeDepth(root-left);intrightBinaryTreeDepth(root-right);returnleftright?left1:right1;}// 查找值xBTNode*BinaryTreeFind(BTNode*root,BTDataType x){if(!root)returnNULL;if(root-datax)returnroot;BTNode*leftBinaryTreeFind(root-left,x);if(left)returnleft;returnBinaryTreeFind(root-right,x);}// 销毁树voidBinaryTreeDestroy(BTNode**root){if(!*root)return;BinaryTreeDestroy((*root)-left);BinaryTreeDestroy((*root)-right);free(*root);*rootNULL;}4.4 判断完全二叉树intBinaryTreeComplete(BTNode*root){if(!root)return1;Queue q;QueueInit(q);QueuePush(q,root);while(!QueueEmpty(q)){BTNode*frontQueueFront(q);QueuePop(q);if(!front)break;QueuePush(q,front-left);QueuePush(q,front-right);}while(!QueueEmpty(q)){BTNode*frontQueueFront(q);QueuePop(q);if(front){QueueDestroy(q);return0;}}QueueDestroy(q);return1;}