基于向量的二叉树遍历 [英] Vector based binary tree traversal

问题描述

我有一个基于向量的二叉树，需要使用各种遍历方法对树中的每个值应用一个函数。前序遍历很容易用递归函数实现，但是我一直在麻烦对于inorder和postorder遍历做同样的事情。

I have a vector based binary tree and need to apply a function to each value in the tree using various methods of traversal. The preorder traversal was very easy to implement with a recursive function but I have been having trouble doing the same with the inorder and postorder traversals. If anyone could help out that would be great!

我应该包括一些额外的信息：
我使用一个节点向量，每个节点包含一个布尔变量，说明该节点是否被填充和模板化的数据变量。每个节点存储在索引i，而其左子节点在索引2i + 1，右子节点在2i + 2。

Some extra information that I should have included: I am using a vector of nodes, each node containing a boolean variable stating whether or not that node is filled and a templated data variable. Each node is stored at an index "i" while its left child is at the index "2i+1" and the right child at "2i+2".

To应用预先遍历到列表，我首先处理存储在索引0的数据，然后调用这个递归函数

To apply a preorder traversal to the list, I first processed the data stored at index 0 and then called this recursive function

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);
    }
}

< 2作为我的n参数。

twice beginning with indices 1 & 2 as my "n" parameter.

推荐答案

假设你的树是最大填充的左主导表示，在位置 i 的位置 2 * i + 1 和 2 * i + 2 。琐碎的步行：

Assuming your tree is a max-populated left-dominant representation, then any given point in your array at position i will have children at positions 2*i+1 and 2*i+2. The trivial walk:

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都可以通过简单的索引转发和一些检查'标志。以下模板假设 T 是一个具有已占用成员的结构类型。

Given this definition, preorder, postorder, and in-order can all be done with simple index forwarding and some checks for your 'occupied' flag. The following templates assume type T is a structure type that has an 'occupied' member.

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]);
}

这篇关于基于向量的二叉树遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！