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

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

本文适合：数据结构入门、考研复习、秋招笔试面试、期末速成。全文理论+代码+OJ题+选择题一站式整理，可直接保存背诵。

前言

树形结构是非线性数据结构的核心，从基础树到二叉树，再到堆、堆排序、TOP-K问题，层层递进、环环相扣。本文把课堂上的重点全部整理成博客版，学完即可应对绝大多数考试与面试。

一、树：所有树形结构的基础

1.1 树的概念与结构

树是由n(n≥0)个有限结点组成的层次关系集合，像一棵根朝上、叶朝下的倒挂树。

核心规则

• 有且仅有一个根结点，没有前驱结点。
• 除根外，其余结点分成M(M>0)个互不相交的子树。
• 树是递归定义的。
• N 个结点 ⇔ N-1 条边。
• 除根外，每个结点有且仅有一个父结点。

1.2 树的常用术语

• 父/双亲结点：有子结点的结点
• 子/孩子结点：子树的根结点
• 结点的度：孩子个数
• 树的度：所有结点度的最大值
• 叶子结点：度为 0 的结点
• 分支结点：度不为 0 的结点
• 兄弟结点：同一个父结点的结点
• 层次：根为第 1 层
• 高度/深度：最大层次数
• 森林：m(m>0) 棵互不相交的树的集合

1.3 孩子兄弟表示法（最常用）

可以把普通树转为二叉树存储。

// 孩子兄弟表示法structTreeNode{intdata;// 数据域structTreeNode*firstChild;// 第一个孩子structTreeNode*nextBrother;// 下一个兄弟};

二、二叉树：最核心、最高频

2.1 二叉树基本概念

• 每个结点最多 2 个子树
• 左、右子树严格有序，不能颠倒
• 递归定义：根 + 左子树 + 右子树

2.2 两种特殊二叉树

1. 满二叉树
   每一层结点数都达到最大值。
   结点总数：2ʰ - 1

2. 完全二叉树
   除最后一层外都满；最后一层靠左连续。
   ✅ 满二叉树是特殊的完全二叉树。

2.3 二叉树重要性质

1. 第 i 层最多：2ⁱ⁻¹个结点
2. 高度 h 最多：2ʰ - 1个结点
3. n₀ = n₂ + 1（叶子数 = 度2结点数 + 1）
4. 完全二叉树高度：h = ⌊log₂n⌋ + 1

2.4 二叉树存储结构

（1）顺序存储

用数组，适合完全二叉树，常用于堆。

（2）链式存储（二叉链）

typedefintBTDataType;typedefstructBinaryTreeNode{BTDataType data;structBinaryTreeNode*left;structBinaryTreeNode*right;}BTNode;

2.5 二叉树遍历（递归版）

// 前序：根 → 左 → 右voidPreOrder(BTNode*root){if(root==NULL){printf("N ");return;}printf("%d ",root->data);PreOrder(root->left);PreOrder(root->right);}// 中序：左 → 根 → 右voidInOrder(BTNode*root){if(root==NULL){printf("N ");return;}InOrder(root->left);printf("%d ",root->data);InOrder(root->right);}// 后序：左 → 右 → 根voidPostOrder(BTNode*root){if(root==NULL){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 + 2

3.3 堆结构定义

typedefintHPDataType;typedefstructHeap{HPDataType*a;intsize;intcapacity;}HP;

3.4 向上调整（插入用）

voidAdjustUp(HPDataType*a,intchild){intparent=(child-1)/2;while(child>0){if(a[child]>a[parent]){HPDataType tmp=a[child];a[child]=a[parent];a[parent]=tmp;child=parent;parent=(child-1)/2;}else{break;}}}

3.5 向下调整（删除/建堆用）

voidAdjustDown(HPDataType*a,intn,intparent){intchild=parent*2+1;while(child<n){if(child+1<n&&a[child+1]>a[child]){child++;}if(a[child]>a[parent]){HPDataType tmp=a[child];a[child]=a[parent];a[parent]=tmp;parent=child;child=parent*2+1;}else{break;}}}

3.6 堆插入、删除

// 插入voidHPPush(HP*php,HPDataType x){assert(php);if(php->size==php->capacity){intnewCapacity=php->capacity==0?4:php->capacity*2;HPDataType*tmp=(HPDataType*)realloc(php->a,newCapacity*sizeof(HPDataType));if(tmp==NULL){perror("realloc fail");return;}php->a=tmp;php->capacity=newCapacity;}php->a[php->size++]=x;AdjustUp(php->a,php->size-1);}// 删除堆顶voidHPPop(HP*php){assert(php);assert(php->size>0);HPDataType tmp=php->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;i>=0;--i){AdjustDown(a,n,i);}intend=n-1;while(end>0){Swap(&a[0],&a[end]);AdjustDown(a,end,0);--end;}}

（2）TOP-K 问题

求海量数据前 K 大/小。

• 前 K 大 → 建小堆
• 前 K 小 → 建大堆
• 时间复杂度：O(n log k)

四、链式二叉树进阶：高频操作

4.1 创建二叉树

BTNode*BuyBTNode(BTDataType val){BTNode*newnode=(BTNode*)malloc(sizeof(BTNode));newnode->data=val;newnode->left=NULL;newnode->right=NULL;returnnewnode;}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;returnn1;}

4.2 层序遍历（队列实现）

// 队列实现（略）voidLevelOrder(BTNode*root){if(!root)return;Queue q;QueueInit(&q);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 常用统计函数（面试高频）

// 总结点个数intBinaryTreeSize(BTNode*root){returnroot==NULL?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(k>=1);if(!root)return0;if(k==1)return1;returnBinaryTreeLevelKSize(root->left,k-1)+BinaryTreeLevelKSize(root->right,k-1);}// 树高度intBinaryTreeDepth(BTNode*root){if(!root)return0;intleft=BinaryTreeDepth(root->left);intright=BinaryTreeDepth(root->right);returnleft>right?left+1:right+1;}// 查找值xBTNode*BinaryTreeFind(BTNode*root,BTDataType x){if(!root)returnNULL;if(root->data==x)returnroot;BTNode*left=BinaryTreeFind(root->left,x);if(left)returnleft;returnBinaryTreeFind(root->right,x);}// 销毁树voidBinaryTreeDestroy(BTNode**root){if(!*root)return;BinaryTreeDestroy(&(*root)->left);BinaryTreeDestroy(&(*root)->right);free(*root);*root=NULL;}

4.4 判断完全二叉树

intBinaryTreeComplete(BTNode*root){if(!root)return1;Queue q;QueueInit(&q);QueuePush(&q,root);while(!QueueEmpty(&q)){BTNode*front=QueueFront(&q);QueuePop(&q);if(!front)break;QueuePush(&q,front->left);QueuePush(&q,front->right);}while(!QueueEmpty(&q)){BTNode*front=QueueFront(&q);QueuePop(&q);if(front){QueueDestroy(&q);return0;}}QueueDestroy(&q);return1;}