普通树按一定顺序遍历输出的算法


给定一个普通树的根节点,要遍历整个树的所有节点,并且以列表或数组的形式返回结果。列表或的要求如下:

  1. 包括树的所有节点
  2. 结果按照树结构的顺序排列比如: [root, child1, child1ofchild1, child2ofchild1,..., child2, child1ofchild2,...] ,即在列表中,子节点一定紧跟在其父节点之后。

算法要求以 非递归 实现,问题标题的表述可能不太准确,只要结果列表或数组符合上面2点要求,遍历的顺序不限,本问题应该属于深度优先遍历,但并不排斥使用广度优先遍历的实现方式,不考虑算法复杂度,仅为调查实现的方法种类。另外,实现的语言不作限制。

数据结构 算法

绿坝子D河蟹 10 years, 10 months ago

自己帖一个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, 10 months ago

Your Answer