基于矢量的二叉树遍历

我有一个基于矢量的二叉树，需要使用各种遍历方法将函数应用到树中的每个值。前序遍历使用递归函数很容易实现，但我一直在进行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

基于矢量的二叉树遍历

回答

相关问题