二叉树上的结点路径
二叉树上的结点路径
附加二叉树上的结点路径
指导教师：徐龙玺
一、设计内容及要求
树形结构是数据结构中非常重要的非线性数据结构，树中结点之间具有明确层次关系。本课程设计是有关二叉树的存储结构及其遍历的应用，首先在采用链式存储的二叉树上，用bt指向根结点，p指向任一给定结点，然后用非递归的方式分别写出二叉树的三种遍历方式，最后编程实现求从根结点到给定结点之间的路径。
二、设计思路
（1）设计思路分析
要求一是对二叉树的三种非递归遍历，二叉树存储结构分为顺序存储结构和链式存储结构，这里我采用链式存储结构以及最常使用的二叉链表结点定义（一个数据域，两个指向左右孩子的指针域）。在编程语言中通常用栈这种数据结构，依靠迭代法来实现递归的逻辑。因此在非递归遍历中我首先选用结合栈数据结构，与课堂上所学递归方法不同之处在于使用迭代法来模拟递归的时候，需要特别注意栈的先进后出的特点，需要后放入要先处理的数据才可以在弹出时先处理该数据。
要求二是求从根结点到给定结点之间的路径，首先在二叉树无论那种遍历方法都可以遍历二叉树中所有节点，但想计算根结点bt与结点*p之间的路径，依然需要借助静态数组stack来存储路径，借助栈来简化树在递归遍历过程中跟踪路径的操作。
首先使用静态数组stack动态存储从根节点到当前节点的路径（本设计中假设stack数组大小为10即假设二叉树最大深度为10），leavel参数跟踪当前节点在树中的深度并管理stack数组。开始运行，检查根节点bt是否为空，若为空则返回代表是空子树。然后将当前结点的压入stack中，如果当前节点的值不是正在搜索的值 (p)，则函数递归调用自身来处理当前节点的左右子树；如果如果它与指定的值 p 匹配，则函数打印从根到当前结点的路径。
（2）所用数据结构与算法及其优点
采用非递归遍历二叉树，简单直观易于实现，不需要使用系统栈进行递归调用，只需借助辅助数据结构（如栈）即可。且在遍历的过程中很容易地获得树的层次结构，也便于理解和处理。这些优点使得每种非递归遍历方法在不同的场景中都有其独特的应用价值。
采用了树结构和线性结构中的栈。树结构作为一类重要的非线性数据结构，不仅在计算机领域应用广泛，同现实世界也有很多联系如工程上的最短路径与最低成本，人类社会的族谱等都可以用树结构表示。
而同时采用栈结构是由于树的基本操作中的遍历操作，是按一定规则与顺序走遍二叉树的所有结点，由于二叉树本身是非线性结构，因此，树的遍历实质上是将二叉树各个节点转换成一个线性序列来表示。而求结点路径的本质就是对这个转换成的线性序列进行操作，因此需要借用栈先进后出的特点来找出所有经过的结点。采用栈来计算根节点到指定结点路径的优点有：
- 优化路径存储： 使用栈能够方便地存储从根节点到当前节点的路径。每当访问一个节点时，将该节点的值压入栈中，这样栈中的内容就表示了当前访问节点的路径。
- 简化输出：在找到目标节点时，直接通过栈的内容就可以输出完整的路径，不需要额外的数据结构简化了输出路径的逻辑。
（3）重要功能流程图
1.非递归遍历（中序为例）
2.求指定结点路径
3.系统功能模块图
三、设计结果及分析
第一部分二叉树的非递归遍历，分别用空二叉树，满二叉树，完全二叉树，普通二叉树四种特别的二叉树来运行测试，二叉树示意图如下：
空二叉树：直接返回，退出函数
满二叉树：前序结果ABDECFG，中序结果DBEAFCG，后序结果DEBFGCA
完全二叉树：前序结果ABDECF,中序结果DBEAFC,后序结果DEBFCA
普通二叉树：前序结果ABDEFC,中序结果BEDFAC，后序结果EFDBCA
三种非递归遍历的时间复杂度为：O(N)
第二部分求根节点到指定结点的路径，以上述图6中的普通二叉树为例分别取距离根节点最近的A结点本身，距离最远的E结点，以及随机选定的结点C进行测试结果如下：
求根节点到指定结点的路径时间复杂度分析：SearchPath函数使用深度优先搜索的方法来查找根节点到指定结点的路径。因此对于每个结点，都会递归调用左右子树，每个结点都可能被访问一次。总的时间复杂度取决于访问结点的数量，设二叉树结点数为N，最坏情况下需要访问所有结点。因此时间复杂度为O（N）。
四、总结
本系统实现了链式存储创建二叉树，二叉树的三种非递归遍历方式，以及求根结点到指定结点的路径三大功能。程序运行后先按1创建一个二叉树再进行后续操作(创建一次即可)。在本次课程设计中比较困难的点以及学到的重要知识主要有以下三点：
（1）非递归遍历后序遍历
非递归方式的后序遍历主要难点在于理解如何使用单个循环实现后序遍历，同时颠倒左右孩子的顺序，利用数组来实现前序遍历的逆序输出。通过课后查阅资料与画图方法结合最终理解了如何输出颠倒后的前序遍历序列。
（2）递归在树结构中的运用
递归是这段代码的核心。在每次调用 SearchPath 函数时，它会深入二叉树的左子树和右子树，并在找到目标节点或者遍历完整棵树后进行回溯。这种递归调用可能会导致对递归的理解困难，特别是在处理函数参数和递归回溯时。深入学习理解了静态数组stack的相关知识，并运用到实际代码中去。本系统中用静态数组stack动态地存储从根节点到当前结点的路径，用level来正确追踪路径，同时注意到静态数组的大小限制可能会影响到可以处理路径的长度。
（3）getchar()的妙用
出现问题：在创建根节点是出现回车符，未能正确接收根节点数据
解决办法：在 scanf() 读取用户选择 (x) 后，包含 getchar() 的原因是为了消耗输入缓冲区中遗留的换行字符。当用户输入整数并按Enter键时，换行字符也会添加到输入缓冲区。如果不清除，这个换行字符可能会被下一个输入操作消耗或影响程序逻辑。因此我用了课堂上讲getchar() 函数用于捕获用户在使用 scanf() 输入后输入的换行字符 (‘\n’)，确保程序可以按预期运行。
