遍历bst使用函数指针的正确方法

Question

我正在创建一个二叉搜索树模板 class，并想为中序遍历函数使用函数指针，我对函数指针没问题，但由于某种原因我不知道如何使用中序一次代码已经到位。网上没有太多其他东西对我有帮助，所以任何反馈都会很棒。

class Bst
{
    struct Node
    {
        T data;
        Node * left;
        Node * right;
        Node(T key) :data(key), left(nullptr), right(nullptr) {}
    };

    typedef void(*inorderPtr)(T &);
    typedef void(*preorderPtr)(T &);
    typedef void(*postorderPtr)(T &);

    Node * root;
    T & GetItem() const;
    void deleteNode(Node*);
    void printNode(Node*);
    void inorder(Node * root, void (*inorderPtr)(T &)) const;
    void preorder(Node * root) const;
    void postorder(Node * root) const;

public:

    Bst();
    ~Bst();
    Bst(const Bst<T> & source);
    const Bst<T> & operator = (const Node &);
    void insert(const T);
    void print();
    void inorder(void(*inorderPtr)(T &)) const;
    void printPreorder() const;
    void printPostorder() const;
};

基本bst的部分代码如下

template<class T>
inline T & Bst<T>::GetItem() const
{
    return data;
}

template<class T>
inline void Bst<T>::inorder(Node * root, void(*inorderPtr)(T &)) const
{
    if (root->left != nullptr)
    {
        inorder(root->left, inorderPtr);
    }

    inorderPtr(root->GetItem());

    if (root->right != nullptr)
    {
        inorder(root->right, inorderPtr);
    }
}

template<class T>
inline void Bst<T>::inorder(void(*inorderPtr)(T &)) const
{   
    inorder(this->root, inorderPtr);
}

int main()
{
        Bst<int> tree;

    for (int i = 0; i < 100; i++)
    {
        tree.insert(i);
    }

    tree.inorder();

}

主要是基本测试，但在使用 inorder() 时遇到问题；参数不足

Answer 1

您需要花数周时间阅读更多有关 C++ 的内容。请记住，C++ 是一种非常难的编程语言（即使练习 5 年，您也不会成为 C++ 专家；我用 C++ 编写代码，但我不是专家； C++ 专家在地球上可能只有几十个）。并且不要学习任何早于 C++11 and preferably C++17 的东西（因为我们是 2019 年，所以最新的 C++ 编译器已经兼容 C++17，并且它们都接受 C++11；如果你的编译器不知道关于 C++11，更新你的 C++ 编译器）。

^{（如果你需要在C++03 or some earlier C++, instead of C++11, ask for a pay raise, because then you are using obsolete tools. Today, in 2019, coding in C++03 is like coding in COBOL中编码：它需要一个具有货币价值的稀有技能。）}

所以首先，阅读一本很好的 C++ 书籍，例如 Programming -- Principles and Practice Using C++ (by the designer of C++). Then look into some C++ reference site. Read also how to debug small programs（这里非常相关）。

然后，使用所有警告和调试信息进行编译。如果你的编译器是 GCC，至少用 g++ -Wall -g 编译。 您会收到一条很好的诊断信息。请在你的问题中显示它。

最后，你声明你的 inorder 接受一个参数，而你在调用它时没有给出任何参数（这样做是不一致的）：

   tree.inorder();
   //           ^     missing argument

你问错了：

I am creating a binary search tree template class, and want to use function pointers

正如我评论的那样，您应该避免function pointers (they are so C like, not genuine C++), and use some std::function type in the declaration of that inorder, and pass perhaps some anonymous lambda expression at its call site. Because what you should pass conceptually is not a function pointer, but a closure (which combines a raw function pointer with data, the closed values), or, if you unfortunately want to avoid genuine C++ and stay compatible with plain C procedural programming style and calling conventions, have callbacks，因此不仅要传递原始函数指针，还要传递一些客户端数据。

所以你真的想声明和定义（像大多数 C++ containers 那样）

template<class T>
inline void Bst<T>::inorder(std::function<void(T&)> fun) const;

（稍后，作为优化，您可以将 fun 作为 const reference 传递）并且您将使用它（与一个 lambda 表达式）例如：

tree.inorder([](T& x) { std::cout << x << std::endl; });

我声称你的老师应该首先教你闭包以及如何以某种 functional programming 风格很好地使用它们（这在你的情况下很自然），然后解释它们的实现也和后来的函数指针教学。在大多数情况下，函数指针在 C++ 中已过时（但它们的存在是为了与 C 和 C++ 的过时版本兼容）。

PS。不明白的地方要解释几十页（因为C++type system很复杂）。我们这里没有那么多space（还有时间写）。请花一周时间读一本好的 C++ 书。

Answer 2

假设您要打印树中每个节点的值：

void value_printer(int& value)
{
    std::cout << "Value is " << value << '\n';
}

int main()
{
    Bst<int> tree;

    // Insert nodes...

    tree.inorder(&value_printer);
}

您在 inorder 调用中传递了指向 value_printer 函数的指针。然后将为遍历中的每个节点调用该函数。

当然，您传递指针的函数可以做其他事情。正如目前声明的那样，您甚至可以修改树的值。

了解有关 std::function and lambda expressions. See also 答案的更多信息。

遍历bst使用函数指针的正确方法

Correct way to use function pointers for traversal bst

c++

traversal

function-pointers

inorder

binary-search-tree