什么是树在正式学习二叉树之前我们先来认识一下更一般的概念——树Tree。树的定义树是一种非线性的数据结构它由nn ≥ 0个节点和连接节点之间的**边Edge**组成并且满足以下两个条件有且仅有一个根节点Root它是整棵树的起点没有父节点除根节点外其余每个节点有且仅有一个父节点且可以通过唯一的路径从根节点到达当 n 0 时称为空树。树的基本术语节点Node树中的基本单元存储数据边Edge连接父节点与子节点的线段表示节点间的隶属关系根节点Root整棵树的顶端节点没有父节点叶子节点Leaf没有子节点的节点也叫终端节点父节点Parent某个节点的直接上级节点子节点Child某个节点的直接下级节点兄弟节点Sibling拥有同一个父节点的节点祖先节点Ancestor从根节点到某节点路径上的所有节点后代节点Descendant某节点子树中的所有节点深度Depth从根节点到该节点的路径长度根节点深度为 0 或 1视定义而定高度Height从该节点到最远叶子节点的路径长度度Degree一个节点拥有的子节点个数层Level根节点在第 1 层其子节点在第 2 层依此类推树的性质节点数 边数 1树中 n 个节点恰好有 n-1 条边或者说成节点数所有节点的度之和1m叉树中第 i 层上最多有 mi-1个节点i1m叉树指每个节点最多有m个孩子极端场景下⾼度为h的m叉树叶⼦结点都在第h层每个分⽀结点均有m个孩⼦每层都是满的假设层数是i则每层结点数为 mi−1 第1⾄h层的结点数是⼀个以m为公⽐的等⽐数列。3.高度为h的m叉树最多有mh-1 / m-1个节点3.连通且无环任意两个节点之间有且仅有一条路径树中不存在回路5.有向性边具有方向性从父节点指向子节点6.层次性树天然具有层级结构适合表达具有从属关系的数据树的分类根据节点的子节点数量树可以分为二叉树Binary Tree每个节点最多有两个子节点是最常用的一种树多叉树Multi-way Tree每个节点可以有多个子节点如 B 树、Trie 树等下面这张图展示了一棵典型的树结构A ← 根节点第 1 层 / | \ B C D ← 第 2 层 / \ | E F G ← 第 3 层叶子节点E、F、G在这棵树中A 是根节点B、C、D 是 A 的子节点互为兄弟节点E、F 是 B 的子节点G 是 D 的子节点E、F、G 都是叶子节点。再举一个例子理解了树的基本概念之后我们再来看它的特例——二叉树就会轻松很多。1. 什么是二叉树二叉树Binary Tree是计算机科学中最基础、最重要的数据结构之一。它是一种树形结构其中每个节点最多有两个子节点也可以称为子树通常称为左子节点和右子节点。1.1 基本定义以下部分节点Node树中的基本单元包含数据和指向子节点的指针根节点Root树的顶端节点没有父节点叶子节点Leaf没有子节点的节点深度Depth从根节点到该节点的路径长度高度Height从该节点到最远叶子节点的路径长度补充节点间关系的描述了解就行关系示例考虑以下二叉树A / \ B C / \ \ D E FA是B和C的父节点B和C是A的子节点B和C是兄弟节点A是D、E、F的祖先节点D、E、F是A的后代节点B是D和E的父节点D和E是兄弟节点以B为根的子树包含B、D、E三个节点上述概念不用刻意去背平常知道是什么就可以2. 二叉树的基本性质2.1 结构特性每个节点最多有两个子节点子树有左右之分顺序不能颠倒第 i 层最多有 2(i-1)个节点深度为 k 的二叉树最多有 2k- 1 个节点对于任意一个二叉树如果度为2的节点数为n2度为0的节点数为n0则n0 n2 1可以自己画个二叉树现推规律也可以用前面的性质推导度为1则叫n1节点数m n1 2*n2 1度之和1n0 n1 n2化简就能得到具有n个节点的完全二叉树的高度为[log 2 n]1[ ]为向下取整可以由2h-1 n 2h两边同时取对数得到补充二叉树具有递归性质任何一个二叉树都可以分成左子树与右子树与根非空的子树亦可以分为左子树右子树与根…2.2 特殊类型满二叉树Full Binary Tree每个节点都有 0 或 2 个子节点套用等比数列前n项和公式可以得出高度为h的满二叉树总结点为2h-1个完全二叉树Complete Binary Tree除最后一层外其他层都是满的且最后一层节点尽量靠左完全⼆叉树的叶⼦⼀定只出现在最后两层且度为1的结点最多有1个剩下的结点都是度为0和度为2。完美二叉树Perfect Binary Tree所有叶子节点都在同一层且每个非叶子节点都有两个子节点3. 二叉树的存储方式3.1 链式存储最常用的存储方式每个节点包含数据域左子节点指针右子节点指针有些情况下需要记录父节点的地址比如红黑树typedefstructTreeNode{intval;// 节点值structTreeNode*left;// 左子节点structTreeNode*right;// 右子节点}TreeNode;3.2 顺序存储数组对于完全二叉树可以使用数组存储根节点存储在索引 1 的位置节点 i 的左子节点在 2*i节点 i 的右子节点在 2*i 1节点 i 的父节点在 i//2如图补充顺序存储里节点权不是靠存地址连起来的而是靠下标之间的数学关系连起来的。使用完全二叉树可以避免空间浪费并且因为完全二叉树有个完美性质按层从上到下、从左到右编上号这个编号本身就隐含了父子关系数组的下标从0开始如果想美观可以舍弃一个空间如果不舍弃公式是左孩子2i 1右孩子2i 2父节点(i - 1) / 2从0开始是比较常用的可以记住公式也可以画个简单的二叉树推到一下4.堆堆Heap是一种特殊的完全二叉树常用于实现优先队列Priority Queue。它满足以下两个条件结构性质堆是一棵完全二叉树即除最后一层外其他层都是满的且最后一层节点尽量靠左。堆序性质根据父节点与子节点的大小关系堆分为两种大根堆Max Heap父节点值 ≥ 子节点值堆顶是最大值小根堆Min Heap父节点值 ≤ 子节点值堆顶是最小值对兄弟节点之间的大小没有要求由于堆是完全二叉树通常使用数组进行存储下标关系与 3.2 节一致这里采用从 1 开始的下标便于理解节点 i 的左子节点在2*i节点 i 的右子节点在2*i 1节点 i 的父节点在i//24.1 堆的存储结构用数组存储堆时数组下标从 1 开始heap[0]可以存放堆的大小或闲置不用。例如下面这个大根堆90 / \ 80 70 / \ / \ 60 50 40 30对应的数组为[_, 90, 80, 70, 60, 50, 40, 30]_表示下标 0 闲置。4.2 堆的插入操作上浮 sift up插入操作的基本思路将新元素添加到数组末尾即完全二叉树的最后一个位置。从该位置开始上浮sift up不断与父节点比较若违反堆序性质大根堆中新元素大于父节点则交换直到满足堆序或到达根节点。时间复杂度为O(log n)。补充相比于冒泡的O(n2)堆排序的效率很高这也是堆排序出现的原因之一上浮所需要的最坏情况就是进行该二叉树高度次数的比较由上面的知识2.1.6可得到时间复杂度// 大根堆的插入voidheap_insert(intheap[],int*size,intval){inti(*size);// 新元素放在末尾heap[i]val;// 上浮与父节点比较并交换while(i1heap[i]heap[i/2]){inttmpheap[i];heap[i]heap[i/2];heap[i/2]tmp;ii/2;}}4.3 堆的删除操作下沉 sift down堆的删除通常指删除堆顶元素大根堆的最大值或小根堆的最小值。基本思路用数组最后一个元素覆盖堆顶元素并将堆的大小减 1。从堆顶开始下沉sift down不断与较大的子节点大根堆比较若违反堆序性质则交换直到满足堆序或到达叶子节点。时间复杂度为O(log n)。// 大根堆的删除删除堆顶voidheap_delete(intheap[],int*size){if(*size0){return;}heap[1]heap[*size];// 用最后一个元素覆盖堆顶(*size)--;inti1;// 下沉与较大的子节点比较并交换while(2*i*size){intchild2*i;// 左子节点// 若右子节点存在且更大则选择右子节点if(child1*sizeheap[child1]heap[child]){child;}if(heap[i]heap[child]){break;// 已满足堆序停止}inttmpheap[i];heap[i]heap[child];heap[child]tmp;ichild;}}4.4 堆的建堆操作给定一个无序数组可以通过自底向上的下沉在O(n)时间内将其调整为堆// 对下标 i 执行下沉操作voidsift_down(intheap[],intn,inti){while(2*in){intchild2*i;if(child1nheap[child1]heap[child]){child;}if(heap[i]heap[child]){break;}inttmpheap[i];heap[i]heap[child];heap[child]tmp;ichild;}}// 建堆从最后一个非叶子节点开始自底向上下沉voidbuild_heap(intheap[],intn){for(intin/2;i1;i--){sift_down(heap,n,i);}}4.5 堆的完整示例下面是一个完整的大根堆示例包含插入、删除和建堆操作#includestdio.h#defineMAX_SIZE100intheap[MAX_SIZE];intsize0;// 插入voidinsert(intval){intisize;heap[i]val;while(i1heap[i]heap[i/2]){inttmpheap[i];heap[i]heap[i/2];heap[i/2]tmp;ii/2;}}// 删除堆顶voiddelete_top(){if(size0){return;}heap[1]heap[size--];inti1;while(2*isize){intchild2*i;if(child1sizeheap[child1]heap[child]){child;}if(heap[i]heap[child]){break;}inttmpheap[i];heap[i]heap[child];heap[child]tmp;ichild;}}// 打印堆voidprint_heap(){for(inti1;isize;i){printf(%d ,heap[i]);}printf(\n);}intmain(){// 依次插入元素insert(50);insert(30);insert(70);insert(20);insert(60);insert(90);printf(插入后的堆);print_heap();// 输出90 60 70 20 30 50// 删除堆顶delete_top();printf(删除堆顶后的堆);print_heap();// 输出70 60 50 20 30return0;}4.6 堆的应用优先队列堆是实现优先队列最常用的数据结构插入和删除堆顶均为 O(log n)。堆排序Heap Sort利用堆的性质反复取出堆顶元素即可完成排序时间复杂度为 O(n log n)。Top K 问题在海量数据中求最大/最小的 K 个元素用大小为 K 的堆即可高效解决。Dijkstra 算法求单源最短路径时用小根堆优化取最小距离节点的过程。4. 二叉树的遍历方式遍历是二叉树操作的基础主要有四种方式4.1 前序遍历Pre-order访问顺序根 → 左 → 右voidpreorder(TreeNode*root){if(rootNULL){return;}printf(%d ,root-val);// 访问根节点preorder(root-left);// 遍历左子树preorder(root-right);// 遍历右子树}4.2 中序遍历In-order访问顺序左 → 根 → 右voidinorder(TreeNode*root){if(rootNULL){return;}inorder(root-left);// 遍历左子树printf(%d ,root-val);// 访问根节点inorder(root-right);// 遍历右子树}4.3 后序遍历Post-order访问顺序左 → 右 → 根voidpostorder(TreeNode*root){if(rootNULL){return;}postorder(root-left);// 遍历左子树postorder(root-right);// 遍历右子树printf(%d ,root-val);// 访问根节点}4.4 层序遍历Level-order按层次从上到下、从左到右访问#includestdio.h#includestdlib.hvoidlevelorder(TreeNode*root){if(rootNULL){return;}// 用数组模拟队列TreeNode*queue[1000];intfront0,rear0;queue[rear]root;while(frontrear){TreeNode*nodequeue[front];printf(%d ,node-val);if(node-left){queue[rear]node-left;}if(node-right){queue[rear]node-right;}}}5. 二叉树的应用场景5.1 搜索结构二叉搜索树BST左子树所有节点值 根节点值 右子树所有节点值平衡二叉树AVL树保持左右子树高度差不超过 1红黑树自平衡二叉搜索树广泛应用于各种库中5.2 表达式树用于表示算术表达式叶子节点操作数内部节点运算符5.3 哈夫曼树用于数据压缩频率高的字符使用短编码6. 二叉树的常见操作6.1 查找节点deffind_node(root,target):ifnotroot:returnNoneifroot.valtarget:returnroot left_resultfind_node(root.left,target)ifleft_result:returnleft_resultreturnfind_node(root.right,target)6.2 计算节点数defcount_nodes(root):ifnotroot:return0return1count_nodes(root.left)count_nodes(root.right)6.3 计算树的高度deftree_height(root):ifnotroot:return0return1max(tree_height(root.left),tree_height(root.right))6.4 判断是否平衡defis_balanced(root):defcheck(node):ifnotnode:return0,Trueleft_height,left_balancedcheck(node.left)right_height,right_balancedcheck(node.right)balanced(left_balancedandright_balancedandabs(left_height-right_height)1)returnmax(left_height,right_height)1,balancedreturncheck(root)[1]7. 学习建议与进阶方向7.1 学习路线建议掌握基础概念理解节点、边、深度、高度等术语熟练四种遍历能够手写递归和非递归实现理解特殊二叉树BST、AVL、堆等变体的特性解决经典问题如求深度、判断对称、最近公共祖先等7.2 经典练习题二叉树的最大深度对称二叉树的判断二叉树的最近公共祖先二叉树的直径路径总和问题7.3 进阶学习多叉树每个节点可以有多个子节点B树/B树用于数据库索引Trie树用于字符串检索线段树用于区间查询8. 总结二叉树作为数据结构的基础具有以下特点结构简单每个节点最多两个子节点易于理解和实现操作高效大多数操作的时间复杂度为 O(log n)应用广泛从基础算法到系统设计都有重要应用扩展性强衍生出多种变体满足不同需求掌握二叉树不仅有助于理解更复杂的数据结构也是算法面试中的必备技能。建议通过实际编码练习加深对二叉树各种操作的理解。学习二叉树最好的方式就是动手实现。从简单的节点类开始逐步实现遍历、查找、插入等操作再尝试解决一些经典算法问题。