简介这是一份面向数据结构课程设计的完整资源包主题为“二叉树的遍历及树与二叉树的转换”适合高校计算机专业学生完成实验、报告撰写或考前复习时参考。资源内含完整课程设计报告与可运行工程代码实现了前序遍历、中序遍历、后序遍历三种递归遍历方式同时给出普通树与二叉树相互转换的核心算法并借助队列、栈等结构完成层次输出与树形打印。压缩包共28个文件以cpp源文件、h头文件、dsw/dsp工程文件和doc文档为主体另附已编译的exe程序及调试过程中生成的辅助文件整体仅1.32MB便于下载后在Visual Studio中直接打开、编译和运行。目前已有280人学习浏览。通过这份资料读者既能掌握二叉树遍历与转换的代码实现细节也能学习递归函数的设计思路、边界条件检查以及课程设计报告的规范写法对提升数据结构和算法实践能力很有帮助。1. 二叉树遍历与树转换这份课程设计资源到底帮你少踩多少坑课程设计里二叉树遍历与树和二叉树的转换几乎是数据结构方向最常被选中的题目但它远没有表面看起来“背完代码就完事”。很多人递归遍历半天能跑通一进入树与二叉树互转就卡住兄弟链该挂左还是挂右、还原时指针怎么拆、层序建树为什么会越界全靠试错。这份课程设计资源把建树、四种遍历、树转二叉树、二叉树还原树、结果验证做成了一个完整的闭环工程报告里连递归栈帧变化和指针改向的关键步骤都示意清楚。适合正在赶课程设计的同学、答辩前补理论的同学以及代码写完了但对结果心里没底的人。下面按我从零复现这份资源的顺序把理论线和实操坑一起说透。2. 先立理论遍历的递归序、打印时机与层序队列2.1 前中后序遍历的本质递归序与三次访问机会很多同学把前序、中序、后序当成三种独立的算法背一写就混。其实它们共享同一个递归框架每个节点在递归过程中都会被访问三次。第一次是在进入左子树之前第二次是左子树递归返回之后第三次是右子树递归返回之后。前序、中序、后序的唯一区别就是选择在哪一次访问时把节点的值打印出来。def preorder(node): if node is None: return print(node.data, end ) # 第一次访问进入左子树之前 preorder(node.left) preorder(node.right) def inorder(node): if node is None: return inorder(node.left) print(node.data, end ) # 第二次访问左子树返回之后 inorder(node.right) def postorder(node): if node is None: return postorder(node.left) postorder(node.right) print(node.data, end ) # 第三次访问右子树返回之后逻辑说明这三个函数只有 print 语句的位置不同递归结构完全一样。理解“三次访问”比记住口诀有用得多。比如后序输出正好对应“先孩子后根”所以释放整棵树内存时用后序遍历先释放左右子树再释放根节点不会出现悬垂指针。课程设计答辩时老师经常会问为什么析构树要用后序能回答上这一层就说明不是背的代码。参数说明node 是当前节点对象为 None 时是递归出口data 字段存节点值。递归版代码简单但树深超过一千层时容易栈溢出第 5 章会专门讲怎么处理。迭代版前序遍历用显式栈模拟后序可以用两个栈也可以在节点里加访问标记资源代码里两种版本都给了。以一棵小树手动推一遍根节点为 A左孩子 B右孩子 CB 的左孩子为 D。前序输出 A B D C中序输出 D B A C后序输出 D B C A。这个例子必须自己手推而不是只看代码否则答辩现场让你画递归树就慌。要点是前序先根、再左子树、再右子树中序先把左子树全输出再输出根再输出右子树后序先左、再右、最后根。每次遇到子树就用同一套顺序递归套下去。2.2 层序遍历队列里存的是节点不是值层序遍历和前三种遍历思路完全不同。它不递归而是用队列做广度优先从根开始每从队列头部弹出一个节点就把它打印出来再把它的左孩子和右孩子依次放入队列尾部。这样天然按层从左到右输出。from collections import deque def level_order(root): if root is None: return queue deque([root]) while queue: node queue.popleft() print(node.data, end ) if node.left: queue.append(node.left) if node.right: queue.append(node.right)逻辑说明队列入队的必须是节点对象而不是节点值。原因很简单下一个节点要从队头弹出来继续访问它的 left/right 指针如果只存值就丢失了继续下探的路径。这个错误很常见典型表现是层序输出每一层只有第一个节点后面的全丢。参数说明这里用 collections.deque 做队列popleft 是 O(1) 操作如果直接用 list 的 pop(0)每次弹出是 O(n)树一大会立刻变慢。另一个小细节是空孩子判断None 的孩子不要入队否则下一轮 popleft 拿到 None 后会崩在访问 node.left 那行。层序遍历的时间复杂度是 O(n)空间复杂度在完全二叉树最坏情况下是 O(n)因为最宽一层可能有接近 n/2 个节点。如果课程设计要求每层单独换行输出可以改成两层循环先记录当前队列长度 level_size内存循环只处理 level_size 个节点处理完就换行。把这段逻辑和普通层序对比着看就能理解为什么入队数量控制是层序输出格式的关键。2.3 遍历序列与二叉树唯一性转换正确性的判定基础做树与二叉树转换之前先搞清楚一个问题给定遍历序列能不能唯一还原出原二叉树。结论是前序加中序可以唯一还原后序加中序也可以唯一还原但前序加后序不行除非这棵树是满二叉树。这个结论直接决定你后面验证转换结果时用什么方案。为什么前序加中序足够前序序列的第一个元素一定是整棵树的根在中序序列里找到这个根它左边就是左子树的中序序列右边就是右子树的中序序列再回到前序序列数出左子树的节点个数就能把前序序列切成左右两段然后对每段递归重复。整个过程是典型的“切序列”。举个例子前序 ABDEC中序 DBEAC。前序第一个是 A中序里 A 在倒数第二位所以左子树的中序是 DBE右子树的中序是 C前序去掉 A 后是 BDEC前两个 BD 属于左子树最后一个 C 属于右子树。递归下去B 是左子树根D、E 分别是 B 的左右孩子树形就确定了。可用序列能否唯一还原说明前序 中序能中序负责划分左右子树后序 中序能后序最后一个是根前序 后序不能只有根信息分不清左右这个结论在后面第 6 章会直接用于验证树转成二叉树后对原树做先根遍历对二叉树做前序遍历两个序列应当完全一致再用前序加中序还原能验证节点位置没丢。现在先记住结论实操时才能少走弯路。3. 树与二叉树转换左孩子右兄弟的指针改向3.1 为什么要转换普通树缺乏统一的三序结构普通树的存储和遍历比二叉树麻烦得多。一个节点可以有很多孩子孩子之间的顺序如果不约定遍历时先走哪个孩子、走完孩子下一步去哪都没有二叉树那样清晰的左右分支。二叉树的优点是每个节点最多两个分支前中后序天然有定义。左孩子右兄弟表示法就是解决这个问题的任何一个节点的第一个孩子当作左孩子它后面的兄弟按顺序串成右指针链一棵任意度数的树就被改写成标准二叉树形态。这个转换不是为了考试而考。操作系统的进程树、目录树、编译原理里的语法树很多底层实现都用了类似的“第一个子节点加兄弟指针”结构来节约内存。课程设计报告里讲清楚这一层理论部分就能从“背规则”升级成“讲设计动机”这是拉开分数差距的地方。3.2 树转二叉树first_child 变左指针兄弟链变右指针树节点的标准结构通常包含 data、first_child第一个孩子、next_sibling下一个兄弟三个字段。转二叉树的规则只有两条第一个孩子变为左孩子第一个孩子之后的每个兄弟变为前一个兄弟的右孩子。class TreeNode: def __init__(self, data): self.data data self.first_child None # 树的孩子链指向第一个孩子 self.next_sibling None # 树的兄弟链指向下一个兄弟 class BSTNode: def __init__(self, data): self.data data self.left None self.right None def tree_to_binary(node): if node is None: return None bnode BSTNode(node.data) if node.first_child: bnode.left tree_to_binary(node.first_child) if node.next_sibling: bnode.right tree_to_binary(node.next_sibling) return bnode逻辑说明这个函数递归的条件是“孩子走左指针、兄弟走右指针”。以树的根节点为例根没有兄弟所以根的右指针为空根的第一个孩子递归转出的节点作为左孩子挂上而这个孩子在原树里的兄弟会通过它自己的右指针一路挂成链。这正是左孩子右兄弟的形态二叉树里每个节点的右子树本质上不再是“亲儿子”而是“下一个兄弟及其后代”。理解这一点还原树时才不会把右子树当成普通右孩子去处理。参数说明TreeNode 和 BSTNode 是两套结构转换时新建节点原树数据完全保留这样可以在一个程序里同时展示原树和二叉树。如果你的课程设计允许原地转换可以只保留一套节点结构把 first_child 改名为 left、next_sibling 改名为 right代码更省但演示效果不如双结构。报告里建议用双结构因为可以分别打印两种树的遍历结果做对比。举一个例子验证。假设原树根 A孩子 B、C、D其中 B 有孩子 E。树结构A.first_child BB.next_sibling CC.next_sibling DB.first_child E。转换后A 的左孩子是 BB 的右孩子是 CC 的右孩子是 DB 的左孩子是 E。原树中 B、C、D 是兄弟关系转换后变成沿右指针的链这是最核心的形状变化。3.3 二叉树还原树沿着右链拆回兄弟序列还原是转换的逆过程。逆规则是二叉树节点的左孩子还原为原树的第一个孩子沿左孩子右指针链走每一跳都是一个兄弟找到所有兄弟后把它们串成原树的 next_sibling 链。def binary_to_tree(bnode): if bnode is None: return None tnode TreeNode(bnode.data) if bnode.left: child binary_to_tree(bnode.left) tnode.first_child child cur bnode.left.right # 左孩子的右链上都是兄弟 while cur: sibling binary_to_tree(cur) child.next_sibling sibling child sibling cur cur.right return tnode逻辑说明binary_to_tree 每层只处理 bnode.left右指针链不在这里递归处理而是在 while 循环中由调用者逐跳推进。这是还原过程中最容易写错的地方如果递归函数内部又对 bnode.right 做递归兄弟链就会被处理两次结果出现重复节点。上面这段代码把“拆孩子”和“拆兄弟”分成两个层面left 进递归right 进循环各管各的结果才正确。参数说明child 变量在循环里不断更新成新还原出的兄弟节点保证 next_sibling 从第一个兄弟开始依次串到最后一个。cur 从 bnode.left.right 开始沿右指针走直到 None 结束这正好对应转换时“兄弟链变成右链”的反向操作。验证还原正确性的方法很简单把还原后的树再做一次 tree_to_binary应得到和原二叉树相同的结构或者对原树做先根遍历输出对比二叉树还原前的先序输出序列。3.4 森林与二叉树把多棵树根串成右链森林是多棵树的集合转二叉树时先把每棵树各自按左孩子右兄弟规则转成二叉树然后把第一棵树的根作为整体根第二棵树的根作为第一棵树根的右孩子第三棵以后依次接在前一棵根的右链末尾。效果上森林的所有根节点通过右指针链成一串。二叉树转森林则相反先从根沿右指针切割出多棵二叉树子树每棵子树再独立还原成普通树。这里有一个容易混淆的边界普通树转二叉树时根节点没有兄弟所以根的右指针为空但森林转二叉树后根的右指针是有内容的指向的是下一棵树的根。答辩时老师会拿这一点区分你到底是“树转二叉树”还是“森林转二叉树”。课程设计报告里如果没有单独展示森林转换建议在原理部分把这句话写进去避免被问倒。4. 课程设计代码落地建树、遍历、转换一条龙4.1 节点结构与输入格式先定数据格式再写代码课程设计的第一步不是写遍历而是定输入格式。很多同学一上来就手工在代码里创建节点树写死之后换个数据就得改代码演示效果很差。建议用两种输入格式之一按层序输入带空节点的序列或者按前序输入并约定用 # 表示空节点。前序格式最直观遇到 # 表示空子树和递归建树过程一一对应。还有一种括号嵌套格式像 A(B(D,E),C(F,G)) 这样虽然人能看懂但解析代码要额外写状态机课程设计没必要。层序输入适合完全二叉树普通二叉树的中途空位置会用 # 占位但建树时下标计算容易被 2i1 公式误导。所以下面以“前序序列加 # 占位”为主线这也是资源代码实际采用的方案。def build_from_preorder(data_list, idx): if idx[0] len(data_list): return None val data_list[idx[0]] idx[0] 1 if val #: return None node TreeNode(val) node.left build_from_preorder(data_list, idx) node.right build_from_preorder(data_list, idx) return node逻辑说明前序序列建树的关键是把 idx 放在一个可变容器里传递而不是直接用返回值更新下标否则递归返回时下标会丢失。每次先取一个值遇到 # 就返回 None否则创建节点先递归建左子树再递归建右子树。这个顺序和前序遍历的顺序完全一致所以很好记。参数说明data_list 是从字符串 split 出的列表idx 是长度为 1 的列表里面存当前读取位置。这里用 idx[0] 而不是直接传 int是因为普通整数是值传递递归中修改了也不影响外层用单元素列表就能跨递归共享下标。C 语言版里对应的是 int* idx 指针参数道理相同报告中可以对照着写。4.2 建树测试用例与遍历输出拿一棵三层树跑断言课程设计最忌讳测试用例太简单。只用根左右三个节点的树遍历和转换的代码全对也不一定能暴露问题。建议用一棵包含至少三层、每层节点数不等的树至少包含一个没有左孩子的节点、一个没有右孩子的节点、一个既有左右孩子又有兄弟的节点。这样四种遍历和转换函数的每个分支都会被走到。下面给出一棵树的完整测试数据用前序序列表示A B D # # E # # C F # # G # #。它对应的二叉树是根 A左孩子 B右孩子 CB 的左孩子 D、右孩子 EC 的左孩子 F、右孩子 G。对这棵树运行四种遍历预期输出如下遍历方式预期输出前序A B D E C F G中序D B E A F C G后序D E B F G C A层序A B C D E F G把这些输出做成自动化断言比肉眼对比靠谱得多。main 函数里把每个遍历结果拼成字符串直接和预期字符串比较不一致就打印错误节点。课程设计报告里放一张这样的对照表答辩老师扫一眼就知道你做过系统验证。建树时还有一个常见需求输入的不一定是单字符。如果节点编号是两位数以上split 之后每个元素是完整字符串不再按字符切分上面这份代码天然支持。这是前序序列加空格分隔的另一个好处节点值里也不会有歧义。4.3 主流程组织菜单式演示与三次序列对照演示程序建议做成菜单循环输入 1 执行前序遍历输入 2 执行中序遍历输入 3 执行后序遍历输入 4 执行层序遍历输入 5 把当前树转为二叉树并输出转换前、转换后的遍历结果输入 6 把二叉树还原回树输入 0 退出。这样演示时每步都有明确输出老师和评委能跟着操作走不会一头雾水。主流程里有一个小细节转换前保留原树转换后新建一棵二叉树输出完对比结果后保留原树以便后续操作。如果直接把原树改成二叉树形态想再演示还原就没有素材了。报告里主程序的逻辑可以这样组织读入前序序列建树打印当前树的前序和中序序列执行 tree_to_binary打印转换后二叉树的前序和中序再执行 binary_to_tree打印还原树的前序和中序。三组序列一对比每一步是否正确一目了然。转换结果的验证有三层手段。第一层是节点计数转换前后节点数必须相等写一个 count_nodes 函数转换前、转换后、还原后各调用一次数字对不上就说明丢了节点。第二层是遍历序列对比原树的先根遍历序列应等于转换后二叉树的前序遍历序列还原后再次对比。第三层是结构还原把二叉树再转回树得到的新树再做一次先根遍历得到的序列应该和最初完全一致。这三层都过才能说转换闭环是正确的。5. 避坑指南二叉树课程设计最常见的五个翻车点5.1 空指针访问在访问 left 之前先问自己节点是不是 None现象运行层序遍历或转换函数时程序报 AttributeError提示 NoneType 对象没有 left 属性换成 C 语言版就是段错误报错位置还经常不稳定。原因访问节点孩子之前没有判断节点是否为 None。最常见的三个位置层序遍历入队前没检查左右孩子是否为空递归建树时下标越界后返回 None调用方继续访问 None.left二叉树转树函数里 bnode.left.right 这一行如果 bnode.left 本身为空直接崩。解决所有访问 left/right 的语句前面一律先判空。层序遍历入队前对左右孩子判空树转二叉树时先判断 first_child 是否为 None二叉树转树时写 bnode.left.right 之前先确认 bnode.left 不是 None。宁可多写一个 if也不要赌测试数据一定带全孩子。5.2 层序建树的下标问题数组公式只对完全二叉树成立现象用数组存二叉树父亲下标 i左孩子 2i1右孩子 2i2但建出来的树节点错位右孩子跑到左孩子下面去了。原因这个公式只对完全二叉树成立。普通二叉树用数组连续存储时中间空位会导致下标关系失真很多同学直接套公式结果节点挂错位置却不自知。解决普通二叉树要么用前序序列配合 # 建树要么用队列按层序建树。队列建树的规则是读一个值创建节点从队列头部取出父节点先挂左孩子再挂右孩子挂满两个孩子后父节点出队。不要把 2i1 公式用在稀疏二叉树上除非你明确知道自己建的是完全二叉树。5.3 转换后遍历结果对不上兄弟链挂错位置了现象树转二叉树后对二叉树做前序遍历得到的序列和原树先根遍历结果不一致或者节点数对了但顺序完全乱。原因最常见的错误是兄弟链挂到左子树上去了。左孩子右兄弟的规则里兄弟链必须走右指针如果把 next_sibling 也递归进 left第一个孩子后面的所有兄弟都会堆在左子树上二叉树结构错乱。解决写转换函数前先画一棵三层带兄弟的树把每个节点转换后的指针走向标在草图上。比如根 A 有孩子 B、CB 有孩子 E。转换后必须达到A.left BB.right CB.left E。如果代码输出里 B 的右孩子不是 C 而是 E说明递归顺序反了。检查顺序是先处理第一个孩子再沿着第一个孩子的兄弟链逐个处理两步不能混。5.4 递归栈溢出深层斜树直接把程序跑崩现象代码在测试数据上一切正常一换大数据就栈溢出Python 报 RecursionErrorC 程序直接闪退。原因递归遍历和递归建树都依赖系统调用栈默认栈空间有限。极端情况下构造一棵深度一万层的斜树每次递归都压栈很快触顶。解决课程设计正文用递归完全没问题但应该知道迭代写法作为兜底。前序、中序用显式栈模拟后序可以用两个栈层序本身就是队列。如果报告里写一句“递归深度受栈空间限制实际工程场景会改用迭代版”这会是答辩的加分项。测试时如果不想构造大斜树可以限制递归深度并给出提示至少不会静默崩溃。5.5 答辩必问为什么前序加后序不能唯一确定二叉树现象答辩时老师问“只有前序和后序遍历结果能不能还原出唯一二叉树”一时答不上来。原因前序和后序都只含“根的位置”信息没有子树划分依据。比如一棵只有根和左孩子的树前序 AB、后序 BA根和右孩子也是前序 AB、后序 BA。两种完全不同的树得到相同序列所以不唯一。解决准备一个反例写在报告里。一棵树的根只有一个孩子时你无法从这个孩子在前序里紧跟根判断它到底在左还是在右。用反例回答比背十遍定义都有说服力。这也能解释为什么第 6 章的还原算法必须同时拿到前序和中序两个序列。6. 进阶验证用前序加中序反推树形闭环校验转换正确性前面讲转换闭环验证时提到三种手段这一章给其中最关键的一种用前序加中序序列反推二叉树然后把反推出来的树和转换得到的二叉树逐层对比。当课程设计做完树与二叉树互转后这是检验正确性的最强工具答辩时也能作为加分演示。def rebuild(preorder, inorder): if not preorder or not inorder: return None root_val preorder[0] root BSTNode(root_val) idx inorder.index(root_val) # 在中序序列中定位根的位置 left_size idx # 左子树节点个数 root.left rebuild(preorder[1:1 left_size], inorder[:idx]) root.right rebuild(preorder[1 left_size:], inorder[idx 1:]) return root逻辑说明每次取前序序列第一个元素作为当前根在中序序列里找到这个根它左边那一段就是左子树的中序序列右边那一段就是右子树的中序序列左子树节点个数等于中序里根的左边元素个数用这个数把前序剩余部分切成左右两段然后对两段分别递归。整个过程是一个“先定根、再切序列、再递归”的过程和前序加中序还原唯一二叉树的数学结论完全对应。参数说明preorder 和 inorder 传入的是列表切片Python 切片会创建新列表课程设计验证用没问题。如果树很大想优化就把中序值和位置存进哈希表用 index 的 O(n) 查找变成 O(1)递归整体复杂度从 O(n²) 降到 O(n)。资源的代码里给的是基础版本报告里可以提一句优化方向显得对复杂度有意识。具体验证流程是对原树做先根遍历得到序列 P对原树做后根遍历得到序列 T用 P 和 T 的第一段构造序列调用 rebuild还原出一棵二叉树再把转换函数 tree_to_binary 输出的二叉树和 rebuild 出的二叉树做一次前序遍历对比序列一致即通过。注意这里不能直接用前序和后序调 rebuild因为两者不能唯一还原必须用前序加中序。原树的中序可以通过“先孩子后根”的遍历得到也就是把每个节点的孩子按从左到右顺序递归遍历后输出当前节点这恰好对应二叉树的中序序列。我最早写这份验证时偷懒只对比层序结果有一棵兄弟链挂反的树层序看起来完全正常直到用前序加中序还原才暴露出问题。从那以后每次做树相关的转换我强制走一遍“转换、还原、再还原”的闭环序列对比这一招救过我好几次。希望帮到你。本文还有配套的精品资源点击获取