2

我有一个基于向量的二叉树，需要使用各种遍历方法对树中的每个值应用一个函数。使用递归函数很容易实现前序遍历，但我在使用中序遍历和后序遍历时遇到了麻烦。如果有人可以帮忙，那就太好了！

我应该包括一些额外的信息：我正在使用一个节点向量，每个节点都包含一个布尔变量，说明该节点是否被填充和一个模板化的数据变量。每个节点存储在索引“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”参数。

4

2 回答 2

3

预购：

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-26T01:32:12.960 回答
2

假设你的树是一个最大填充的左显性表示，那么你的数组中的任何给定点在位置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...

给定这个定义，preorder、postorder 和 in-order 都可以通过简单的索引转发和一些检查你的 'occupied' 标志来完成。以下模板假定 typeT是具有“占用”成员的结构类型。

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-26T01:49:26.940 回答