简介这是一份面向C初学者、数据结构课程学生以及需要手写二叉树代码的读者的学习型资源围绕创建、遍历、添加、查找与删除五类核心操作提供可直接运行的完整代码与配套说明适合在课程实验、期末复习或算法入门阶段对照练习。压缩包共3个文件包括一个C源文件、一份Markdown文档和一份txt部署说明整体约5KB。内容覆盖节点结构定义、二叉树类封装、各操作时间复杂度分析代码简洁注释清晰有助于读者掌握递归与非递归遍历、节点插入与删除时的指针调整等关键细节。代码中给出了清晰的函数接口与主流程便于拆解复用README文档则梳理了实现思路与踩坑点能帮助读者边读边练加深对树形结构递归特性的理解。目前已有159人学习下载作为轻量级示例可帮助读者在短时间内完成二叉树核心操作的编码实现与理解。资源体量轻、目录简洁适合作为二叉树模块的速查样例。开头最近有读者在后台问我一个问题C实现二叉树的创建、遍历、添加、查找和删除到底该怎么写这个问题看着基础实际上坑非常多——尤其是删除操作里同时有两个子树的case新手十个有八个会写崩。C里写二叉树和C语言最大的区别在于你要时刻想着内存管理new出来的节点必须delete干净否则几万次插入删除下来内存就直接爆炸了。这篇文章我打算从零开始把二叉搜索树BST这套完整实现讲清楚包含创建、递归/非递归遍历、添加节点、查找节点、删除节点每一步都会解释我为什么这么写以及实际调试时踩过的坑。不管你是刚学到数据结构的学生还是刷算法题准备面试的C爱好者都可以直接抄走这套代码建议先看思路再看代码最后自己重新默写一遍。1. 先想清楚要什么二叉搜索树的设计目标1.1 二叉搜索树到底要解决什么问题二叉树本身只是一个数据结构概念但我们要实现的是二叉搜索树Binary Search Tree简称BST。BST有一个核心约束对于任意一个节点它左子树上的所有节点值都小于它右子树上的所有节点值都大于它。通俗点理解就像图书馆里按照编号整理书籍你去查一本书的编号不需要把整个图书馆翻一遍只需要先去中间那排比较小了往左走去查大了往右走去查三次五次就能定位到目标。这个约束带来的最大好处是查找效率高——平均情况下时间复杂度是O(log n)。对比一下链表删除一个节点可能要在O(n)的时间里先找到这个节点BST直接把整个操作压缩到了对数级别。当然这是针对一棵平衡的树来说的如果节点插入顺序恰好是递增或递减的树会退化成一条链查询效率就变成O(n)这也是为什么后续会有AVL树、红黑树这些自平衡树但那是后话先把基础版实现搞明白再说。1.2 结构体的定义与关键性设计选择C里最简单的写法是定义成一个结构体内部用指针指向左右孩子struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };有人会问为什么不用class其实完全可以TreeNode里只有公有成员用struct纯粹是写着省事语义上也更接近C时代的习惯。构造函数必须写上不然每次new完之后还要手动给left和right置空容易漏。另一个设计选择是要不要把树的操作封装成一个BinarySearchTree类我的建议是如果要经常重复使用最好封装。因为删除操作涉及根节点的替换直接在外面写一个void函数处理不了根节点需要被换成孩子节点的情况要么返回新的根节点要么用二级指针要么把根节点指针放在类的成员变量里。用类封装一个private TreeNode* root_所有操作都变成成员函数代码会清晰很多。下面我给出的代码就是这种类组织方式。2. 从无到有创建与添加节点的核心细节2.1 递归函数返回值的四个关键问题写递归二叉树操作最难的是想清楚一件事情函数的返回值怎么定很多新手栽跟头就栽在这里——写了个void insert结果传进去一个指针改来改去发现调用方那边的树一点变化都没有。因为指针本身是按值传递的函数内部给指针赋新值不会影响调用方的指针变量。处理这个问题一般有三种套路函数返回新节点指针调用方用返回值接住函数参数使用TreeNode*引用函数参数使用TreeNode**二级指针。我个人最推荐第一种因为它的逻辑最直观你给我一棵子树的根节点我返回插入之后新的根节点。即使这棵子树是空指针我new出来的节点也能顺利接到上一层。结构统一出错概率最低。2.2 插入操作的完整实现TreeNode* insertNode(TreeNode* node, int val) { if (node nullptr) { return new TreeNode(val); } if (val node-val) { node-left insertNode(node-left, val); } else if (val node-val) { node-right insertNode(node-right, val); } return node; }这里我处理了值相等的情况跳过插入不做任何操作。这是BST的常见约定但如果你想让树支持重复值可以在相等时固定往右子树插入或者给每个节点加一个count计数。刷题的时候要注意题目到底允不允许重复值这是很多人踩坑的地方。创建一棵树的时候有一种经典扔面试题的做法给定一个前序序列比如{5,3,7,2,4,6,8}依次调用insertNode插入空树。用户输入的时候为了从键盘直接创建树我通常先接收一个数字n表示节点个数然后循环调用insertNode。别问我为什么要先从空格或者换行符输入——C的cin默认就会跳过空白字符这里没什么坑但如果你用scanf或者getline就别搞混了。void createFromInput() { int n, val; cin n; for (int i 0; i n; i) { cin val; root_ insertNode(root_, val); } }这里有一个容易被忽略的细节root_每次都要接收返回值。有新手会写insertNode(root_, val)不赋值结果插入几次之后发现树根本没变。原因就是我在开头说的指针按值传递的问题老生常谈但架不住每次都有人踩。2.3 内存管理的两个铁律铁律一new的每个节点最后必须delete。否则你的程序运行时间久了内存占用会持续涨上去就是所谓的内存泄漏。对于二叉树来说删除整棵树最安全的做法是后序遍历删除——先删左子树再删右子树最后删除自己。void destroyTree(TreeNode* node) { if (node ! nullptr) { destroyTree(node-left); destroyTree(node-right); delete node; } }铁律二释放一个节点后不要再去访问它。这听起来像废话实际场景里却是大坑。比如删除某个节点时如果你先把节点的left和right保存到局部变量delete之后再顺着原指针去访问它的孩子程序会崩溃或者出现访问已释放内存这种难以复现的bug。在C里delete之后的指针是悬垂指针dangling pointer无论如何都不要再去解引用它。3. 遍历的四种姿势递归、栈模拟、层序3.1 先序、中序、后序递归遍历递归遍历的核心代码少到让你怀疑人生void preorder(TreeNode* node) { if (node nullptr) return; cout node-val ; preorder(node-left); preorder(node-right); } void inorder(TreeNode* node) { if (node nullptr) return; inorder(node-left); cout node-val ; inorder(node-right); } void postorder(TreeNode* node) { if (node nullptr) return; postorder(node-left); postorder(node-right); cout node-val ; }注意观察中序遍历的输出结果——只要是BST中序遍历出来的序列一定是有序递增的。这个特性是面试和笔试的高频考点比如题目验证一棵树是不是合法的BST光靠中序排序就能做。我经常用中序输出作为插入、删除操作正确性的快速验证手段插入完之后跑一次中序看看是不是有序的基本就能判断树的形状对不对。3.2 非递归遍历栈是怎么帮你还原递归的递归好用但递归有两个毛病一是函数调用有额外开销二是递归深度等于树的高度如果树退化成链递归一万层直接用完栈程序就崩了栈溢出。所以实际工程项目里经常用显式栈来模拟递归。先序非递归比较好写用一个栈先把右子树入栈再左子树入栈弹出栈顶就是下一个要访问的节点。void preorderIterative(TreeNode* root) { if (root nullptr) return; stackTreeNode* st; st.push(root); while (!st.empty()) { TreeNode* cur st.top(); st.pop(); cout cur-val ; if (cur-right) st.push(cur-right); if (cur-left) st.push(cur-left); } }后序非递归稍微麻烦一点一个常见技巧是用两个栈。第一个栈按根-右-左的顺序入栈输出的时候正好就是后序左-右-根。也有更省空间的做法——用一个栈加一个prev指针标记上一次访问的节点但两个栈的写法最好记忆我建议直接背下来。中序非递归也属于必考题从根开始先把整条左链全部压栈然后弹一个访问访问完右孩子再把右孩子的整条左链压栈。这个逻辑在面试里特别常见我就不展开代码了核心就一句话能往左走就一直往左走走不动了再弹栈。3.3 层序遍历二叉树和队列的经典组合层序遍历就是按层级从上到下、从左到右扫描这需要借助队列queue实现。每弹出一个节点就依次压入它的左孩子和右孩子。因为队列的先进先出特性天然保证同一层的节点会连着出队。void levelOrder(TreeNode* root) { if (root nullptr) return; queueTreeNode* q; q.push(root); while (!q.empty()) { TreeNode* cur q.front(); q.pop(); cout cur-val ; if (cur-left) q.push(cur-left); if (cur-right) q.push(cur-right); } }如果你想按层打印比如第一行打印第一层第二行打印第二层那就在while循环里再套一层for循环进入for之前先用q.size()记下当前层的节点数只处理这个数目的节点。这个技巧在LeetCode 102题二叉树层序遍历里是标配。4. 查找从递归到迭代的优化路径4.1 查找一个值递归版和安全问题查找的具体逻辑非常简单当前节点为空就返回nullptr当前值等于目标值就返回当前节点目标值小于当前值就去左子树找大于就去右子树找。TreeNode* searchNode(TreeNode* node, int target) { if (node nullptr || node-val target) { return node; } if (target node-val) { return searchNode(node-left, target); } return searchNode(node-right, target); }这个函数有两个用途一是判断树里是否存在某个值二是返回那个节点的指针方便后续做修改或者删除。注意一个容易忽略的问题如果调用方在找到节点后拿到了裸指针却不小心delete了它整棵树的该节点就断了后面再遍历会崩溃。所以裸指针的管理要靠约定和自觉——这也是C后来搞出shared_ptr、unique_ptr的一部分原因实际项目里可以改用智能指针。4.2 迭代查找为什么更推荐递归查找写起来简单但如果树的深度很大递归调用栈付出的代价不值得。迭代版用一个while循环就能搞定完全没有栈溢出风险效率也高TreeNode* searchNodeIterative(TreeNode* node, int target) { while (node ! nullptr node-val ! target) { if (target node-val) { node node-left; } else { node node-right; } } return node; }这两个版本的区别就像你查字典递归版像是每次都问别人我要找的词在左边还是右边然后让别人继续帮你查迭代版是你自己翻书一路找过去。功能一样但迭代版更节省中间环节。最终版代码里我会直接使用迭代版作为查找的核心实现。4.3 两个高频变体找最小值和最大值BST在结构上的一个天然特性最左下角的节点是最小值最右下角的节点是最大值。查找它们甚至不需要比较值只需要一路向左或者一路向右走到尽头。TreeNode* findMin(TreeNode* node) { if (node nullptr) return nullptr; while (node-left ! nullptr) { node node-left; } return node; }这个函数在删除操作里是刚需——删掉有两个子树的节点时我们需要从右子树里找到中序后继也就是右子树的最小值节点来替代它。很多人不知道中序后继是什么概念其实它就是中序遍历中当前节点之后被访问的那个节点数值上等于比当前节点大的最小节点。在BST里它一定在右子树的最左边记住这句话就够了。5. 删除节点二叉树操作里最容易翻车的环节先给结论删除是二叉树操作里最复杂的一个因为要处理的情况多而且每种情况的做法都不同。千万别硬背代码一定要理解每一种情况背后的为什么否则换个应用场景你照样懵。5.1 三种情况的划分与处理情况一要删除的节点是叶子节点没有孩子。这个最简单直接delete掉同时让它的父节点对应的指针指向nullptr即可。情况二要删除的节点只有一个孩子。做法是让这个唯一的孩子顶上被删除节点的位置然后delete掉原节点。你可以类比成要裁员一个人直接让他的副手接替位置。情况三要删除的节点有两个孩子。这个最复杂直接删掉会让左右子树都变成孤儿。经典解法是从左子树里找最大值或者从右子树里找最小值拿出来顶替被删除节点。注意我们不一定真的删除这个节点本身——我们把它替换成后继节点然后在右子树里递归删除那个后继节点。为什么要从右子树中找最小值来顶替因为右子树的最小值一定大于左子树的所有节点而且小于等于右子树的其他节点顶替之后BST的有序性不会被破坏。相反如果你选择左子树的最大值同理。两种策略都能用但通常大家都用右子树的最小值因为中序后继在删除操作中更好维护。5.2 删除的完整实现下面这段代码会直接暴露一个新手常犯的思维误区——删除之后怎么返回我们的策略依然是返回处理完后当前子树的新根节点。TreeNode* deleteNode(TreeNode* node, int target) { if (node nullptr) { return nullptr; } if (target node-val) { node-left deleteNode(node-left, target); } else if (target node-val) { node-right deleteNode(node-right, target); } else { // 找到了要删除的节点 if (node-left nullptr) { TreeNode* rightChild node-right; delete node; return rightChild; } else if (node-right nullptr) { TreeNode* leftChild node-left; delete node; return leftChild; } // 两个子节点都在找右子树的最小值 TreeNode* minNode findMin(node-right); node-val minNode-val; node-right deleteNode(node-right, minNode-val); } return node; }仔细看两个子节点都在这个分支我们并没有delete掉minNode指向的节点而是把它复制到当前节点上然后再在右子树里递归删除那个原本的minNode。这么做的原因是minNode很可能还有右孩子比如右子树不是一条链的话直接删会破坏树结构但递归删除会妥善处理它没有左孩子的情况。逻辑上是干净利落的。5.3 删除根节点时的三个坑第一个坑如果你用deleteNode(root_, val)却忘了给调用方赋返回值根节点删了或者换了你手里的root_还是旧指针。所以入口函数一定要写成root_ deleteNode(root_, val)。第二个坑删除之后立刻中序输出顺序应该依然是有序的。如果有玩家发现输出里的重复值或者漏了一个八成是在两个子节点的分支写错——比如拿左子树最大值来顶替却从右子树里删了自己要的节点。第三个坑不确定minNode是否真的会被delete需要层层传递返回值。我之前遇到过一种写法是先保存TreeNode* tmp minNode; node-val minNode-val; deleteNode(node-right, minNode-val); delete tmp;这种情况如果没删干净就释放了同一块内存两次double free程序直接报错。用递归返回值的方式可以完全规避这个问题。6. 常见问题与排查技巧实录6.1 新手反复踩坑的几个点我整理了一张速查表读者可以对照自查症状可能原因解法插入后中序遍历顺序不变调用insertNode时没接收返回值root_ insertNode(root_, val)删除节点后程序崩溃访问了delete之后的内存delete后立刻置nullptr递归访问时栈溢出树退化成链递归深度过大改用迭代遍历或自平衡树重复值进入树插入时没处理相等情况约定相等时跳过或固定往右走中序输出有乱序两个孩子的删除分支替换值写错先用findMin定位再递归删除内存占用持续上涨忘了析构整棵树或delete单节点后序遍历销毁树还有一种很隐蔽的错误先序和中序遍历可以唯一确定一棵二叉树但只拿先序和后序是无法唯一确定的。如果我们做删除操作或者重建树操作时依赖了这个前提容易踩坑。比如你想通过输入先序序列重建BST就必须注意BST的空节点标识符要怎么处理否则输入根本没法区分空子树。6.2 调试二叉树的两板斧第一板斧dump中序序列。凡是对树做过添加、删除操作马上输出一次中序遍历检查是否有序。无序树坏了有序大概率没问题。第二板斧可视化打印树的结构。我一般用递归打印树到控制台核心思想是先用中序算出每个节点的偏移量再按层输出空格。简单一点的做法是写一个按层打印的levelOrder每层节点后面加个逗号。可视化对debug的帮助太大了光靠人眼盯代码很难想象实际树长什么样。这里给一个简化版本适用命令行环境void printTree(TreeNode* node, int depth) { if (node nullptr) return; printTree(node-right, depth 1); for (int i 0; i depth; i) cout ; cout node-val endl; printTree(node-left, depth 1); }把树横过来打印在控制台上节点位置和缩进能直观反映出左右子树的高度差。我调试时顺手就把这个函数加进类里每次操作后跑一次树长什么样一目了然。7. 从基础到工程化的几个扩展方向如果你已经把上面这套代码跑通了我建议下一步尝试以下三个方向对理解和求职面试都有实际帮助其一把裸指针全部替换成智能指针。C工程中unique_ptrTreeNode是首选因为你总是希望独占父子节点关系。但注意递归时不能把同一个节点插入到两个父节点下否则unique_ptr所有权会冲突。使用shared_ptr则要面临循环引用和缓存开销一般来说二叉树用unique_ptr最自然。其二实现AVL树或者红黑树。它们都是在BST基础上增加平衡维护操作。AVL树要求左右子树高度差不超过1插入后需要做左旋、右旋、左右旋、右左旋判断条件就是平衡因子。你一旦理解了BST的插入和删除逻辑这些旋转操作就只是锦上添花。其三把树的节点类型从int改成模板。templatetypename T struct TreeNode;这样你的树就能存放任意可比较类型的数据字符串、浮点数、自定义结构体都能塞进去。这也是从会写算法题到能写通用工具库的必经一步。我在实际工作中写二叉树的机会不算多但面试里考察频率很高而且很多高级算法比如线段树、B树、堆、哈夫曼树的底层思想都在围绕树打转。把创建、遍历、添加、查找、删除这一整套流程吃透你会突然发现其它树形结构的代码读起来也不那么费劲了。最后再分享一个我个人的小习惯任何树类型写完先在脑内过一遍最坏情况。如果是插入有序序列树退化成链查找效率变成O(n)那这套代码的用途就要打折扣反之如果你知道数据顺序是随机的BST表现就很稳定。这个判断能力比记代码重要得多——代码总会忘但为什么要这么设计想明白了随手就能写出来。本文还有配套的精品资源点击获取