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

发布于 2016-11-26 02:37:19 字数 357 浏览 1176 评论 3

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

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

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

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(3

想挽留 2017-09-21 23:58:53

自己帖一个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

夜无邪 2017-08-14 11:45:21

不知道你要的是不是先根遍历的非递归算法?

void unread(bitree T) // T 是指向树根节点的指针
{
  int result[100],i=0;
  bitree tree[50],p; // bitree 是指向树节点的指针类型,p 指向当前节点
  int top,base; // top 是栈顶位置
  top=base=0;
  tree[top]=p=T;
  while(top>=0) // 判断是否遍历过根节点
  {
    while(p) // 遍历左孩子
    {
      p=p->lchild;
      tree[++top]=p;
    }
    if(!tree[top])
    {
      top--; // 如果左孩子为空,退回到父节点
      putchar('n');
      if(top>=0)
      {
        p=tree[top];
        if(p->data){ // 遍历(访问)父节点,输出数据
          result[i] = p->data;
          i++;
        }
        p=p->rchild; // 遍历右节点
        tree[top]=p;
      }else;
    }else;
  }
}
清晨说ぺ晚安 2017-05-24 14:28:23

树的遍历无非深度优先或者广度优先,无论哪种都不可能做到“子节点一定紧跟在其父节点之后 ”。看楼主的例子应该是要求深度优先。

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文