基於矢量的二叉樹遍歷

我有一個基於矢量的二叉樹，需要使用各種遍歷方法將函數應用到樹中的每個值。前序遍歷使用遞歸函數很容易實現，但我一直在進行inorder和postorder遍歷時遇到問題。如果任何人都能幫上忙，那會很棒！基於矢量的二叉樹遍歷

一些額外的信息，我應該包括：我使用節點的向量，每個節點包含一個布爾變量，說明該節點是否填充和模板化的數據變量。每個節點存儲在索引「i」處，而其左側的子節點處於索引「2i + 1」，右側的子節點處於「2i + 2」處。

申請前序遍歷到列表中，我首先處理存儲在索引0的數據，然後調用該遞歸函數

template <typename Item, typename Key> 
template <typename Function> 
void BST<Item,Key>::preTraverse(int n, Function f) { 
    if(tree[n].occupied == false) return; 
    else { 
     f(tree[n].data); 
     preTraverse(2*i+1,f); 
     preTraverse(2*i+2,f); 
    } 
}

與指數1 & 2作爲我的「N」參數兩次開始。

來源

2012-11-26 Brandon Bosso

請問您可以發佈您設法正確的遍歷代碼嗎？這將有助於我們更好地理解您用來摺疊矢量樹的方式。 – dasblinkenlight

矢量表示有效地是一個最大化的從左到右的定義嗎？（即[我]的孩子在[2i + 1]和[2i + 2]？ – WhozCraig

「*預序遍歷很容易...但我[有麻煩]與前序...遍歷*」？也許你didn不知道你想說什麼 –

假設你的樹是最大填充左顯性表現，那麼任何給定的點你排列在位置i的孩子將在位置2*i+1和2*i+2。瑣碎的步行路程：

Node Children 
===== =========== 
ar[0]: ar[1], ar[2] 
ar[1]: ar[3], ar[4] 
ar[2]: ar[5], ar[6] 
ar[3]: ar[7], ar[8] 
ar[4]: ar[9], ar[10] etc...

根據這個定義，序，後序和按順序都可以用簡單的指數轉發和一些檢查你的「佔領」標誌來完成。以下模板假定類型爲T是具有「佔用」成員的結構類型。

template<typename T> 
void preorder(const T ar[], size_t i, size_t count, void (&visit)(const T&)) 
{ 
    if (i>=count || !ar[i].occupied) 
     return; 

    visit(ar[i]); 
    preorder(ar, 2*i+1, count, visit); 
    preorder(ar, 2*(i+1), count, visit); 
} 

template<typename T> 
void inorder(const T ar[], size_t i, size_t count, void (&visit)(const T&)) 
{ 
    if (i>=count || !ar[i].occupied) 
     return; 

    inorder(ar, 2*i+1, count, visit); 
    visit(ar[i]); 
    inorder(ar, 2*(i+1), count, visit); 
} 

template<typename T> 
void postorder(const T ar[], size_t i, size_t count, void (&visit)(const T&)) 
{ 
    if (i>=count || !ar[i].occupied) 
     return; 

    postorder(ar, 2*i+1, count, visit); 
    postorder(ar, 2*(i+1), count, visit); 
    visit(ar[i]); 
}

來源

2012-11-26 01:49:26 WhozCraig

你的後單功能是錯誤的，它應該（ar，2 * i + 1，visit）;''，''postorder（ar，2 * i + 2，visit）;''然後''visit（ar [i]）;'' – hinafu

序：

do something with the value 
f(go to the left) 
f(go to the right)

序：

f(go to the left) 
do something with the value 
f(go to the right)

後序：

f(go to the left) 
f(go to the right) 
do something with the value

來源

2012-11-26 01:32:12 hinafu

基於矢量的二叉樹遍歷

回答

相關問題