数据结构精讲树 → 二叉树 → 堆 从入门到实战文章目录数据结构精讲树 → 二叉树 → 堆 从入门到实战一、树一切树形结构的基础1.1 树的概念与结构1.2 树的常用术语1.3 孩子兄弟表示法C 语言完整实现二、二叉树最常用的树形结构2.1 二叉树基本概念2.2 两种特殊二叉树2.3 二叉树重要性质2.4 二叉树存储结构1顺序存储数组2链式存储二叉链2.5 二叉树遍历递归版完整代码三、堆完全二叉树的经典应用3.1 堆的核心概念3.2 堆结构定义3.3 向上调整插入用3.4 向下调整删除/建堆用3.5 堆插入、删除完整代码3.6 堆的两大应用一、树一切树形结构的基础1.1 树的概念与结构树是由n(n≥0)个有限节点组成的非线性层次结构形态像一棵根朝上、叶朝下的倒挂树。核心规则有且仅有一个根节点无双亲。其余节点分为互不相交的子树子树也是树。N 个节点 ⇔ N-1 条边。除根外每个节点仅有一个父节点。1.2 树的常用术语节点的度孩子个数树的度所有节点度的最大值叶子节点度为 0 的节点兄弟节点同一个父节点的节点高度/深度节点最大层次数森林多棵互不相交的树的集合1.3 孩子兄弟表示法C 语言完整实现// 孩子兄弟表示法通用树结构structTreeNode{intdata;// 数据域structTreeNode*firstChild;// 指向第一个孩子structTreeNode*nextBrother;// 指向右兄弟};✅ 作用可将任意树转为二叉树存储是树与二叉树的桥梁。二、二叉树最常用的树形结构2.1 二叉树基本概念二叉树是每个节点最多有两个子树的有序树左子树、右子树严格区分不能颠倒。特点节点度 ≤ 2是有序树递归定义根 左子树 右子树2.2 两种特殊二叉树满二叉树每一层节点数都达到最大值。节点总数2ʰ - 1h 为高度完全二叉树除最后一层外其他层满节点最后一层节点靠左连续排列。✅ 满二叉树是特殊的完全二叉树。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 堆的核心概念大根堆父节点 ≥ 孩子节点堆顶最大小根堆父节点 ≤ 孩子节点堆顶最小下标公式双亲(i - 1) / 2左孩子2 * i 1右孩子2 * i 23.2 堆结构定义typedefintHPDataType;typedefstructHeap{HPDataType*a;intsize;// 当前元素个数intcapacity;// 容量}HP;3.3 向上调整插入用// 向上调整大堆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.4 向下调整删除/建堆用// 向下调整大堆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.5 堆插入、删除完整代码// 堆插入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.6 堆的两大应用堆排序升序 → 建大堆降序 → 建小堆时间复杂度O(n log n)TOP-K 问题求前 K 大 → 建小堆求前 K 小 → 建大堆海量数据最优解法时间复杂度O(n log k)