c++ - 二叉搜索树没有匹配的函数调用

Question

我尝试在 C++ 中使用空节点的构造函数编写二叉搜索树，该构造函数将主数组插入其中并打印结果，至少这是我的意图。如前所述，我遇到了这两个错误，如果可能的话，需要将它们更正为规范。需要做的是创建一个 node_t * 构造函数并将数组插入到二叉搜索树中。
错误:没有匹配函数调用 'BST::insert(BST&, std::array::value_type&)'
错误:没有用于调用“BST::print_bst(BST&)”的匹配函数

#include <cstdio>
#include <cstdlib>
#include <array>
using namespace std;

/*
 * Define a node structure for double linked list.
 */
class BST 
{
private:
    typedef struct node {
        int val;
        struct node* left;
        struct node* right;
    } node_t;
    node_t* tree;

public:
    BST() { tree = NULL; }
    node_t* newNode(int val);
    node_t* insert(node_t* cur_root, int val);
    node_t* find_node(int val, node_t* root);
    node_t* find_val(int val, node_t* root);
    node_t* delete_node(int val, node_t* root);
    void delete_bst(node_t* root);
    void print_bst(node_t* root);
    node_t* find_max(node_t* root);
};

// Creates a new node from a given value, allocating heap memory 
// for it.
BST::node_t* BST::newNode(int val)
{
    node_t* newNode = new node;
    newNode->val = val;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// Inserts a new value into a given binary search tree, 
// allocating heap memory for it.
BST::node_t* BST::insert(BST::node_t* cur_root, int val)
{
     if(cur_root == NULL) { return newNode(val); }
     if( val <= cur_root->val )
         cur_root->left = insert(cur_root->left, val);
     else if( val > cur_root->val)
         cur_root->right = insert(cur_root->right, val);
     return cur_root;
}

BST::node_t* BST::find_node(int val, BST::node_t* root) {
    if (root == NULL || root->val == val) { return root; }
    else if (root->val <= val) { 
        return find_node( val, root->left );
    }
    else { return find_node( val, root->right ); }
    return root;
}

BST::node_t* BST::find_max(BST::node_t* root)
{
    if(root ==  NULL)
    return NULL;
    while(root->right != NULL)
    {
        root = root->right;
    }
    return root;
}

// Deletes node and reorders bst
BST::node_t* BST::delete_node(int val, BST::node_t* root)   
{
    if( root == NULL ) return root;
    else if( val <= root->val )
        root->left = delete_node( val, root->left );
    else if( val > root->val )
        root->right = delete_node( val, root->right );
    else
    {
        // No child
        if( root->right == NULL && root->left == NULL )
        {
            delete root;
            root = NULL;
        }
        // One child
        else if(root->right == NULL)
        {
            node_t* temp = root;
            root = root->left;
            delete temp;
        }
        else if( root->left == NULL )
        {
            node_t* temp = root;
            root = root->right;
            delete temp;
        }
        // Two child
        else
        {
            node_t* temp = find_max(root->left);
            root->val = temp->val;
            root->left = delete_node(temp->val, root->left);
        }
    }
    return root;
}

// Given a pointer to the root, frees the memory associated with 
// an entire tree.
void BST::delete_bst(BST::node_t* root) {
    if(root != NULL)
    {
        delete_bst( root->left );
        delete_bst( root->right );
        delete(root);
        if( root->left != NULL)
            root->left = NULL;
        if( root->right != NULL)
            root-> right = NULL;
        root = NULL;
    }
}

/* Given a pointer to the root, prints all of
 * the values in a tree.
 */
void BST::print_bst(BST::node_t* root) 
{
    if (root != NULL) {
        printf("%d ", root->val);
        print_bst(root->left);
        print_bst(root->right);
    }
}

int main()
{
    BST bst;
    array<int, 9> ai = {17, 9, 23, 5, 11, 21, 27, 20, 22};
    for( size_t i = 0; i < ai.size(); ++i)
    {
        bst.insert(bst, ai[i]);
    }
    BST::print_bst(bst);
}

Answer 1

error: no matching function for call to 'BST::insert(BST&, std::array::value_type&)'
error: no matching function for call to 'BST::print_bst(BST&)'

这些错误告诉您您调用 insert和 print_bst在 main()错了。具体来说，您有:

    for( size_t i = 0; i < ai.size(); ++i)
    {
        bst.insert(bst, ai[i]);
    }
    BST::print_bst(bst);

一个明显的问题是 BST::print_bst(bst); .从语法的角度来看，您不使用解析运算符 bst.print_bst(bst); (这只是冰山一角)

您正在通过 insert和 print_bst参数 bst , BST 类型的对象不是 node_t * .你要传递给他们的是 tree ，但你不能因为 tree是私有(private)的。

处理这个问题的一种方法是编写一个简单的访问器函数来返回 tree 的地址。用于功能，例如

  public:
    ...
    node_t *get_root (void) { return tree; }    /* tree accessor */

现在您可以同时调用 insert和 print_bst如下:

    for (size_t i = 0; i < ai.size(); i++)
        bst.insert (bst.get_root(), ai[i]);

    bst.print_bst (bst.get_root());
    putchar ('\n');       /* make your program POSIX compliant with final '\n' */
}

从编译的角度来看，您还应该使用 -Wshadow 进行编译。以确保您不会隐藏或尝试在另一个范围内重新声明变量。你在这里有这个问题:

BST::node_t* BST::newNode(int val)
{
    node_t* newNode = new node;

newNode影响您的成员函数 newNode ，例如

  public:
    ...
    node_t* newNode(int val);

您可以简单地更改您在 newNode 中声明的新节点至 newnode (或任何不与您的成员函数冲突的东西)。虽然在这里使用它的方式不是问题，但如果您不检查阴影名称，它可能会咬你。

在您的 BST对象， tree是指向二叉树开头的指针，但您永远不会将二叉树的开头(或其他任何东西)分配给 tree .你最终调用 insert一遍又一遍 cur_root == NULL并返回 return newNode(val);没有在任何地方使用，所以结果是 cur_root总是 NULL .相反，您需要检查 tree == NULL并设置 tree = newNode (val);如果是。如果你想返回指针只是 return (tree = newNode (val)); ，例如

/* Inserts a new value into a given binary search tree, 
 * allocating heap memory for it.
 */
BST::node_t *BST::insert (BST::node_t *cur_root, int val)
{
     if (tree == NULL)  /* you must assign 1st node to tree */
        return (tree = newNode(val));

     if (cur_root == NULL)
        return (cur_root = newNode(val));

     if (val <= cur_root->val )
         cur_root->left = insert (cur_root->left, val);
     else if (val > cur_root->val)
         cur_root->right = insert (cur_root->right, val);

     return cur_root;
}

注:保持参数顺序一致。不要交换订单，这只会让事情变得非常困惑，例如

    node_t* insert(node_t* cur_root, int val);
    node_t* find_node(int val, node_t* root);

一种方式或另一种方式。我更喜欢 (node_t* cur_root, int val) ，但这取决于你。如果您喜欢 (int val, node_t* root) ，然后使用它，但要保持一致。

您的 BST::delete_bst在您将它们释放以将它们设置为 NULL 后尝试访问这些值，例如

// Given a pointer to the root, frees the memory associated with 
// an entire tree.
void BST::delete_bst(BST::node_t* root) {
    if(root != NULL)
    {
        delete_bst( root->left );
        delete_bst( root->right );
        delete(root);
        if( root->left != NULL)
            root->left = NULL;
        if( root->right != NULL)
            root-> right = NULL;
        root = NULL;
    }
}

当您到达 root->left = NULL; 时和 root-> right = NULL;和 root = NULL; ，这些内存块不再存在。

相反，您可以使用类似以下内容并设置 tree = NULL;在最后，

/* Given a pointer to the root, frees the memory associated with 
 * an entire tree.
 */
void BST::delete_bst (BST::node_t *root)
{
    if (root != NULL) {
        delete_bst (root->left);
        delete_bst (root->right);
        delete(root);
    }

    tree = NULL;
}

您可以通过使用像 valgrind 这样的内存错误检查程序来发现这些问题。在 Linux 上。 (但显然，您的代码必须先编译才能执行此操作)。每个操作系统都有类似的程序。

那是你的大部分逻辑问题。您需要纠正一些清理问题，例如，如果您声明了一个构造函数，然后也声明了一个析构函数。如果你声明了一个构造函数或析构函数，那么你也应该声明一个复制构造函数，见 Rule of Three

此外，请确保程序的输出符合 POSIX 并始终提供最终的 '\n' .否则，当从控制台运行时，您的提示符会卡在最后一行输出的末尾。您可以简单地添加 putchar ('\n');在 main() 结尾(因为您没有包含 <iostream> )或为 print_bst 编写一个简单的包装函数这对你有用，例如

  public:
    ...
    void print_tree (void) { print_bst (tree); putchar ('\n'); };

然后您可以调用 bst.print_tree();在 main()并且不必担心。

总而言之，您可以执行类似于以下的操作:

#include <cstdio>
#include <cstdlib>
#include <array>
using namespace std;

/*
 * Define a node structure for a binary tree list.
 */
class BST 
{
  private:
    typedef struct node {
        int val;
        struct node* left;
        struct node* right;
    } node_t;
    node_t *tree;

  public:
    BST() { tree = NULL; }
   ~BST() { delete_bst (tree); }   /* if you define BST(), define ~BST() */
    node_t *get_root (void) { return tree; }    /* tree accessor */
    node_t *newNode (int val);
    node_t *insert (node_t* cur_root, int val);
    node_t *find_node (node_t* root, int val);
    node_t *find_val (node_t* root, int val);
    node_t *delete_node (node_t* root, int val);
    void delete_bst (node_t* root);
    void print_bst (node_t* root);
    node_t *find_max (node_t* root);
    /* make program output POSIX compliant with final '\n'
     * (just create a wrapper for print_bst, or add putchar('\n') in main )
     */
    void print_tree (void) { print_bst (tree); putchar ('\n'); };
};

/* Creates a new node from a given value, allocating heap memory for it. */
BST::node_t* BST::newNode (int val)
{
    node_t* newnode = new node_t;
    newnode->val = val;
    newnode->left = NULL;
    newnode->right = NULL;
    return newnode;
}

/* Inserts a new value into a given binary search tree, 
 * allocating heap memory for it.
 */
BST::node_t *BST::insert (BST::node_t *cur_root, int val)
{
     if (tree == NULL)  /* you must assign 1st node to tree */
        return (tree = newNode(val));

     if (cur_root == NULL)
        return (cur_root = newNode(val));

     if (val <= cur_root->val )
         cur_root->left = insert (cur_root->left, val);
     else if (val > cur_root->val)
         cur_root->right = insert (cur_root->right, val);

     return cur_root;
}

/* determine whether node with value exists in tree
 * (don't swap parameter order -- it's confusing)
 */
BST::node_t *BST::find_node (BST::node_t *root, int val)
{
    if (root == NULL || root->val == val)
        return root;
    else if (root->val <= val) { 
        return find_node (root->left, val);
    }
    else
        return find_node (root->right, val);

    return root;
}

/* determine maximum value in the tree */
BST::node_t* BST::find_max (BST::node_t* root)
{
    if (root ==  NULL)
        return NULL;

    while (root->right != NULL)
        root = root->right;

    return root;
}

/* Deletes node and reorders bst */
BST::node_t* BST::delete_node (BST::node_t* root, int val)   
{
    if (root == NULL)
        return root;
    else if (val <= root->val)
        root->left = delete_node (root->left, val);
    else if (val > root->val)
        root->right = delete_node (root->right, val);
    else {
        // No child
        if (root->right == NULL && root->left == NULL) {
            delete root;
            root = NULL;
        }
        // One child
        else if (root->right == NULL) {
            node_t *temp = root;
            root = root->left;
            delete temp;
        }
        else if (root->left == NULL) {
            node_t *temp = root;
            root = root->right;
            delete temp;
        }
        // Two child
        else {
            node_t *temp = find_max (root->left);
            root->val = temp->val;
            root->left = delete_node (root->left, temp->val);
        }
    }
    return root;
}

/* Given a pointer to the root, frees the memory associated with 
 * an entire tree.
 */
void BST::delete_bst (BST::node_t *root)
{
    if (root != NULL) {
        delete_bst (root->left);
        delete_bst (root->right);
        delete(root);
    }

    tree = NULL;
}

/* Given a pointer to the root, prints all of
 * the values in a tree.
 */
void BST::print_bst (BST::node_t *root) 
{
    if (root != NULL) {
        printf ("%d ", root->val);
        print_bst (root->left);
        print_bst (root->right);
    }
}

int main (void) {

    BST bst;
    array<int, 9> ai = {17, 9, 23, 5, 11, 21, 27, 20, 22};

    for (size_t i = 0; i < ai.size(); i++)
        bst.insert (bst.get_root(), ai[i]);

    bst.print_tree();   /* POSIX comliant output w/final '\n'
                         * use wrapper function, or just putchar('\n') here
                         */    
}

示例使用/输出

$ ./bin/arr_bst
17 9 5 11 23 21 20 22 27

内存使用/错误检查

$ valgrind ./bin/arr_bst
==8123== Memcheck, a memory error detector
==8123== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==8123== Using Valgrind-3.12.0 and LibVEX; rerun with -h for copyright info
==8123== Command: ./bin/arr_bst
==8123==
17 9 5 11 23 21 20 22 27
==8123==
==8123== HEAP SUMMARY:
==8123==     in use at exit: 0 bytes in 0 blocks
==8123==   total heap usage: 10 allocs, 10 frees, 72,920 bytes allocated
==8123==
==8123== All heap blocks were freed -- no leaks are possible
==8123==
==8123== For counts of detected and suppressed errors, rerun with: -v
==8123== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

始终确认您已释放所有已分配的内存并且没有内存错误。

如果您还有其他问题，请仔细查看并告诉我。