Python数据结构与算法-实训指导书4-树 附参考答案

《《Python数据结构与算法》课程实训任务书实训4树【实训目的】理解企业组织结构的树状表示：通过构建企业组织结构树，加深对树形数据结构在现实世界中应用的理解。掌握树节点的自定义和操作：学习如何定义树节点类，并进行节点的添加、查询等操作。实践树的遍历算法：通过编写函数实现对组织结构树的遍历，熟悉树的广度优先搜索算法。提高编程技能：通过实际编码练习，提升运用树结构解决实际问题的编程能力。培养问题解决能力：通过解决具体问题（如查询特定部门的下级部门），培养学生的问题分析和解决能力。【实训场地】××机房（××实训室）【实训条件】硬件设备：台式电脑，软件设备：Pycharm，word或wps【实训任务】实训任务：组织结构题目描述：在企业组织结构中，通常以树的形式表示。每个节点代表一个部门，节点之间的关系形成了组织的层级结构。请完成以下任务：自定义企业组织结构树的节点。编写一个函数：输入任意的部门名称，能输出其直接下级部门。答案：classDepartment:def__init__(self,name):=name#部门名称self.sub_departments=[]#子部门defadd_sub_department(self,sub_department):self.sub_departments.append(sub_department)defget_direct_sub_departments(root,department_name):"""输入任意的部门名称，输出其直接下级部门。:paramroot:组织结构树的根节点:paramdepartment_name:待查询的部门名称:return:直接下级部门的列表，如果部门不存在或没有直接下级部门，则返回空列表"""deffind_department(node,target_name):#递归实现广度优先遍历if==target_name:returnnode.sub_departmentsforsub_departmentinnode.sub_departments:result=find_department(sub_department,target_name)ifresult:returnresultreturn[]department=find_department(root,department_name)returndepartmentifdepartmentelse[]#示例使用#构建一个简化的企业组织结构#CEO#├──CTO#│├──LeadEngineer#│├──SeniorEngineer#├──CFO#│├──Accountant#├──COO#├──HRManager#├──OfficeManagerceo=Department("CEO")cto=Department("CTO")lead_engineer=Department("LeadEngineer")senior_engineer=Department("SeniorEngineer")cfo=Department("CFO")accountant=Department("Accountant")coo=Department("COO")hr_manager=Department("HRManager")office_manager=Department("OfficeManager")ceo.add_sub_department(cto)ceo.add_sub_department(cfo)ceo.add_sub_department(coo)cto.add_sub_department(lead_engineer)cto.add_sub_department(senior_engineer)cfo.add_sub_department(accountant)coo.add_sub_department(hr_manager)coo.add_sub_department(office_manager)#输出直接下级部门target_department="CTO"direct_sub_departments=get_direct_sub_departments(ceo,target_department)forsub_departmentindirect_sub_departments:print(sub_)【实训注意】×××××（清晰列出本次实训操作的注意点，若有安全方面的注意点，务必重点列出）【拓展任务】拓展任务:基于栈实现二叉树深度优先遍历任务描述：在已经学习了二叉树深度优先遍历的基础上，尝试使用栈实现深度优先遍历算法。这个任务将提供一个基本的代码框架，你需要完成其中的缺失部分，理解并运用栈的概念，完成二叉树的深度优先遍历。任务步骤：1.理解深度优先遍历：回顾深度优先遍历算法，确保对其原理和步骤有清晰的理解。2.查看代码框架：仔细阅读提供的Python代码框架，其中包含一个简单的二叉树结构和一个使用栈的深度优先遍历函数。注意，其中有一些缺失的部分需要你完成。classTreeNode:def__init__(self,value):self.value=valueself.left=Noneself.right=Nonedefdfs_stack_traversal(root):ifnotroot:return[]result=[]stack=[root]whilestack:node=stack.pop()result.append(node.value)#TODO:在这里完成代码，将右子节点和左子节点按深度优先顺序压入栈中returnresult#示例使用#构建一个二叉树#1#/\#23#/\#45root=TreeNode(1)root.left=TreeNode(2)root.right=TreeNode(3)root.left.left=TreeNode(4)root.left.right=TreeNode(5)dfs_result=dfs_stack_traversal(root)print(dfs_result)提示：栈的基本操作包括入栈（push）和出栈（pop）。在深度优先遍历中，节点的访问顺序为根节点、右子节点、左子节点。使用栈来模拟递归过程，确保每次弹出的节点符合深度优先遍历的顺序3.完成代码：在注释提示的地方，根据深度优先遍历的规则，将右子节点和左子节点按照正确的顺序压入栈中。4.运行测试：运行代码，查看深度优先遍历的结果是否符合预