以升序生成树遍历树

问题描述：

首先我想知道这是否是一个定义明确的操作：我们首先访问树的所有树叶（从左到右）。然后我们访问所有叶子的父母（从左到右）。然后，所有父母的父母等......直到最后一个未访问节点被访问。请注意，根不一定是最后访问的节点。如果某位父母已经被访问过，我们简单地忽略它。我想不出一个反向例子，这个遍历将会失败。以升序生成树遍历树

因此，假设它是明确的。什么是最有效的算法来做这个遍历？为了简化伪代码，我们可以假设它是一棵二叉树。首先获得所有的叶子已经非常耗时。但与此同时，我们可以通过在获得叶子时将父母存储在某个地方，从而随每个父母一起提取。然后我们访问这些父母名单，每个名单在树中比先前的名单高出一代。像那样的东西？不幸的是，我只知道C++，但可以找出其他语言的伪代码。

获得一个二叉树的所有叶子（测试）：

template <typename T, typename Comparator> 
inline void BinaryTree<T, Comparator>::obtainLeaves (const std::shared_ptr<Node>& node, 
std::list<std::shared_ptr<Node>>& leaves) const { 
    if (!node) 
     return; 
    if (node->isLeaf()) 
     return leaves.emplace_back(node); 
    obtainLeaves(node->left, leaves); 
    obtainLeaves(node->right, leaves); 
}

虽然叶的父母可以很容易地从这个绕过去了父母该名单，那所有的父母相继存储？或者，不要一次性完成所有事情，首先得到树叶。然后通过调用->parent来重复叶子列表以获得父母。然后和父母一起重复这个过程，等等。但是，这对我来说似乎非常笨拙和耗时，并且也没有真正检查重复。

如何在构建树的同时在树中和节点中存储额外的字段以促进此操作？我们是否在假设我们得到了一棵树并且必须遍历它并且不能指望有任何特殊领域？ –

@ThomasG树的结构本身可以修改。我认为“父”成员是我们可以添加到每个节点的唯一新的有用成员。其他成员会为此提供便利吗？ – prestokeys

我们可以在构建阶段向树添加'LeftMostNode'。我们还可以添加例如兄弟指针。然后，不是从根开始遍历，我们可以从最左边的节点开始，并遵循同级指针。这样，我们可以在第一遍中增加比率（访问过的叶子节点的数量/父母访问过的数量）。基本上是空间与速度的权衡。出于某种原因，SO不会允许我在本评论开始处添加@prestokeys！ –

答

简单且正确的解决方案：

构建一个颠倒的树。在遍历时，维护一组朝向根的反向链接。

创建一个叶子的向量。在你这样做的时候，把它们的指针值记录在散列图中。现在走他们。

现在，对于该向量中的每个元素，将其替换为其父元素。并将其添加到哈希映射。如果这已经在哈希映射中，而不是它。

重复，直到您用完父母。

这可能不是最优的。

颠倒树上的谷歌搜索没有任何结果。什么是倒置树的成员？它的叶子？每个节点只有一个“父”成员，没有孩子？ – prestokeys

@prestokeys是的，跟踪每个节点的父节点。有很多方法可以做到这一点;做一个从节点到父节点的无序映射，例如have_I_visited bool。 – Yakk

答

以下我测试出来正常工作。我不知道它的时间复杂性与雅克解决方案相比有多大，甚至不知道它的时间复杂性。我知道每个非叶节点至少在这里访问两次，这不是一件好事。

template <typename T, typename Comparator> 
template <typename F, typename... Args> 
inline void BinaryTree<T, Comparator>::traverseUpwards (F f, Args&&... args) const { 
    std::list<std::shared_ptr<Node>> leaves; 
    const std::size_t N = heightOfTree(); 
    std::vector<std::list<std::shared_ptr<Node>>> parents(N); 
    std::set<std::shared_ptr<Node>> alreadyVisited; 
    traverseUpwards(root, leaves, parents, alreadyVisited); 
    for (const std::shared_ptr<Node>& node : leaves) 
     f(node, std::forward<Args>(args)...); 
    for (std::size_t i = 0; i < N; i++) { 
     for (const std::shared_ptr<Node>& node : parents[i]) 
      f(node, std::forward<Args>(args)...); 
    } 
} 

template <typename T, typename Comparator> 
inline void BinaryTree<T, Comparator>::traverseUpwards (const std::shared_ptr<Node>& node, 
std::list<std::shared_ptr<Node>>& leaves, 
std::vector<std::list<std::shared_ptr<Node>>>& parents, 
std::set<std::shared_ptr<Node>>& alreadyVisited) const { 
    if (!node) 
     return; 
    if (node->isLeaf()) { // e.g. (!node->left && !node->right) for a binary tree. 
     leaves.emplace_back(node); 
     std::shared_ptr<Node> p = node->parent; 
     std::size_t i = 0; 
     while (p && alreadyVisited.find(p) == alreadyVisited.end()) { 
      parents[i++].emplace_back(p); 
      alreadyVisited.emplace(p); 
      p = p->parent; 
     } 
    } 
    traverseUpwards(node->left, leaves, parents, alreadyVisited); 
    traverseUpwards(node->right, leaves, parents, alreadyVisited); 
} 

template <typename T, typename Comparator> 
inline int BinaryTree<T, Comparator>::heightOfTree (const std::shared_ptr<Node>& node) const { 
    return node ? std::max (heightOfTree(node->left), heightOfTree(node->right)) + 1 : -1; 
}

以升序生成树遍历树

相关推荐