★ FEATURED ARTICLE 二叉树这东西说实话很多人一开始学的时候容易迷左子树右子树、前中后序遍历看着挺绕但等真上手写过几遍完整代码你会发现它其实是一个非常顺的逻辑结构。这篇笔记我打算从二叉树的基本概念出发重点讲透它的两种主流存储方式也就是顺序存储和链式存储每一种我都会给出完整的代码实现包括建树、遍历、求深度、统计节点这些常规操作。适合正在学数据结构的学生、准备面试刷题的人以及工作中需要手写树结构但好久没碰过的同学参考。1. 二叉树到底解决了什么问题1.1 先分清楚这些基本术语在写任何代码之前先得把二叉树里的几个词捋顺了。二叉树是每个节点最多有两个子节点的树结构这两个子节点一般叫作左孩子和右孩子左右是有顺序的互换一下就变成另一棵树了这一点和一般的树有明显区别。节点、根节点、叶子节点这些概念比较基础我重点说一下容易混淆的“深度”和“高度”。不同的教材定义不完全一样有的把根节点深度记为 0有的记为 1。我个人建议参考大部分考研教材和面试中的惯例深度就是从根节点到该节点经过的边的条数根节点深度为 0高度是从该节点到叶子节点的最长路径边的条数单个节点的树高度为 0。只要自己代码里口径统一写起来不会出问题但和别人沟通时最好先确认用的是哪种定义我踩过这个坑。还有两个术语必须分清“度”和“层”。度指一个节点拥有的子节点个数二叉树的节点度只能是 0、1、2层数一般从 1 开始根节点是第一层。搞清楚这些术语后边理解性质和推导公式会顺畅很多。1.2 三个必须记住的性质二叉树有几个性质考试和面试都喜欢考代码里也经常用到。第一个性质第 i 层最多有 2^(i-1) 个节点其中 i 从 1 开始。这个很好推导第一层最多 1 个第二层最多 2 个第三层最多 4 个每层翻倍所以是等比数列 2^(i-1)。第二个性质深度为 k 的二叉树最多有 2^k - 1 个节点。这就是把第一层到第 k 层的最大节点数加起来等比数列求和结果等于 2^k - 1。第三个性质对于任意非空二叉树叶子节点数 n0 和度为 2 的节点数 n2 满足 n0 n2 1。这个证明思路值得说一说。假设总节点数 n n0 n1 n2其中 n1 是度为 1 的节点数。再看边的数量除了根节点外每个节点都有一条边连着父节点所以总边数是 n - 1。从另一个角度看度为 1 的节点贡献 1 条出边度为 2 的节点贡献 2 条出边于是 n1 2*n2 n - 1。联立两个式子就能推出 n0 n2 1。这个性质在做选择题和算法题时非常有用比如给定完全二叉树的节点总数可以快速推出叶子节点的个数范围。1.3 满二叉树、完全二叉树、二叉排序树实际使用中最常遇到的几种二叉树形态得搞清楚。满二叉树是每一层节点都达到最大数量也就是深度为 k 时正好有 2^k - 1 个节点。这种树的形状非常整齐适合用数组来存。完全二叉树稍微宽松一点除了最后一层其他层都是满的并且最后一层的节点都连续地集中在左侧。这个“从左往右连续分布”是判断完全二叉树的核心标准。为什么要费劲定义这种形态因为它恰好适合顺序存储父节点和子节点的下标关系非常干净后面我写顺序存储代码就是基于这个特点。二叉排序树也叫二叉搜索树则是把数据的顺序关系利用起来左子树所有节点的值都小于根节点右子树所有节点的值都大于根节点。查找效率在平衡的情况下能达到 O(log n)这也是二叉树在工程里最广泛的应用场景之一。2. 存储方式不同存法背后的账本2.1 顺序存储数组的直白与空间陷阱顺序存储的思路很直接用一个一维数组来记录二叉树的所有节点然后通过下标关系找到某个节点的左孩子、右孩子和父节点。以下标从 1 开始为例某个节点在数组中的下标为 i那么它的左孩子下标是 2i右孩子下标是 2i 1父节点下标是 i/2 向下取整。如果用下标从 0 开始左孩子就是 2i 1右孩子是 2i 2父节点是 (i-1)/2。我习惯用从 1 开始的版本因为计算式更干净有时候题目也默认这套规则。这种存储方式的优点非常明显结构简单存完全二叉树时几乎没有空间浪费还能通过下标快速跳转到任意位置的父节点和子节点缓存命中率也高。但它也有一个很大的坑对于普通二叉树尤其是只有右子树不断延伸的退化树数组里会留下大量空闲位置因为你要为不存在的左子树保留空间。极端情况下一个深度为 k 的“斜树”用数组存储需要 2^k - 1 个位置却只放了 k 个节点空间浪费极其严重。提示所以顺序存储基本只用于完全二叉树或者节点数量不大、形态接近完全的二叉树。如果你的树是随意建的动不动就缺左孩子缺右孩子老老实实走链式存储。2.2 链式存储最主流的二叉链表链式存储把每个节点设计成一个小结构体里面保存数据外加两个指针分别指向左孩子和右孩子这种结构叫二叉链表。typedef struct BiTNode { char data; struct BiTNode *lchild; struct BiTNode *rchild; } BiTNode, *BiTree;这种存法摆脱了数组下标的限制任意形态的二叉树都能自然表示插入和删除节点只需要改几个指针非常灵活。它的缺点是每个节点要额外存两个指针内存开销比纯数组大而且查找父节点比较麻烦因为节点本身没有记录父节点是谁。链式存储还有一个有趣的数学结论n 个节点的二叉链表里总共有 2n 个指针域其中真正用来指向孩子的指针是 n-1 个因此空指针域有 n1 个。这些空指针后来被“线索二叉树”利用起来用来加速遍历这个我后边单独讲。2.3 进阶存储三叉链表与线索二叉树如果经常需要从某个节点回溯到它的父节点二叉链表就不够用了。三叉链表在节点里再加一个 parent 指针指向上级节点这样向上向下都能走代价是存储空间进一步增加。另一个进阶方案是线索二叉树它的核心思路是复用空指针域。叶子节点的左右指针本来都是空的我们可以把左空指针指向某种遍历序列中的“前驱节点”把右空指针指向“后继节点”。前序、中序、后序都可以做线索化但最常用的是中序线索化因为中序遍历的结果是有序的。做线索化时需要一个全局变量 pre 记录上一次访问的节点。如果当前节点左指针为空就把左指针指向 pre如果 pre 的右指针为空就把 pre 的右指针指向当前节点。为了避免指针方向混淆还需要加两个标志位来区分指针是指向孩子还是指向前驱/后继。typedef struct ThreadNode { char data; struct ThreadNode *lchild, *rchild; int ltag, rtag; // 0表示指向孩子1表示指向前驱/后继 } ThreadNode, *ThreadTree;线索化的好处是遍历时不需要递归也不需要显式栈只要沿着线索往后走就行时间复杂度和空间复杂度都很理想。代价是建树和维护线索的逻辑变复杂日常大多数场景用不到但面试中偶尔会考到原理。2.4 如何选一张表讲清不同存储方式没有绝对的好坏关键看场景。我整理了一张对照表方便你在写代码前快速决策。存储方式适用场景优点缺点顺序存储完全二叉树、堆、优先队列实现简单下标关系计算快非完全树空间浪费严重二叉链表绝大多数通用二叉树操作结构灵活插入删除方便无法快速找父节点三叉链表需要频繁回溯父节点的场景支持双向访问空间开销更大线索二叉树频繁遍历、需要快速找前驱后继省去栈遍历效率高建树和维护逻辑复杂如果你只是单纯学习二叉树链式存储是最推荐的后边我的代码也以它为核心。3. 完整代码实现用C语言从零建一棵二叉树3.1 节点定义与前序建树我在这一节会用 C 语言演示一套完整的链式存储实现包括建树、遍历和统计操作。C 的指针操作最贴近二叉树存储的本质理解了 C 版本再看其他语言的实现会容易很多。建树的方式很多最常用的是通过扩展的前序遍历序列来建树把空子树用特殊符号#表示。比如序列A B # # C # #表示根节点 A左孩子 BB 的左右孩子都是空右孩子 CC 的左右孩子都是空。建树过程递归进行读取一个字符如果不是#就创建节点然后递归创建左子树和右子树。#include stdio.h #include stdlib.h typedef struct BiTNode { char data; struct BiTNode *lchild; struct BiTNode *rchild; } BiTNode, *BiTree; // 用扩展前序序列建树#表示空 BiTree CreateTree() { char ch; scanf( %c, ch); if (ch #) { return NULL; } BiTree T (BiTree)malloc(sizeof(BiTNode)); T-data ch; T-lchild CreateTree(); T-rchild CreateTree(); return T; }有人问为什么要用扩展前序序列而不是直接用标准的前序序列因为标准前序序列无法唯一确定一棵二叉树只有补上所有空位置变成扩展序列递归才能知道什么时候该停。这个思路在序列化和反序列化二叉树时也会用到。3.2 三种递归遍历前序、中序、后序前中后序遍历指的是根节点被访问的时机前序是先访问根再递归访问左子树最后右子树中序是左子树、根、右子树后序是左子树、右子树、根。代码结构几乎一模一样区别只是 visit 的位置void PreOrder(BiTree T) { if (T ! NULL) { printf(%c , T-data); PreOrder(T-lchild); PreOrder(T-rchild); } } void InOrder(BiTree T) { if (T ! NULL) { InOrder(T-lchild); printf(%c , T-data); InOrder(T-rchild); } } void PostOrder(BiTree T) { if (T ! NULL) { PostOrder(T-lchild); PostOrder(T-rchild); printf(%c , T-data); } }这三段代码看似简单但它是理解递归遍历的根基。你要关注的不是代码本身而是递归调用时的“执行栈”每次递归调用都会把当前现场保存到系统栈里等子树处理完再弹出来继续。这也是后边非递归遍历要手动维护栈来模拟的东西。3.3 层序遍历队列的经典用法层序遍历是按“从上到下、从左到右”的顺序逐层访问节点。它和深度优先遍历的思路完全不同要用队列实现。算法流程先把根节点入队然后循环处理每次从队首取出一个节点访问它再把它的左孩子和右孩子依次入队。因为队列是先进先出所以同一层的节点会按顺序被访问完然后才轮到下一层。#include stdbool.h // 假设队列已经实现好这里只写核心逻辑 void LevelOrder(BiTree T) { if (T NULL) return; BiTree queue[100]; // 简化处理实际可用动态队列 int front 0, rear 0; queue[rear] T; while (front rear) { BiTree p queue[front]; printf(%c , p-data); if (p-lchild ! NULL) { queue[rear] p-lchild; } if (p-rchild ! NULL) { queue[rear] p-rchild; } } }层序遍历在很多算法题里是基础操作比如求二叉树最大宽度、按层打印、判断完全二叉树都是在层序遍历框架上加一些统计逻辑。3.4 核心统计操作深度、节点数、叶子数这几个操作是二叉树最常问的“基础能力”实现起来也适合用来检验对递归的理解。求树的高度/深度典型做法是递归如果树为空深度为 0否则深度等于左子树深度和右子树深度中的较大值再加 1。int TreeDepth(BiTree T) { if (T NULL) return 0; int leftDepth TreeDepth(T-lchild); int rightDepth TreeDepth(T-rchild); return (leftDepth rightDepth ? leftDepth : rightDepth) 1; }求节点总数也很直观空树为 0否则节点数等于左子树节点数加右子树节点数再加 1。int CountNode(BiTree T) { if (T NULL) return 0; return CountNode(T-lchild) CountNode(T-rchild) 1; }统计叶子节点数时判断条件要清楚一个节点是叶子当且仅当左右孩子都为空。int CountLeaf(BiTree T) { if (T NULL) return 0; if (T-lchild NULL T-rchild NULL) return 1; return CountLeaf(T-lchild) CountLeaf(T-rchild); }这三个操作的共同点是把大问题拆成左右两个子问题再把子问题的结果合并。二叉树的很多算法题走的都是这个套路熟练之后你会发现万变不离其宗。4. 进阶代码非递归遍历与还原二叉树4.1 非递归遍历手写栈把递归吃透递归好写但有隐患。当二叉树退化成一条链时递归深度等于节点数如果节点很多很容易把系统栈打爆。非递归遍历就是用显式的栈模拟系统栈的行为常见的有两种思路。先看中序非递归这是最经典的一个。核心逻辑从根节点开始一路向左把节点压栈当走到空节点时弹出栈顶节点并访问它然后转向该节点的右子树重复这个过程。void InOrderNonRec(BiTree T) { BiTree stack[100]; int top -1; BiTree p T; while (p ! NULL || top 0) { if (p ! NULL) { stack[top] p; p p-lchild; } else { p stack[top--]; printf(%c , p-data); p p-rchild; } } }前序非递归的代码和中序很接近区别只是访问时机。你可以在压栈之前先访问根节点这样节点顺序就是“根左右”。后序非递归稍微麻烦因为要等左右子树都访问完才能访问根需要额外记录上一个访问的节点或者给每个节点加一个“是否已访问右子树”的标记。void PostOrderNonRec(BiTree T) { BiTree stack[100]; int top -1; BiTree p T; BiTree lastVisited NULL; while (p ! NULL || top 0) { if (p ! NULL) { stack[top] p; p p-lchild; } else { BiTree peek stack[top]; if (peek-rchild ! NULL peek-rchild ! lastVisited) { p peek-rchild; } else { printf(%c , peek-data); lastVisited peek; top--; } } } }这套代码的难点是理解lastVisited的作用它用来判断右子树是否已经处理过。如果右孩子存在且没有被访问过就先去处理右子树否则说明左右子树都处理完了才能弹出并访问根节点。注意非递归遍历的空间复杂度和递归一样都是 O(n)实际运行却不一定会更快因为手动栈操作有额外开销。它最大的价值在于避免系统栈溢出以及让你真正搞懂遍历的顺序是怎么来的。4.2 由前序中序还原二叉树在面试和学习中经常遇到这样一道题给出前序序列和中序序列还原整棵二叉树。原理很简单但自己写代码时容易在下标边界上出错。思路是前序序列的第一个元素一定是根节点在中序序列中找到这个根节点的位置它左边的是左子树的中序序列右边的是右子树的中序序列根据中序左右子树的长度把前序序列也切成左子树和右子树两段然后递归还原。BiTree BuildByPreIn(char pre[], int preL, int preR, char in[], int inL, int inR) { if (preL preR) return NULL; BiTree T (BiTree)malloc(sizeof(BiTNode)); T-data pre[preL]; int k inL; while (in[k] ! pre[preL]) k; int leftCount k - inL; // 左子树节点个数 T-lchild BuildByPreIn(pre, preL 1, preL leftCount, in, inL, k - 1); T-rchild BuildByPreIn(pre, preL leftCount 1, preR, in, k 1, inR); return T; }用前序序列A B D E C和中序序列D B E A C来试。根是 A中序里 A 左边是D B E右边是C说明左子树有 3 个节点右子树有 1 个节点。前序里 A 后面紧跟的 3 个元素B D E就是左子树的前序C是右子树的前序。递归还原后得到A / \ B C / \ D E中序 后序也能还原思路类似。但前序 后序不行因为无法区分左右子树树形会有歧义。这是一个高频易错点我建议专门记一下。5. 工程实践Python版本与调试心得5.1 Python版本面试和刷题更常用C 语言版适合理解原理但实际刷题或者工作里Python 的简洁写法更常用。我用 Python 重新实现一遍核心逻辑你会发现结构其实一模一样只是指针换成了对象引用。class TreeNode: def __init__(self, val): self.val val self.left None self.right None def build_tree(seq): 根据扩展前序序列构建二叉树# 表示空节点 if not seq: return None val seq.pop(0) if val #: return None root TreeNode(val) root.left build_tree(seq) root.right build_tree(seq) return root def preorder(root): if root is None: return [] return [root.val] preorder(root.left) preorder(root.right) def inorder(root): if root is None: return [] return inorder(root.left) [root.val] inorder(root.right) def postorder(root): if root is None: return [] return postorder(root.left) postorder(root.right) [root.val] def level_order(root): if root is None: return [] result [] queue [root] while queue: node queue.pop(0) result.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) return resultPython 版本里有个小坑要注意build_tree里用了seq.pop(0)会直接修改传入的列表。在测试时你需要确保调用前序列是可变且不会被其他代码共享的状态否则会拿到意外结果。5.2 调试二叉树的三板斧我自己在学习和调二叉树代码时总结了三件非常好用的工具强烈建议你用起来。第一个是“带空标记的先序输出”。写一个专门用于调试的函数把空孩子也打印出来def debug_print(root): if root is None: print(#, end ) return print(root.val, end ) debug_print(root.left) debug_print(root.right)这个函数能把你构建的树完整输出成一个唯一的“序列化”字符串可以用来验证建树是否正确也可以作为树的回文校验手段。第二个是“层序输出带层数”。层序遍历时把每一层的节点括在一起打印能够非常直观地看到树的总体形状。def debug_level(root): if not root: return queue [root] while queue: size len(queue) for _ in range(size): node queue.pop(0) print(node.val, end ) if node.left: queue.append(node.left) if node.right: queue.append(node.right) print() # 每一层换行第三个是“先用小树练手”。我强烈建议测试时从空树、单节点树、完全二叉树、只有左子树的退化链状树这四类用例开始。空树和单节点树能查边界条件完全二叉树能验证层序逻辑退化链状树能验证递归是否会爆栈。5.3 常见问题速查表我把二叉树学习和代码实现中容易踩的坑整理成一张速查表方便你写代码时对照自查。问题原因解决办法递归遍历时栈溢出树退化成链表递归深度过大改用非递归遍历或改用迭代栈建树时输入格式错误输入的扩展前序序列格式不对调试时先输出序列核对确保空节点标记正确层序遍历时死循环忘记把节点的左右孩子判空再入队入队前必须检查孩子是否为 NULL求深度时结果总是少 1根节点深度定义不同统一约定根节点深度为 1 还是 0并在代码注释里写清楚还原二叉树时下标越界前序序列分段时边界算错用 leftCount 先算出左子树节点数再推导各段边界判断完全二叉树失败没有在遇到空节点后继续检查后续节点层序遍历中遇到第一个空节点后后续节点必须全为空关于判断完全二叉树我再多说一句。正确的做法是层序遍历遇到第一个空节点后设置一个标记如果标记已设置且后面又出现非空节点说明这不是完全二叉树。很多人在这一步卡住是因为只判断了空节点的位置没有做“标记后检查”的处理。最后分享一个我自己的习惯写二叉树的递归函数时第一行永远写递归出口也就是判空返回的语句然后才写递归逻辑。这样能避免一半的野指针和空引用问题。每次写完代码先用最小测试用例跑一遍再逐渐叠加树的高度确认没有隐藏问题。这个习惯帮我省了很多排查时间也让我在面试时写树上代码更加从容。
阅读完成 · 觉得有帮助？
