C++手写多叉树：从节点设计到遍历与内存管理实战

简介一个C多叉树结构示例工程特别适合正在学习数据结构、需要对非线性结构做动手练习的C开发者。资源核心是tree.h头文件它定义了节点类以及固定容量的子节点指针数组并围绕多叉树提供插入、删除、前序/后序深度优先遍历和广度优先遍历等接口Tree_test.cpp则是配套的可运行测试程序用于验证这些操作是否达到预期。压缩包共8个文件h与cpp构成完整实现和测试sln与vcproj为Visual Studio工程配置txt文件包含相关说明与算法文本整体仅6KB麻雀虽小但结构清晰。目前已有1222人学习适合用来快速理清多叉树与二叉树在节点结构、遍历逻辑上的区别也可作为建模文件系统目录、搜索树等场景的参考实现。通过阅读源码并运行测试能够直接复用其中的节点管理和遍历函数同时掌握固定容量子节点处理、递归遍历及借助栈/队列完成深度优先与广度优先搜索的关键写法。 早些年我写文件索引工具目录结构天然就是一棵多叉树。那会儿我刚写完二叉树的练习下意识想把代码改成 left/right 两个指针的版本结果一动手就卡住了一个目录下面可能挂着十个子目录左孩子右孩子根本塞不下。后来才意识到课本里“二叉树优先”的训练和工程里真正普遍存在的 N 叉树之间隔着一条很深的断层。这篇文章就把 C 手写多叉树的完整思路、代码实现和踩坑过程拉开讲一遍。无论你是准备面试但只能手写二叉树的候选人还是一直要和 XML/JSON 解析、目录遍历、UI 控件层级打交道的 C 开发者这篇文章都能帮你在工程场景里把多叉树真正用起来。1. 冷知识业务系统里到处都是多叉树却很少有人会手写1.1 多叉树是什么一个节点不再被“两个孩子”束缚多叉树也叫 N 叉树N-ary Tree定义和二叉树一脉相承每个节点可以有零到多个子节点而不是像二叉树那样最多只能有两个。这里的 N 指的是“这个树里任意节点最多拥有的孩子数量”比如四叉树、八叉树就是 N 固定的多叉树如果 N 不固定那每个节点的孩子数量完全由业务决定。学习数据结构时大家总优先讲二叉树因为二叉树结构简单、便于教学和推导平衡性质。可真实的业务系统不会为了配合教材而选结构。文件目录、公司组织架构、HTML 的 DOM 树、JSON 嵌套对象天然都是非线性的多叉关系。强行用二叉树去模拟代码会变得非常别扭还得反复维护一堆空指针。从性能角度看多叉树的优势同样明显。树的高度决定了从根到叶子要走多少步孩子越多、分支越宽树就越矮。同样是 100 万个节点二叉树最差能退化成链表退成 100 万层而一个宽泛的多叉树可能只要几层就能装下。1.2 哪些场景属于隐藏的多叉树很多你天天碰的东西底层就是多叉树只是它们包着各种业务外壳文件系统目录树根目录下面有多个子目录子目录下面还有多个子目录和文件。Windows 上敲tree命令打出来的就是一棵标准多叉树。公司组织架构CEO 下面挂 CTO、CFO、COOCTO 下面挂技术部、产品部、项目部层层展开典型的乱序多叉树。XML/HTML DOM标签可以无限嵌套每个标签节点可以有任意多个兄弟标签和子标签解析完就是一个庞大的多叉树。编译器抽象语法树AST一条if语句下面挂着条件表达式、then 分支、else 分支每个分支又可能挂更复杂的子结构。Trie 前缀树每个节点保存一个字符配合一堆指向下一个字符的指针本质上就是一个孩子数量不固定的多叉树常用于搜索引擎关键词提示和敏感词过滤。B 树数据库索引的底层实现每个页节点可以存多个 key 和多个孩子指针算是一种平衡的宽多叉树。这些场景的共同点是节点之间的父子关系天然存在孩子数量不稳定需要一个能动态扩展的数据结构来承载。这就是为什么工程经验丰富的开发者哪怕不需要天天写多叉树也一定要知道怎么设计它的存储和遍历。2. 先定存储方案节点里放 vector 还是裸指针数组2.1 最直觉的节点结构data children多叉树节点的核心是什么一块业务数据加一个存放孩子的容器。#include vector template typename T struct TreeNode { T val; std::vectorTreeNodeT* children; explicit TreeNode(const T v) : val(v) {} };children用std::vector是最常见的选择。原因很简单孩子们的数量是动态的vector 可以自动扩容遍历时内存连续缓存友好删除尾部孩子是 O(1)删除中间孩子虽然要移动元素但孩子数量一般不会特别大代价可以接受。不要一上来就想着用定长数组。定长数组适合那种孩子数量非常固定的场景比如四叉树可以用TreeNode* children[4]八叉树用TreeNode* children[8]。如果孩子数量不固定却硬用定长数组要么浪费大量内存要么就得维护一个容量阈值外加扩容逻辑平白给自己添麻烦。2.2 孩子指针用什么管理裸指针、unique_ptr 还是 shared_ptr面试和工程里最常纠结的问题是孩子指针到底用裸指针还是智能指针。裸指针的好处是写法直白理解成本低。但代价是你要手动管理整棵树的释放稍一疏忽就会内存泄漏或者出现 double free。用std::unique_ptr是工程上更稳的选择。树是一种典型的独占所有权结构每个孩子节点只能有一个父节点父节点销毁时它应该带着所有孩子一起销毁。这种语义和unique_ptr完美匹配。#include memory #include vector template typename T struct TreeNode { T val; std::vectorstd::unique_ptrTreeNodeT children; explicit TreeNode(const T v) : val(v) {} };有人可能觉得shared_ptr更省心其实在树结构里不太合适。一是树本身是独占关系没必要引入共享所有权二是如果反向加了 parent 指针再配合 shared_ptr 一起用很容易形成循环引用反而导致内存泄漏三是 shared_ptr 的引用计数是原子操作频繁拷贝、析构会带来额外性能开销。所以我的建议是工程代码默认unique_ptr教学演示为了看得清楚才用裸指针。2.3 要不要给节点加 parent 指针这是一个经常被忽略的决策点。加了 parent 指针从任意节点向上回溯就很快比如找祖先节点、算节点深度、实现兄弟节点遍历都能直接用。但代价也很明显首先每个节点多出一个指针内存占用上升其次插入、删除时要同步维护 parent 字段漏掉一处就会留下悬垂指针。更重要的是如果你已经选了 unique_ptr 管理孩子再往节点里塞一个裸指针parent指向父对象除非你自己非常清楚这个裸指针不拥有所有权否则后面维护代码的人很容易误用成shared_ptr做出危险操作。我的经验是如果只是构建后做遍历、查找不需要加 parent如果业务里频繁要求从某个子节点反查路径或者要反复比较两个节点的祖先关系那就加建议把 parent 设置为不可拥有所有权的裸指针并在注释里写清楚。3. 手写四件套构建、遍历、查找、释放3.1 构建树从 addChild 开始先看一个裸指针版本逻辑最清晰适合面试时快速写出框架#include iostream #include vector template typename T struct TreeNode { T val; std::vectorTreeNodeT* children; explicit TreeNode(const T v) : val(v) {} }; template typename T TreeNodeT* addChild(TreeNodeT* parent, const T val) { auto* node new TreeNodeT(val); parent-children.push_back(node); return node; }构建一棵树int main() { auto* root new TreeNodeint(1); auto* n2 addChild(root, 2); auto* n3 addChild(root, 3); auto* n4 addChild(root, 4); auto* n5 addChild(n2, 5); auto* n6 addChild(n2, 6); auto* n7 addChild(n4, 7); // 此时树结构 // 1 // ├── 2 // │ ├── 5 // │ └── 6 // ├── 3 // └── 4 // └── 7 return 0; }addChild返回新孩子的指针这样可以继续往这个孩子下面挂孙节点。这个设计很实用因为它允许调用方在不知道整棵树结构的情况下依次把树搭起来。这里有一个容易漏的检查如果传入的parent是空指针函数不能继续做push_back。工程上应该在函数开头加空指针校验或者直接用断言。别觉得这种细节不重要真实的 DOM 解析器和文件系统遍历里一个空指针可能来自解析失败或者上一个操作的异常不挡住就会直接崩掉。3.2 深度优先遍历与广度优先遍历深度优先遍历递归写起来很自然先序就是“先打印当前节点再依次遍历所有孩子”template typename T void dfsPreOrder(TreeNodeT* node) { if (!node) return; std::cout node-val ; for (auto* child : node-children) { dfsPreOrder(child); } }后序就是“先遍历所有孩子再打印当前节点”。后序在释放树内存时格外重要因为必须先递归释放所有孩子最后才能 delete 当前节点顺序反了会导致孩子节点变成悬垂对象。广度优先遍历用队列实现也叫层序遍历#include queue template typename T void bfsOrder(TreeNodeT* root) { if (!root) return; std::queueTreeNodeT* q; q.push(root); while (!q.empty()) { auto* cur q.front(); q.pop(); std::cout cur-val ; for (auto* child : cur-children) { q.push(child); } } }两种遍历各有各的用途。深度优先适合做序列化、复制树、计算子树属性广度优先适合找最短路径、按层输出、统计某一层的节点数量。3.3 查找节点DFS 和 BFS 怎么选查找某个值对应的节点深度优先和广度优先都能实现。递归版本的 DFS 查找非常简洁template typename T TreeNodeT* findNode(TreeNodeT* node, const T target) { if (!node) return nullptr; if (node-val target) return node; for (auto* child : node-children) { auto* result findNode(child, target); if (result) return result; } return nullptr; }如果不在乎找到的是哪一条路径上的节点只想“快速确认存不存在”DFS 通常更合适因为它不需要额外开一个队列空间开销更小。如果明确知道目标一定在浅层或者想找“从根到目标的最小深度”那就用 BFS按层走下去第一次碰到目标时一定是最短路径。查找函数返回的是裸指针这里要注意一个悬垂问题如果树在查找后被修改、删除了部分节点这个返回的指针可能失效。所以工程上最好约定清楚查找返回的指针只在树结构不变的前提下使用如果你在遍历的同时改树很容易踩到后文会说的迭代器失效问题。3.4 删除与释放正确销毁整棵树的姿势裸指针版本手动释放整棵树必须先孩子后自己template typename T void destroyTree(TreeNodeT* node) { if (!node) return; for (auto* child : node-children) { destroyTree(child); } delete node; }递归调用的顺序不能写反。假如你先 delete 了当前节点然后才去递归孩子节点那递归访问到的就是一块已经释放的内存程序直接未定义行为。如果你在children里用的是unique_ptr那么析构函数都不需要手写。vector 析构时会逐个调用每个元素也就是 unique_ptr的析构进而递归销毁整棵子树。这就是智能指针在树结构里最直观的价值代码量少而且不会漏删。不过删除单个子节点时要注意只delete目标节点还不够还需要把它从父节点的children容器里移除否则父节点还握着一个指向已释放内存的悬垂指针下次遍历就会崩。4. 踩坑实录递归深度、内存泄漏与迭代器失效4.1 递归爆栈十万层树直接崩给谁看递归写起来舒服但有个致命隐患树的高度一旦很深递归调用栈会被撑爆。比如一个 JSON 文件嵌套层次很深解析出来的树可能几千上万层或者一个退化成链表的多叉树每个节点只有一个孩子深度等于节点总数十万个节点递归遍历程序直接栈溢出运行时报错还不容易复现。解决方式是把递归改成显式栈的迭代版本。先序遍历的迭代写法如下#include stack template typename T void dfsPreOrderIterative(TreeNodeT* root) { if (!root) return; std::stackTreeNodeT* st; st.push(root); while (!st.empty()) { auto* cur st.top(); st.pop(); std::cout cur-val ; // 逆序压栈保证遍历顺序和递归先序一致 for (auto it cur-children.rbegin(); it ! cur-children.rend(); it) { st.push(*it); } } }这里最容易出错的是压栈顺序。栈是先进后出如果按顺序把children[0]、children[1]、children[2]压栈弹出来的顺序就是children[2]、children[1]、children[0]。为了保持和递归一致的先序顺序必须逆序压栈。这个细节面试时很加分至少说明你真的理解栈的行为。4.2 裸指针一时爽析构忘写火葬场裸指针版本的树最经典的事故是浅拷贝带来的 double free。看下面这段代码TreeNodeint* root buildTree(); // 假设这棵树有 100 个节点 TreeNodeint* copy root; // 很多人以为这是复制树其实只复制了根指针如果后续有一段逻辑对 root 调用了destroyTree然后又在另一个分支对 copy 也调用destroyTree同一个节点就被 delete 了两次程序崩溃。正确做法有三种只允许显式深拷贝重新递归创建所有节点直接禁用拷贝C 里用 delete声明拷贝构造函数和拷贝赋值运算符把节点容器换成unique_ptr从根上消除裸指针共享的可能。我见过不少自称“写过树”的候选人写不好这层安全边界。所以做项目时我强烈建议直接使用unique_ptr把所有权关系交给编译器检查而不是靠人脑记忆。4.3 遍历时改动 children 导致的迭代器失效std::vector有一个很隐蔽的坑在遍历children的过程中如果调用了erase删除元素会导致当前迭代器失效。很多人在删除符合条件的子节点时顺手就写了这样的代码for (auto it parent-children.begin(); it ! parent-children.end(); it) { if (shouldDelete(*it)) { delete *it; parent-children.erase(it); // it 已经失效再 it 是未定义行为 } }这段代码是错误的。erase之后it指向的位置已经没有意义继续it是未定义行为。正确做法是利用erase的返回值它会返回被删除元素的下一个迭代器for (auto it parent-children.begin(); it ! parent-children.end();) { if (shouldDelete(*it)) { delete *it; it parent-children.erase(it); } else { it; } }另一种稳妥办法是先把要删除的节点指针收集到一个临时数组里循环结束后统一 delete再统一清空容器。好处是删除逻辑和遍历逻辑分离不容易出错。4.4 内存碎片与大量小对象的性能问题每个节点都通过new单独在堆上分配节点数量一旦上百万级malloc 的调用次数和内存碎片问题就会显现。节点本身占的内存很小但每次分配都有额外头部开销内存利用率下降CPU 缓存命中率也不高。性能优化的常见方向有两个。一是用内存池一次性申请一大块连续内存然后从池里分配节点对象释放时统一回池二是用连续数组存储节点节点间通过下标索引而不是指针互相关联这样数据局部性强遍历时对缓存更友好。但我不建议在新手阶段一上来就做这种优化。先确保逻辑正确、封装合理然后通过性能剖析工具看看瓶颈到底是不是节点分配。多数业务场景下树本身的遍历算法复杂度才是主要矛盾。5. 面试与工程实战中的多叉树变形LCRS 与资源管理5.1 左孩子右兄弟表示法用两个指针塞下任意多个孩子如果内存非常受限或者希望复用一些二叉树算法可以把多叉树用左孩子右兄弟Left-Child Right-Sibling简称 LCRS的方式存储。每个节点只有两个指针template typename T struct LCRSNode { T data; LCRSNode* firstChild; // 指向第一个孩子 LCRSNode* nextSibling; // 指向下一个兄弟 explicit LCRSNode(const T v) : data(v), firstChild(nullptr), nextSibling(nullptr) {} };转换思路是把原来children数组里的第一个孩子拿出来作为firstChild剩下的孩子依次用nextSibling串成一条链表。比如一个节点原本有 3 个孩子 A、B、CLCRS 下就是firstChild指向 AA 的nextSibling指向 BB 的nextSibling指向 C。这种表示的优点是一个节点只占用两个指针内存占用和二叉树完全一样很多二叉树的递归思路可以直接迁移过来。缺点就是找某个子节点得沿着兄弟链表遍历时间复杂度从 O(1) 变成 O(k)。如果孩子数量不大、内存优先的嵌入式场景LCRS 是很实用的方案。5.2 B 树为什么也被归到多叉树体系数据库索引里常见的 B 树从“每个节点有多个孩子”这个意义上看也属于多叉平衡树。但它和普通业务多叉树不一样的地方在于每个内部节点存的不只是数据还有一组有序 key 和一组指向子节点的指针查询时通过二分定位去决定走哪个孩子分支。普通多叉树通常不限制每个节点的孩子数量上限B 树则要求每个节点保持在某个最小和最大孩子数之间超过就分裂、低于就合并从而保证树高始终平稳。面试时如果提起你懂 B 树的思想不要只背“三层可存千万数据”这种话术最好能解释清楚它为什么能减少磁盘 I/O因为一次读一个磁盘页能拿到很多 key一次比较就能排除一大半路径。5.3 工程化封装断舍离拷贝拥抱移动语义工程上写多叉树强烈建议包一层 RAII 管理类把裸指针和释放逻辑收起来。template typename T class NTree { public: NTree() default; ~NTree() { destroyTree(root_); } // 禁止拷贝 NTree(const NTree) delete; NTree operator(const NTree) delete; // 允许移动 NTree(NTree other) noexcept : root_(other.root_) { other.root_ nullptr; } NTree operator(NTree other) noexcept { if (this ! other) { destroyTree(root_); root_ other.root_; other.root_ nullptr; } return *this; } private: TreeNodeT* root_ nullptr; };这里最关键的设计是拷贝构造和拷贝赋值直接删除因为对一棵大树的深拷贝代价很高而且默认的浅拷贝会引发双重释放。移动语义则允许我们用很小的开销转移一棵树和标准库容器的使用习惯保持一致。如果你确实需要拷贝一棵树就明写一个cloneTree递归函数复制所有节点数据而不要依赖默认拷贝。明确表达意图的代码比隐式触发的浅拷贝安全得多。5.4 一道典型面试题的完整推导N 叉树最大深度面试八股里二叉树最大深度几乎成了固定题目但 N 叉树版本的思考更有区分度。递归定义很简单空树深度为 0否则深度等于所有子树最大深度加 1。#include algorithm template typename T int maxDepth(TreeNodeT* node) { if (!node) return 0; int depth 0; for (auto* child : node-children) { depth std::max(depth, maxDepth(child)); } return depth 1; }迭代版本可以用 BFS 层序遍历每走一层深度加一template typename T int maxDepthIterative(TreeNodeT* root) { if (!root) return 0; std::queueTreeNodeT* q; q.push(root); int depth 0; while (!q.empty()) { int levelSize q.size(); depth; while (levelSize--) { auto* cur q.front(); q.pop(); for (auto* child : cur-children) { q.push(child); } } } return depth; }递归版本时间复杂度 O(n)空间复杂度取决于树高最坏情况下退化成链表就是 O(n)BFS 版本空间复杂度取决于树的最大宽度。两者各有优劣面试时最好把这两种方案都说出来展示你对递归和迭代两种思路的把握程度。从我个人经验来说多叉树的难点从来不是定义本身而是三个地方容器的选择、内存所有权、遍历过程中的结构修改。只要把这三件事想清楚无论是写编译器 AST、做文件扫描还是准备面试题都能少踩很多坑。最后分享一个很实用的调试技巧写完树之后先别急着看遍历输出写一个带缩进的递归打印函数把整个树形结构按层级直观打出来检查父子关系对不对效率会高很多。template typename T void printTree(TreeNodeT* node, int depth 0) { if (!node) return; for (int i 0; i depth; i) { std::cout ; } std::cout node-val std::endl; for (auto* child : node-children) { printTree(child, depth 1); } }这套组合拳打下来不管是学习还是面试多叉树都不会再是那种“见过但没写过”的结构了。本文还有配套的精品资源点击获取