数据结构二叉树：遍历、线索化与运行时错误排查

数据结构四二叉树学数据结构绕不开二叉树408考研、期末考、实验报告、机试到处都有它的影子。我当年学到这里的时候也有种“听懂了但不会写代码写出了代码却总报错”的憋屈感尤其是那几个运行时错误一度让人怀疑电脑是不是在针对我。这篇就顺着二叉树这条线把概念、存储、遍历、线索化、排序树以及实际写代码时踩过的坑一起捋一遍希望能让你少走几步弯路。先说清楚这篇能帮你解决什么问题如果你正在准备王道408或者本科的数据结构考试这篇可以帮你把二叉树的核心知识点串起来顺带补充一些手算题的技巧如果你正在赶数据结构实验报告这篇里有可以直接抄作业的代码框架和实验心得如果你是自学看到“运行时错误”这个词就头大那第四部分专门对着这些问题做了一次排查实录。总之不管你属于哪种情况都可以从我这份折腾过的经验里捞点有用的。二叉树到底是什么——核心概念与存储结构解析1.1 先搞清楚二叉树在“树”里的地位很多教材上来就抛定义二叉树是每个节点最多有两个子树的树结构。这个说法没错但它没告诉你为什么偏偏是“两个分支”。实际上树形结构之所以在计算机里大量落地成二叉树是因为二叉树天然适合用二进制思维去表示和运算相比普通多叉树它的结构最简单、规律最强逻辑判断只有“左、右”两个方向方便用递归、循环和数组去处理。计算机里的表达式树、哈夫曼树、搜索树、堆本质上都是二叉树的某种变形或应用。从考研角度讲你需要把树和二叉树的区别先刻在脑子里普通的树不限制子节点数量兄弟节点之间没有顺序关系而二叉树每个节点的子树有严格的左右之分即使只有一个子节点也必须标明是左孩子还是右孩子。这一点在题目里经常拿来考比如“具有n个节点的二叉树有多少种形态”“某二叉树中度为1的节点个数是X求叶子节点数”这类题考的都是对二叉树结构特性的理解。二叉树的核心性质也要背熟尤其是这几条第i层最多有2^(i-1)个节点深度为k的二叉树最多有2^k - 1个节点叶子节点数n0等于度为2的节点数n2加1即n0 n2 1。前两条是常识性的最后一条在推导各种题目时特别常用比如给你节点总数和叶子数让你反推二叉树深度绕不开它。1.2 三种存储方式顺序存储、链式存储、静态链表二叉树的存储是我当时最纠结的部分。先看最常见的链式存储也就是二叉链表。每个节点体面地放着数据域和两个指针域一个指向左孩子一个指向右孩子。因为结构直观、动态分配灵活考试和实际工程里基本都用它。结构体定义长这样typedef struct BiTNode { int data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree;如果还要方便找父节点可以再加一个父指针变成三叉链表但考研笔试和面试一般不讲这个知道概念就行。顺序存储则利用数组下标来映射节点关系核心公式是对于下标为i的节点从1开始计数左孩子下标是2i右孩子是2i 1父节点是i/2向下取整。这种存储方式最大的好处是不用指针连续存储速度快但它要求树尽量是“完全二叉树”形态否则下标空洞会浪费大量空间。比如一棵深度为4但每层只有最左边一个节点的退化树用顺序存储硬存会需要2^4 - 1 15个位置实际却只用了4个空间利用率惨不忍睹。所以真题里经常专门考“判断是否为完全二叉树”“给一个完全二叉树的顺序存储数组画出树的形态”这类题目。第三种是静态链表用结构体数组模拟指针。也就是在数组里放data、lchild下标、rchild下标用-1表示空。这种方式在C语言里没有指针概念的时候经常用比如写哈夫曼树、并查集时都用得到。它的好处是内存连续可控、容易调试坏处是插入删除不如链式灵活。实际代码里我用得最多的是前两种静态链表更多是处理特定场景。1.3 满二叉树、完全二叉树、搜索二叉树等概念辨别概念辨析是二叉树选择题的第一大坑。满二叉树是每一层都完全填满深度为k时节点总数恰好是2^k - 1。完全二叉树是除了最后一层外都填满最后一层的节点集中在左侧连续排列重点在“连续”二字。判断是否为满二叉树的核心只有一条所有节点的左右子树深度是否相等或者树的总节点数是否刚好等于2^depth - 1。我常用递归法写判断函数思想就是分别取左右子树的深度如果深度相等且左右子树也都是满二叉树那么整棵树就满。int treeDepth(BiTree T) { if (T NULL) return 0; int leftDepth treeDepth(T-lchild); int rightDepth treeDepth(T-rchild); return (leftDepth rightDepth) ? (leftDepth 1) : (rightDepth 1); } bool isFull(BiTree T) { if (T NULL) return true; if (treeDepth(T-lchild) ! treeDepth(T-rchild)) return false; return isFull(T-lchild) isFull(T-rchild); }搜索二叉树也叫二叉排序树、二叉搜索树它的特性是左子树所有节点值小于根节点右子树所有节点值大于根节点且左右子树也各自满足这个规则。这个结构后面单独讲因为它牵扯到插入、删除、查找三个核心操作是笔试和机试的高频考点。二叉树的遍历从递归到非递归的完整实操2.1 四种递归遍历写法二叉树的遍历是“数据结构四件套”里最该拿下的基本功。前序、中序、后序遍历的递归写法非常简单核心区别就是访问根节点的时机。先说前序先访问根节点再递归左子树最后递归右子树。中序先递归左子树再访问根最后递归右子树。后序先递归左右子树最后访问根。三种写法代码结构几乎一样差别只是printf和递归调用的顺序但很多初学者会在递归边界上犯迷糊最常见的错误是只判断了当前节点非空忘了递归调用自身函数时的终止条件导致访问空指针的data域然后报Segmentation fault。写递归函数时一定要记住一个原则进入函数先判空。这是所有二叉树递归函数的第一行“护身符”。// 前序遍历 void PreOrder(BiTree T) { if (T NULL) return; printf(%d , T-data); PreOrder(T-lchild); PreOrder(T-rchild); } // 中序遍历 void InOrder(BiTree T) { if (T NULL) return; InOrder(T-lchild); printf(%d , T-data); InOrder(T-rchild); } // 后序遍历 void PostOrder(BiTree T) { if (T NULL) return; PostOrder(T-lchild); PostOrder(T-rchild); printf(%d , T-data); }层序遍历则不同它需要借助队列按层访问一层一层从左到右扫过去。这个算法在思维上更接近“广度优先搜索”用数组模拟队列就能轻松实现。很多同学写层序遍历时硬用递归结果各种别扭其实这里用队列就是最自然的思路不建议为了炫技硬上递归。2.2 非递归遍历为什么总是“运行时错误”考研408对非递归遍历有明确要求尤其用栈模拟递归的过程这是每年必考的手写代码题。非递归前序和中序的思想很一致用一个栈来模拟递归中的函数调用栈。中序的流程是从根节点出发沿左子树一直往下走边走边把节点压栈直到走到空弹出栈顶节点访问它然后把指针移到右子树继续同样的过程。写下这段代码时特别容易碰到的运行时错误包括栈溢出、死循环、空指针解引用。栈溢出的原因往往是循环里少了“指针移动”这一步或者压栈条件写成了while (!stackEmpty p NULL) 这种永真条件导致节点被无限压栈最终栈的容量被撑爆。死循环则常常发生在出栈后忘了把指针指向右孩子导致同一个节点反复被处理。你可以这样理解递归版本里的“隐式状态”全由函数调用栈帮你保存非递归版本要自己维护这个“当前走到哪一步”的状态任何一个环节漏了就会出问题。void InOrderNonRec(BiTree T) { BiTree stack[100]; int top -1; BiTree p T; while (p ! NULL || top ! -1) { while (p ! NULL) { stack[top] p; p p-lchild; } if (top ! -1) { p stack[top--]; printf(%d , p-data); p p-rchild; } } }后序非递归则更麻烦一些因为根节点必须等左右子树都访问完才能输出需要记录“上一次访问的节点”来判断当前是从左子树回来还是从右子树回来。这块容易让人绕晕我建议初学阶段先把中序非递归练熟后序可以在理解了中序的基础上再扩展思路是增加一个辅助指针prev。2.3 根据遍历序列反推二叉树手算题标准套路考试里“已知前序和中序求后序”是经典题这种题考的就是对遍历顺序的理解。核心结论是前序或后序中序可以唯一确定一棵二叉树而前序后序不能唯一确定。这句话很多同学直接背了但没有理解为什么。关键在中序序列的作用中序能够将左右子树精确分开前序或后序则负责提供根节点的位置。单独看前序和后序虽然也能找到根但左右子树的分界点不唯一所以无法确定树的形态。手算时我的习惯是先看前序序列的第一个元素确定根节点再到中序序列里找到这个根的位置左边是左子树的中序序列右边是右子树的中序序列然后回到前序序列按顺序把左右子树的前序切分出来最后递归处理两个子树。这个步骤听起来复杂实际上用笔和纸画几次就能熟练考场上速度很重要。我建议平时多练习几组数据不用写代码纯手推锻炼脑内递归的速度。线索二叉树与二叉排序树考试高频与实战要点3.1 线索二叉树为什么要给“空指针”用起来线索二叉树这个知识点出现的频率极高因为它考的是对二叉树空间利用的深入理解。普通二叉链表中n个节点共有2n个指针域真正被用来指向孩子的只有n-1个每个节点除了根节点外都有一个指针指向它剩下n1个指针是空的。线索化就是把这些空指针利用起来指向节点的前驱或后继节点从而方便遍历。中序线索化最常用因为它能把中序遍历变成类似链表的顺序访问。线索化时定义一个全局变量pre指向前一个访问的节点如果当前节点左孩子为空就让它指向pre如果pre的右孩子为空就让它指向当前节点。这里有一个重要的概念要区分ltag和rtag是用来标记指针是“孩子”还是“线索”的。ltag0表示lchild指向左孩子ltag1表示lchild指向前驱线索。理解了这个标记你才能正确判断什么时候该跟指针走什么时候该跟线索走。线索二叉树的定义和线索化代码在严蔚敏版教材和王道书里都有标准答案但实验报告里经常要求写出“中序线索化”和“中序线索遍历”的完整代码。核心的遍历逻辑是先找到最左下角的节点然后不断利用后继线索往右走。如果当前节点rtag1直接走线索如果rtag0就转向右子树的最左下角。3.2 二叉排序树插入、删除、查找一条龙二叉排序树在机试和面试里属于必考内容因为它考查的是“动态查找表”的思想。插入操作的逻辑不复杂从根出发如果当前节点为空就直接新建节点插入如果待插入值小于当前节点值往左走如果大于往右走。这个过程用递归写非常简洁。BiTree BSTInsert(BiTree T, int key) { if (T NULL) { BiTree node (BiTree)malloc(sizeof(BiTNode)); node-data key; node-lchild node-rchild NULL; return node; } if (key T-data) { T-lchild BSTInsert(T-lchild, key); } else if (key T-data) { T-rchild BSTInsert(T-rchild, key); } return T; }但删除操作就复杂多了因为有三种情况叶子节点直接删除只有一个子树让子树接替自己有两个子树则用左子树的最大节点或右子树的最小节点替换当前节点再删除那个替换节点。第三种情况是整个删除操作的难点因为替换节点的删除又可能引发新的删除逻辑。很多同学第一次写BST删除时会把自己绕进去建议画一个三节点的树逐步走一遍就理解了。查找操作是递归或循环都可以时间复杂度平均O(log n)但最坏情况会退化到O(n)也就是树变成了单链表。这也是为什么后面要引入平衡二叉树的原因。不过考试阶段你先把二叉排序树的三种操作写好已经能拿到大半分数了。3.3 二叉树的深度、节点计数与判断完全二叉树“二叉树的深度”是热搜词里单独出现的一个概念足以说明它在作业和考试里的重要性。深度定义为根节点到最远叶子节点的路径长度加1空树深度为0。递归求深度的代码已经在前面isFull函数里出现过了核心就是max(左子树深度, 右子树深度) 1。节点计数我常用的代码总共两个函数一是统计总节点数二是统计叶子节点数。叶子统计的核心是if (T-lchild NULL T-rchild NULL) return 1。判断完全二叉树则是层序遍历的经典应用。思路按层序遍历整棵树遇到空节点时记个标记如果后面再遇到非空节点那这棵树就不是完全二叉树。因为完全二叉树的特性是最后一层节点连续空节点后面不能再出现真实节点。还有一种等价方法是判断下标关系按完全二叉树编号规则若某个节点下标大于总节点数则不是完全二叉树。笔试时用第一种方法最好写机试时用第二种方法可以做出O(n)的判断。常见运行时错误排查与实验报告避坑指南4.1 二叉树程序运行时错误排查速查表写二叉树程序时总是报运行时错误这个热搜词条简直说出了很多人的心声。我当年排查了一晚上的经历至今记忆犹新这里把最常见的错误和排查思路整理成一张表方便你对照查看。错误现象常见原因排查思路Segmentation fault段错误访问了空指针的data或左右孩子检查递归入口有没有判空检查创建节点时lchild和rchild是否初始化程序卡死或栈溢出递归没有终止条件或非递归压栈条件错误检查递归边界检查循环中p指针是否真的在移动输出顺序错乱遍历时printf位置放错对照前中后序定义检查访问根节点的时机节点数统计错误递归返回值被覆盖检查返回语句是否在递归分支之外插入节点丢失传入的指针没有接收递归返回值确认插入函数是否使用了返回值接收新的子树根节点第四行是链表和二叉树初学者最容易犯的错你觉得你已经把新节点挂上了但实际插入操作没有真正改变树的结构。原因在于传参时如果传的是指针的副本不返回新的根节点就无法把更新后的子树传回调用方。BSTInsert里必须return node或者T就是为了保证新建的子树能一层层挂回去。段错误在写二叉树时的高发区还有释放内存很多实验要求最后销毁整棵树销毁时也要先递归销毁左右子树再free根节点顺序反了就会访问到已释放的内存。这个顺序和后续遍历的顺序是一致的建议写成统一的PostOrder风格。4.2 数据结构实验报告的正确打开方式如果你正在写数据结构实验报告我建议按这个结构来组织需求分析、概要设计、详细设计、代码实现、运行测试、心得体会。每个部分都要和你的代码对上号。需求分析里讲清楚要解决什么问题比如“实现二叉树的前中后序递归遍历和层序遍历”概要设计里画一个简单的模块结构图写清每个函数的功能、参数和返回值详细设计里把核心函数的伪代码或流程图写清楚运行测试要放运行截图并且配上边界测试用例比如空树、单节点树、只有左子树的树。实验报告最容易翻车的地方是“运行测试”只贴了一张成功的截图这会让老师觉得你没有做充分的边界测试。我的建议是至少测四组数据空树、单节点、完全二叉树、非完全二叉树并说明每组数据的作用。这样既显得专业又能预防代码里潜在的问题。另外报告里不要照搬教材代码哪怕是一模一样的思路也建议改一下变量名、调整一下函数结构再在注释里写上你自己的理解。这不是鼓励你偷懒而是阻止你变成调包侠毕竟面试和考试时最终还是要靠你自己写得出来。4.3 王道408与期末复习重点整理如果你在备考408或者期末二叉树章节有四个重点必须掌握第一二叉树的遍历递归和非递归都要会尤其是中序非递归和层次遍历第二根据两种遍历序列构造二叉树这个不但笔试考机试也经常出第三线索二叉树的构造和遍历线索化的代码要在理解的基础上默写第四二叉排序树的操作插入删除查找一条龙特别是删除操作的各种情况。我的复习顺序建议是先理解手算逻辑再写代码最后再回来做选择题。很多同学习惯反过来选择题做了几遍代码一行没写结果考试遇到“写出中序非递归遍历算法”直接懵住。代码这东西看十遍不如动手调一遍。调试过程能帮你加深对指针、递归、栈这些概念的理解这种理解是刷题刷不出来的。还有一些常见手算题型可以提前准备给定n个节点的二叉树求最大深度和最小深度给定完全二叉树的数组求某个节点的父节点和孩子节点下标给定先序和后序序列判断是否能构造一棵唯一的二叉树计算二叉树的带权路径长度。这些题万变不离其宗本质都是对二叉树基本性质的掌握。我个人在实际操作中的体会是二叉树所有的算法题不管是遍历、计数、求深度还是判断满二叉树本质上都是在教你“如何处理树的左右关系”。写代码时先把特殊情况写清楚比如空树怎么处理、只有一个节点怎么处理然后主体逻辑自然就顺了。还有一个很实用的小技巧遇到复杂的指针链表操作先在纸上画出节点之间的关系图再对照着写代码比在脑子里空想要可靠得多。如果你能把递归和非递归遍历都默写出来并且搞清楚为什么那样写那二叉树这一章基本上就稳了。