定父节点数组，打印出树

Question

给定一个未排序的节点阵列的前序遍历，其中节点被定义为：
Node { int id; int parent_id; string label; }

每个节点都有自己独特的ID。 parent_id在树中标识其父项。问题是如何执行树的前序遍历？ （不一定是二叉树）

这是一个面试问题，困扰了我好几天。我能想到的是使用哈希映射map<int,list<node> >其中关键是parentid。然后我不能再走了。我应该从地图上构建树并执行预先遍历，还是有直接从地图上完成的好方法？那怎么样？任何提示表示赞赏！

Answer 1

因此，你需要：

map<int, list<Node> > childMap; 
map<int, Node> nodeMap; 

你会发现，没有一个家长（PARENT_ID = -1或东西），这显然是根的节点。设置完上面的地图之后，您可以为该节点调用下面的函数。

preOrder(int id) 
{ 
    process(nodeMap[id]); 
    foreach (Node node: childMap[id]) 
    preOrder(node); 
}