以升序生成樹遍歷樹

首先我想知道這是否是一個定義明確的操作：我們首先訪問樹的所有樹葉（從左到右）。然後我們訪問所有葉子的父母（從左到右）。然後，所有父母的父母等......直到最後一個未訪問節點被訪問。請注意，根不一定是最後訪問的節點。如果某位父母已經被訪問過，我們簡單地忽略它。我想不出一個反向例子，這個遍歷將會失敗。以升序生成樹遍歷樹

因此，假設它是明確的。什麼是最有效的算法來做這個遍歷？爲了簡化僞代碼，我們可以假設它是一棵二叉樹。首先獲得所有的葉子已經非常耗時。但與此同時，我們可以通過在獲得葉子時將父母存儲在某個地方，從而隨每個父母一起提取。然後我們訪問這些父母名單，每個名單在樹中比先前的名單高出一代。像那樣的東西？不幸的是，我只知道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來重複葉子列表以獲得父母。然後和父母一起重複這個過程，等等。但是，這對我來說似乎非常笨拙和耗時，並且也沒有真正檢查重複。

來源

2015-11-05 prestokeys

如何在構建樹的同時在樹中和節點中存儲額外的字段以促進此操作？我們是否在假設我們得到了一棵樹並且必須遍歷它並且不能指望有任何特殊領域？ –

@ThomasG樹的結構本身可以修改。我認爲「父」成員是我們可以添加到每個節點的唯一新的有用成員。其他成員會爲此提供便利嗎？ – prestokeys

我們可以在構建階段向樹添加'LeftMostNode'。我們還可以添加例如兄弟指針。然後，不是從根開始遍歷，我們可以從最左邊的節點開始，並遵循同級指針。這樣，我們可以在第一遍中增加比率（訪問過的葉子節點的數量/父母訪問過的數量）。基本上是空間與速度的權衡。出於某種原因，SO不會允許我在本評論開始處添加@prestokeys！ –

簡單且正確的解決方案：

構建一個顛倒的樹。在遍歷時，維護一組朝向根的反向鏈接。

創建一個葉子的向量。在你這樣做的時候，把它們的指針值記錄在散列圖中。現在走他們。

現在，對於該向量中的每個元素，將其替換爲其父元素。並將其添加到哈希映射。如果這已經在哈希映射中，而不是它。

重複，直到您用完父母。

這可能不是最優的。

來源

2015-11-05 02:44:25 Yakk

顛倒樹上的谷歌搜索沒有任何結果。什麼是倒置樹的成員？它的葉子？每個節點只有一個「父」成員，沒有孩子？ – 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; 
}

來源

2015-11-05 18:25:46 prestokeys

以升序生成樹遍歷樹

回答

相關問題