一种非递归解决多叉树深度访问的方法

本文主要是介绍一种非递归解决多叉树深度访问的方法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 问题描述：

'''
例如：
A  A1  A11
    A2  A21  A211  A2111
                             A2112
                   A212  A2121
          A22
    A3  A31   A311
          A32   A321 A322
  A4
  
期望的输出：A A1 A11 A2 A21 A211 A2111 A2112 A212 A2121 A22 A3 A31 A311 A32 A321 A322
'''

其中，A1是A的子节点，A11是A1的子节点，A2是A的第二子节点，A21是A2的第一子节点

import reclass A:def __init__(self, name):self.name = nameself.child = []self.parent = Noneself.is_visit = Falseself.child_visit_position = -1def add_child(self, node):self.child.append(node)def set_parent(self, node):self.parent.append(node)def visit(self):self.is_visit = Truedef build_tree():tree_str = '''A A1 A11A2 A21 A211 A2111A2112A212 A2121A22A3 A31 A311A32 A321 A322A4'''result = list(filter(lambda x: x.strip(), re.split(r'[\n\r ]', tree_str)))node_map = {each: A(each) for each in result}for each in result:node = node_map.get(each)node_name = node.nameif len(node_name) == 1:continueelse:parent_name = node_name[:-1]parent_node = node_map.get(parent_name)node.parent = parent_nodeparent_node.child.append(node)return node_map.get("A")def visit_tree(root_tree: A):visit_list = []current_root = root_treewhile True:if not current_root.is_visit:visit_list.append(current_root.name)current_root.is_visit=Trueif len(current_root.child)>0:if current_root.child_visit_position < len(current_root.child)-1:current_root.child_visit_position +=1current_root = current_root.child[current_root.child_visit_position]continueif current_root.parent is not None:current_root = current_root.parentcontinueif current_root.parent is None and (len(current_root.child)<=0 or  current_root.child_visit_position >=len(current_root.child)-1):breakprint("\n".join(visit_list))root_node = build_tree()visit_tree(root_node)

这篇关于一种非递归解决多叉树深度访问的方法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---