南京工程学院课程设计说明书(论文)题 目中根与后根构造二叉树与二叉树的匹配替换课 程 名 称 数据结构 院（系、部、中心） 计算机工程学院 专 业 计算机科学与技术 班 级 计算机卓越 131 学 生 姓 名 羌秀君 学 号 202530404 设 计 地 点 信息楼 指 导 教 师 叶核亚 设计起止时间：2025 年 5 月 10 日至 2025 年 5 月 20 日 一、课程设计目的和要求目的：深化理解数据结构的基本理论，掌握数据存储结构的设计方法，掌握基于成绩数据结构的各种操作的实现方法，训练对基础知识和基本方法的综合运用能力，增强对算法的理解能力，提高软件设计能力。在实践中培育独立分析问题和解决问题的作风和能力。要求：熟练运用 C++语言、基本数据结构和算法的基础知识，独立编制一个具有中等难度的、解决实际应用问题的应用程序。通过题意分析、选择数据结构、算法设计、编制程序、调试程序、软件测试、结果分析、撰写课程设计报告等环节完成软件设计的全过程，不断地完善程序以提高程序的性能。二、题意说明及分析题目要求采纳中根和后根序列构造一颗二叉树，并匹配替换二叉树的子树。中根和后根构造：由于后根可以确定一颗树的根，而中根在知道根的情况下可以确定左右子树的序列，因此这样递归，中根和后根可以确定一颗唯一的二叉树。匹配替换二叉树：1.通过遍历二叉树找到关键树根值在待匹配树中首次出现的位置，返回节点地址。2.推断以找到的节点为根的子树和带匹配的树是否相同，采纳递归算法。3.确定以找到根节点的子树与带匹配的树相同，然后删除以此为根节点的子树，然后再将带替换的树复制到删除的节点。三、算法设计与分析算法设计思路、数据结构描述、流程图等中根和后根构造算法：设数组 inlist[]和 lalist[]分别表示一颗二叉树的中根和后根序列，两序列长度均为 n。1.由后根遍历的次序可知，该二叉树的根是 lalist[n-1]；改节点必定在中根次序中，设根节点在中根次序的第 i 个位置即 inlist[i]=lalist[n-1]。2.由中根遍历次序知，inlist[i]节点前的节点在根的左子树上，inlist[i]后的所有节点在根节点的右子树上。因此，根的左子树由 i 个节点组成，子序列为：左子树的后根次序 lalist[0]....lalist[i-1]左子树的中根次序 inlist[0]...inlist[i-1]根的右子树由 n-j-1 个节点，子序列为：右子树的后根次序 lalist[i]...lalist[n-2]右子树的中根次序 inlist[i+1]...inlist[n-1]3.以此...
