简介这是一份面向数据结构课程设计的实践资料主题为二叉树的遍历及树与二叉树的转换适合高校学生在完成课程设计报告、算法实现或期末项目时参考。压缩包共收录28个文件以h头文件、cpp源文件、exe可执行程序和doc课程设计报告为核心另含Visual C工程配置文件dsw/dsp/opt等与调试辅助文件整体仅1.32MB。代码实现了二叉树的前序、中序、后序遍历并完成普通树与二叉树的递归转换支持按树形结构打印输出便于直观观察遍历与转换结果。doc报告涵盖问题分析、结构设计、算法描述与测试过程源码可直接编译运行或二次修改适合快速理解递归、队列、栈等核心知识。已有280人学习下载对巩固数据结构基础、提升编程调试能力很有帮助。1. 二叉树的遍历及树与二叉树的转换课程设计到底在考什么当数据结构课程设计把“二叉树的遍历及树与二叉树的转换”这个题目发下来时很多同学的直觉是“这题我熟三个递归函数就完事了”。真正动起手来才发现这个题目考的不是背代码而是把递归、栈、队列、结构映射这几块知识揉在一起做出一套能跑、能演示、能接住追问的程序。它解决的核心问题是两个树这种非线性结构如何在计算机里被线性地访问不同形态的树也就是普通多叉树或森林如何统一用二叉树的存储方式去表达。适合正在做课程设计、准备期末上机、或者想把“看懂”变成“写得出”的读者。下面按我实际带课程设计的顺序把这条路上的关键点过一遍。2. 四种遍历的递归实现先序、中序、后序与层次2.1 节点结构定义与三个递归函数课程设计的第一步是把存储结构定下来。C 语言里二叉树节点通常用左右孩子指针这是最直观、也最容易配合后续“树转二叉树”写法的结构typedef struct BiTNode { char data; // 节点值课程设计里常用字符也可改 int struct BiTNode *lchild; // 左孩子指针 struct BiTNode *rchild; // 右孩子指针 } BiTNode, *BiTree;逻辑说明这个节点只有两个指针域这正是“二叉树”二字的来源。后续所有遍历和转换代码都建立在这两个字段的顺序上lchild 在前、rchild 在后是约定俗成不要中途交换字段位置否则你写别的函数时会绕晕。参数说明data 用 char 是为了打印方便如果题目要求统计节点权值或做表达式求值把 data 换成 int 或 double然后同步改 printf 的格式符和转换函数里的赋值语句。三个深度优先遍历的递归写法是所有后续代码的地基// 先序遍历根 - 左 - 右 void preOrder(BiTree T) { if (T NULL) return; printf(%c , T-data); preOrder(T-lchild); preOrder(T-rchild); } // 中序遍历左 - 根 - 右 void inOrder(BiTree T) { if (T NULL) return; inOrder(T-lchild); printf(%c , T-data); inOrder(T-rchild); } // 后序遍历左 - 右 - 根 void postOrder(BiTree T) { if (T NULL) return; postOrder(T-lchild); postOrder(T-rchild); printf(%c , T-data); }逻辑说明三个函数结构一模一样区别只有 printf 那一行放在哪个位置。遇到空指针就返回这是唯一的递归出口也是整段代码不越界的关键。每个节点恰好被访问一次时间复杂度和节点数成正比这是遍历最基本的性能结论。参数说明三个函数都只接收根节点指针 T对同一个树调用三次会得到三条不同顺序的序列。课程设计里如果要求“统计叶子数”或“求树高”不要改这三个函数而是另写一个 visit 回调函数在 printf 的位置调用它这样遍历骨架可以复用。2.2 三条序列各自的特点与用途先序序列的第一个节点一定是整棵树的根。这个性质可以用来快速定位根但仅凭先序序列无法唯一确定一棵二叉树因为左子树和右子树的边界切分点你不知道。中序序列则有另一个关键性质一旦知道根节点是谁根左边全是左子树节点根右边全是右子树节点。这两个性质叠加起来就是后面第 6 章“用先序中序重建二叉树”的数学基础也是答辩时老师最爱追问的一个点“给你一个先序序列能不能唯一确定二叉树”答案是不能必须再给一个中序或后序序列。后序序列在表达式树里最常用表达式树做后序遍历得到的就是后缀表达式编译原理里四则运算的中间代码生成、计算器的逆波兰式实现都是吃这碗饭。层序遍历则对应广度优先搜索用来按层打印树、求树的宽度、判断完全二叉树。遍历方式序列第一个节点序列最后一个节点典型应用场景先序根节点最右下的节点结构复制、表达式前缀中序最左下节点最右下节点表达式中缀、BST 升序输出后序最左下节点根节点表达式后缀、目录空间统计层序根节点最底层最右节点按层打印、完全二叉树判断这张表建议你在课程设计报告里画出来它能把四种遍历的区别讲清楚省一段文字描述。2.3 递归的边界空树和单节点树递归写法短但边界条件写错会在空树上直接翻车。空树调用 preOrder(NULL) 应当什么都不打印函数一进来就命中 if (T NULL) return直接退出。单节点树三个遍历输出同一个字符这个用例也必须用代码验证不能只在脑子里过一遍。我见过最典型的错误写法是把递归出口去掉靠调用前判断来避免空指针// 错误示范空树上会崩溃 void preOrderWrong(BiTree T) { printf(%c , T-data); if (T-lchild ! NULL) preOrderWrong(T-lchild); if (T-rchild ! NULL) preOrderWrong(T-rchild); }这段代码在非空树上没问题但一旦 T 是 NULL第一行就空指针解引用程序秒崩。课程设计的测试数据里几乎必然包含空树这种用例写成这样等于白送分。正确的做法永远是在函数入口统一判空而不是在每个调用点单独判断。3. 非递归遍历用显式栈和队列把递归逻辑翻出来3.1 先序非递归根先出栈右左逆序入栈递归本质是系统栈在帮你管理现场非递归遍历就是自己开一个栈。先序的顺序是“根-左-右”所以入栈时为了保证左孩子先出栈要先把右孩子压进去再把左孩子压进去#define MAXSIZE 100 void preOrderNonRecursive(BiTree T) { if (T NULL) return; BiTree stack[MAXSIZE]; int top -1; stack[top] T; while (top 0) { BiTree p stack[top--]; printf(%c , p-data); if (p-rchild ! NULL) stack[top] p-rchild; if (p-lchild ! NULL) stack[top] p-lchild; } }逻辑说明栈是后进先出先把右孩子压栈、再把左孩子压栈下一轮循环弹出来的就是左孩子正好符合“先左后右”的访问顺序。循环的终止条件是栈空也就是整棵树都处理完。参数说明MAXSIZE 定成 100只对节点数在 100 以内的树安全。如果课程设计题目给了最大节点数 N就把数组长度改成 N 或直接用动态分配的数组否则节点多时数组越界程序可能在遍历中途报错。这个写法对应递归里“访问根然后递归左子树再递归右子树”的过程。和递归最大的差别是自己管理的栈存在程序数据区不占用系统调用栈树深度很大时也不会栈溢出。3.2 中序非递归左链入栈法中序非递归比先序稍微绕一步因为访问根的时机必须在左子树完全处理完之后。常见做法是“沿左链一路压栈出栈时访问节点然后转向右孩子”void inOrderNonRecursive(BiTree T) { BiTree stack[MAXSIZE]; int top -1; BiTree p T; while (top 0 || p ! NULL) { while (p ! NULL) { stack[top] p; p p-lchild; } if (top 0) { p stack[top--]; printf(%c , p-data); p p-rchild; } } }逻辑说明外层 while 的条件是两个状态“栈非空”和“当前节点非空”的或缺一不可。内层 while 负责把当前节点和它一路往左的全部子孙压栈出栈后打印节点再把 p 指向右孩子让下一轮循环处理右子树。参数说明栈的最大深度等于树高。平衡二叉树高度约对数级别退化成链的树高度就是节点数这种情况下栈数组要开得足够大。这个算法的记忆点可以缩成十二个字“先奔最左出栈回头再奔右边”答辩时能说清楚它和递归的对应关系。中序非递归的调试手段比较有效的是打印每一步栈顶元素输入一棵只有三个节点的树手工模拟栈的变化和程序输出对照。这个花的十分钟能帮你省下半小时定位指针错误的时间。3.3 层序遍历队列实现广度优先层序遍历要求从上到下、从左到右先进先出的队列是天然匹配的数据结构typedef struct { BiTree data[MAXSIZE]; int front; int rear; } SqQueue; void levelOrder(BiTree T) { if (T NULL) return; SqQueue q; q.front 0; q.rear 0; q.data[q.rear] T; while (q.front ! q.rear) { BiTree p q.data[q.front]; printf(%c , p-data); if (p-lchild ! NULL) q.data[q.rear] p-lchild; if (p-rchild ! NULL) q.data[q.rear] p-rchild; } }逻辑说明出队一个节点就把它的左右孩子按先左后右的顺序入队。每一层处理完时队列里恰好装着下一层的全部节点所以只要队列非空就证明还有节点没访问。参数说明这个数组队列的实现没有做取模回绕rear 一直往前加所以数组长度必须大于等于树的节点总数。更规范的写法是循环队列把入队改成 q.rear (q.rear 1) % MAXSIZE出队改成 q.front (q.front 1) % MAXSIZE同时用 (q.rear 1) % MAXSIZE q.front 判断队满。课程设计如果没要求“手写循环队列”数组模拟够用但报告里要写清局限性。验证层序输出有个取巧办法把根节点放在数组下标 1左孩子下标 2i右孩子下标 2i1层序遍历的输出顺序正好等于这个数组从左到右的存储顺序。随便拿一棵满二叉树验证一下会立刻发现这个规律写报告时可以用它说明层序遍历的应用场景。3.4 递归与非递归怎么选递归代码短、可读性好、和数学定义一一对应这是它最大的优点。非递归代码长、容易写错但它不依赖系统调用栈、可控性强。课程设计里我的建议是三个递归遍历作为主体代码提交非递归遍历作为扩展功能写进同一份工程两个都跑通答辩时老师问“递归有什么缺点”你就能直接指着非递归版本回答。对比维度递归实现非递归实现代码量每个 5 行左右每个 15 行左右依赖资源系统调用栈自管理栈/队列树深 1000 时可能栈溢出可控可读性好差一些答辩加分项作为基础作为扩展亮点4. 树转二叉树左孩子右兄弟表示法及转换代码4.1 为什么普通树要转成二叉树输出普通树的每个节点孩子数量不固定如果节点结构里开一个固定大小的指针数组空间浪费严重如果开链表又增加一层间接性。左孩子右兄弟表示法用两个指针搞定一切第一个指针指向“最左孩子”第二个指针指向“右兄弟”。转换完成后树变成了一棵二叉树兄弟关系躺在了右子树里父子关系立在左子树里。课程设计把“树与二叉树的转换”放进题目目的就是让你理解这个编码变换。转换前后的树在逻辑上不是同一棵树——存储形态变了但节点之间的层级关系仍然能从二叉树里恢复出来。这个“可逆”的性质是答辩时老师考察的重点你得能说清楚“二叉树还原成树”的过程是转换的逆过程。4.2 树节点的定义与转换函数先定义树节点的存储结构。课程设计里常见的做法是让节点带有 firstChild 和 nextSibling 两个指针#define MAX_CHILD 10 typedef struct CSTNode { char data; struct CSTNode *firstChild; // 最左孩子 struct CSTNode *nextSibling; // 右兄弟 } CSTNode, *CSTree;逻辑说明这个结构就是我们说的左孩子右兄弟表示法。它和二叉树节点的结构一个字面意义上完全一样只是语义不同二叉树里左指针叫 lchild这里叫 firstChild右指针叫 rchild这里叫 nextSibling。参数说明MAX_CHILD 这个宏在这里没被用到但建树函数里如果按“先读孩子个数再逐个创建”的方式输入数据时会用到保留它方便扩展。转换函数是最核心的代码递归三行结束BiTree convertTreeToBinary(CSTree t) { if (t NULL) return NULL; BiTree root (BiTree)malloc(sizeof(BiTNode)); root-data t-data; root-lchild convertTreeToBinary(t-firstChild); root-rchild convertTreeToBinary(t-nextSibling); return root; }逻辑说明递归地处理每个节点。当前节点的第一个孩子递归转换后成为左子树当前节点的右兄弟递归转换后成为右子树。不需要遍历孩子链表因为 nextSibling 指针已经把兄弟串起来了递归会逐个访问到。参数说明t 是原始树当前节点的指针返回值是转换后对应的二叉树节点指针。malloc 分配的新节点没有单独初始化 lchild 和 rchild但递归返回的值马上会赋给左右指针如果某个分支是空的convertTreeToBinary(NULL) 返回 NULL左右指针自然为空所以这段代码不需要再额外赋 NULL。这段代码在只有两三个节点的树上测试结果往往对的到五个以上节点、有多层分支的时候孩子顺序一旦写反就会露馅。所以写完转换函数必须立刻用第 4.3 节的性质做自检。4.3 转换结果怎么验证先序不变、中序等于后序树转二叉树有一个雷打不动的规律普通树的先序遍历序列和转换后二叉树的先序遍历序列完全相同普通树的后序遍历序列和转换后二叉树的中序遍历序列完全相同。这两个性质可以直接写进程序的验证部分一行 printf 的事。举例一棵三层的树根 A 有三个孩子 B、C、D。转换后的二叉树里A 的左孩子是 BB 的右孩子是 CC 的右孩子是 D。对转换后的二叉树做中序遍历得到 B C D A对原树做后序遍历得到的也是 B C D A。两个顺序一致说明转换逻辑没错。我在课程设计里会把这两个性质做成一个 verify 函数先打印原树的先序和后序再打印二叉树的先序和中序四行输出人眼扫一遍就知道对不对。整个验证逻辑不超过十行但答辩演示时效果会好很多。5. 遍历与转换的踩坑排查常见问题与边界条件5.1 空指针解引用最常出现的“为什么崩了”现象建树完成一调用遍历或转换函数程序就崩溃有时还打印出乱七八糟的地址。原因这是最典型的空指针问题。一种是遍历函数没在入口判断 NULL对空树直接访问 data 字段另一种是建树时 malloc 出来的节点没有把 lchild 和 rchild 初始化为 NULL遍历遇到脏指针就炸。解决malloc 之后立刻初始化两个指针为 NULL养成习惯。建树函数建议统一走一个 newNode 函数BiTree createNode(char data) { BiTree p (BiTree)malloc(sizeof(BiTNode)); p-data data; p-lchild NULL; p-rchild NULL; return p; }初始化完先用三个最小用例自测空树、单节点树、只有左链的树。这三个用例通过了再去跑复杂树不要一开始就拿大用例调试那样定位不到问题源头。5.2 递归栈溢出树深 1000 的链式结构现象测试数据里有一棵深度很大的退化成链的树每个节点只有一个孩子递归遍历直接崩溃报错信息指向 preOrder 或 inOrder。原因递归深度等于树的高度。树退化成链时高度等于节点数系统调用栈被消耗殆尽程序被运行时环境强制终止。这种情况在小数据集上完全正常一换大数据就随机崩溃很让人头大。解决对这种数据改走非递归遍历。显式栈的数组是自己开的只要开够大小就不会因为调用栈不够而崩。如果题目明确要求“不得使用递归”那第 3 章的三个非递归函数就是标准答案如果题目没要求也建议至少写一个非递归先序答辩时老师问到递归限制时有话可讲。5.3 转换后孩子顺序反了现象树转二叉树之后先序遍历对得上但二叉树的中序序列和原树的后序序列不一致。原因firstChild 和 nextSibling 的身份在转换时搞混了。正确的是 firstChild 对应二叉树的左子树nextSibling 对应右子树。有人顺手写成“firstChild 到右边”在只有两个孩子的情况下不太明显因为序列看似有规律到三个孩子时才彻底露馅。解决构造一个根带三个孩子的简单用例手工画出转换后的二叉树再用程序跑同样的输入逐行比对。三孩子用例是这类转换题的试金石比任何调试器都管用。5.4 建树输入格式没对齐现象按文本字符串建树比如输入“AB#CD##E##”这样的带空标记的序列程序读出来的树和预想的不一样。原因字符串建树的格式五花八门有的用“#”表示空节点有的用“0”有的用“^”还有一种是按“节点值孩子个数”的格式读多叉树。格式没对齐建出来的树就完全不是你想的那棵。解决写建树函数之前先把输入样例的格式读懂是前序扩展序列还是孩子列表格式。建完树不要急着跑遍历先打印根节点、根的左孩子、根的右孩子三个值确认关键位置正确再往下走。这一步十几秒能挡住后面半小时的返工。5.5 层序遍历的队列长度不够现象层序遍历在小树上没问题节点数一多就随机崩溃单步调试发现队列数组越界。原因数组队列的长度给了一个固定的小值比如 20而层序遍历在最坏情况下队列里要同时容纳一整层节点。完全二叉树的最后一层大约有总节点数的一半节点数越多这一层需要的空间越大。解决把队列数组长度开到“节点总数 1”或者改用链式队列避免长度限制。如果题目要求循环队列必须配合取模和队满判断别用裸数组一路自增。6. 一个验证技巧用先序中序重建二叉树反向确认转换没写错第 4 章讲了“先序不变、中序等于后序”这个自重检查法这里再给一个更强的自检手段从转换后二叉树的中序序列和先序序列反向重建出二叉树。重建结果如果呈现“左孩子右兄弟”的骨架说明转换函数从头到尾没有出错。重建算法的核心是递归先序序列的第一个节点是根拿它去中序序列里定位根左边是左子树、右边是右子树。递归处理左右两段划分子序列时只传边界偏移不复制字符串BiTree rebuildTree(char *pre, char *in, int ps, int is, int len) { if (len 0) return NULL; BiTree root createNode(pre[ps]); int idx 0; while (in[is idx] ! pre[ps]) idx; root-lchild rebuildTree(pre, in, ps 1, is, idx); root-rchild rebuildTree(pre, in, ps 1 idx, is idx 1, len - idx - 1); return root; }逻辑说明ps 是先序序列里当前子树根的位置is 是中序序列里当前子树段的起点len 是子树节点数。while 循环在中序序列里找根的下标idx 是根到段起点的距离也正好是左子树的节点数。左子树的先序段从 ps1 开始长度 idx右子树的先序段从 ps1idx 开始中序段从 isidx1 开始。参数说明调用示例是 rebuildTree(pre, in, 0, 0, n)其中 n 是树的节点总数pre 和 in 是两个以 \0 结尾的字符串。这个函数要求先序和中序来自同一棵二叉树如果题目输入本来就不一致重建出来的树是错的这是输入问题不是算法问题。实际课程设计中我不建议把重建函数加进主流程而是单独写成一个验证函数只在回归测试时调用。理由有三个第一重建算法本身就是另一个考点写进主流程会让代码量膨胀答辩时反而分不清主次第二重建后的树还要和原树递归比对结构比对函数又是额外代码第三评分重点在遍历和转换验证环节做到第 4.3 节的四行输出对比已经足够。把这个验证函数当调试器用日常有三个习惯值得保持每次改完转换函数先跑三孩子用例再跑复杂多叉树用例把测试数据连同期望输出存成文本文件改完代码直接比对不靠肉眼盯终端程序开头打印树的节点数和深度输出值和预期不符时优先检查建树函数别在遍历代码上死磕。说点我自己的经验这门课设计最让初学者吃亏的点不是算法难而是“以为写完递归就万事大吉”。空树不测、非递归不写、转换不验证这三个省略恰恰会在答辩演示时一起找上门。老老实实把非递归、层序、转换自检补全演示时才不会翻车。希望帮到你。本文还有配套的精品资源点击获取
