普通树按一定顺序遍历输出的算法
给定一个普通树的根节点，要遍历整个树的所有节点，并且以列表或数组的形式返回结果。列表或的要求如下：
- 包括树的所有节点
- 结果按照树结构的顺序排列比如： [root, child1, child1ofchild1, child2ofchild1,..., child2, child1ofchild2,...] ，即在列表中，子节点一定紧跟在其父节点之后。
算法要求以 非递归 实现，问题标题的表述可能不太准确，只要结果列表或数组符合上面2点要求，遍历的顺序不限，本问题应该属于深度优先遍历，但并不排斥使用广度优先遍历的实现方式，不考虑算法复杂度，仅为调查实现的方法种类。另外，实现的语言不作限制。
绿坝子D河蟹
10 years, 9 months ago
Answers
自己帖一个python的，用了队列。起始不用队列也可以，用栈就可以搞定。
代码如下:
from collections import deque
def get_tree_list_non_recursive(root):
result = []
stack = deque()
result.append(root)
if len(node.children.keys()) > 0:
for ck in node.children:
if len(node.children[ck].children.keys()) > 0:
stack.append(root.children[ck])
else:
result.append(root.children[ck])
if len(stack) > 0:
while len(stack) > 0:
cnode = stack.popleft()
result.append(cnode)
if len(cnode.children.keys()) > 0:
stack.extendleft(cnode.children.values())
return result
class Node(object):
'''数据类型'''
def __init__(self, item, parent=None, children=None):
self.item = item
self.parent = parent
self.children = children or weakref.WeakValueDictionary()
def add_child(self, name, child):
self.children[name] = child;
child.parent = self
def remove_child(self, name):
try:
self.children[name].parent = None
del self.children[name]
except KeyError:
raise KeyError("No child named " + name + "!")
@property
def grade(self):
grade = 0
parent = self.parent
while parent:
grade += 1
parent = parent.parent
return grade
def __repr__(self):
out = "<Node item: " + self.item + " has_parent: "
if self.parent:
out += "yes"
else:
out += "no"
if self.children.keys():
out += " children: " + str(self.children.keys())
else:
out += " children: None"
out += " >"
return out
綯気ぐ公￡爵
answered 10 years, 9 months ago