文章/答案/技术大牛

发布

社区首页 >问答首页 >如何正确使用模板类的嵌套类？

问如何正确使用模板类的嵌套类？
EN

Stack Overflow用户

提问于 2015-02-13 17:50:21

回答 2查看 200关注 0票数 0

全!我正在尝试实现一个简单的模板类二进制搜索树。我遇到了一些关于函数定义的问题。以下是我的BST类代码

#ifndef BINARY_SEARCH_TREE_H
#define BINARY_SEARCH_TREE_H

#include <iostream>
#include <stdlib.h>

using namespace std;

template<class T>
class BST
{
    struct TreeNode {
        TreeNode* left;
        TreeNode* right;
        T value;
    };

    //member functions
    void destroyTree(TreeNode* leaf);
    void insert(T key, TreeNode* leaf);
    TreeNode* search(T key, TreeNode* leaf);
    void printInOrder(TreeNode* leaf);
    void printPreOrder(TreeNode* leaf);
    void printPostOrder(TreeNode* leaf);

    //memebr variables
    TreeNode* root;
public:

    enum Traversal { INORDER, PREORDER, POSTORDER };

    BST();
    BST(T key);
    ~BST();

    void insert(T key);
    TreeNode* search(T key);
    void printTree(T option);
    void destroyTree();
};

template <class T>
BST<T>::BST()
{
    root = NULL;
};

template <class T>
BST<T>::BST(T key)
{
    root = new TreeNode;
    root->left = NULL;
    root->right = NULL;
    root->value = key;
};

template <class T>
BST<T>::~BST()
{
    destroyTree();
};

template <class T>
void BST<T>::destroyTree(TreeNode* leaf)
{
    if (leaf->left != NULL) destroyTree(leaf->left);
    if (leaf->right != NULL) destroyTree(leaf->right);
    delete leaf;
    leaf = nullptr;
};

template <class T>
void insert(T key, BST<T>::TreeNode* leaf)
{
    if (leaf->value == key)
    {
        cout << "failed inserting node: duplicate item" << endl;
        return;
    }
    else if (leaf->value < key)
    {
        if (leaf->right != NULL) insert(key, leaf->right);
        else
        {
            TreeNode newNode = new TreeNode;
            newNode->left = NULL;
            newNode->right = NULL;
            newNode->value = key;
            leaf->right = newNode;
        }
    }
    else
    {
        if (leaf->left != NULL) insert(key, leaf->left);
        else
        {
            TreeNode newNode = new TreeNode;
            newNode->left = NULL;
            newNode->right = NULL;
            newNode->value = key;
            leaf->left = newNode;
        }
    }
};

template <class T>
BST<T>::TreeNode* BST<T>::search(T key, TreeNode* leaf)
{
    if (leaf == NULL) return NULL;
    if (leaf->value == key) return leaf;
    else if (leaf->vluae < key) return search(key, leaf->right);
    else return search(key, leaf->left);
};

template <class T>
void printInOrder(TreeNode* leaf)
{
    if (leaf->left != NULL) printInOrder(leaf->left);
    cout << leaf->value << " ";
    if (leaf->right != NULL) printInOrder(leaf->right);
};

template <class T>
void printPreOrder(TreeNode* leaf)
{
    cout << leaf->value << " ";
    if (leaf->left != NULL) printPreOrder(leaf->left);
    if (leaf->right != NULL) printPreOrder(leaf->right);
};

template <class T>
void printPostOrder(TreeNode* leaf)
{
    if (leaf->left != NULL) printPostOrder(leaf->left);
    if (leaf->right != NULL) printPostOrder(leaf->right);
    cout << leaf->value << " ";
};

template <class T>
void BST<T>::insert(int key)
{
    if (this->root == NULL)
    {
        this->root = new TreeNode;
        this->root->left = NULL;
        this->root->right = NULL;
        this->root->value = key;
    }
    else insert(key, root);
};

template <class T>
BST<T>::TreeNode* BST<T>::search(int key)
{
    search(key, this->root);
};

template <class T>
void BST<T>::printTree(int option)
{
    switch (option)
    {
    case BST<T>::INORDER:
        printInOrder(this->root);
        cout << endl;
        break;
    case BST<T>::POSTORDER:
        printPostOrder(this->root);
        cout << endl;
        break;
    case BST<T>::PREORDER:
        printPreOrder(this->root);
        cout << endl;
        break;
    }
};

template <class T>
void BST<T>::destroyTree()
{
    destroyTree(this->root);
};

#endif

正如您所看到的，对于void insert(T key, BST<T>::TreeNode* leaf)和BST<T>::TreeNode* BST<T>::search(T key, TreeNode* leaf)函数，我需要对TreeNode类执行一些操作，比如返回它的一个对象或将其传递给一个函数，该函数是在BST类中定义的嵌套类型。我得到的错误是语法错误，但我不知道我在代码中哪里做错了。任何建议或建议都将不胜感激！

c++

nested

template-classes

回答 2

Stack Overflow用户

发布于 2015-02-13 18:22:23

您应该：

将每个单独的TreeNode替换为BST<T>::TreeNode，因为可能会有不同的TreeNode定义，因此编译器需要知道您正在讨论的定义。
在每个BST<T>::TreeNode前面添加typename。BST<T>::TreeNode可能有几种不同的定义，甚至有些不是类型，因此您需要告诉编译器它是一种类型。

票数 2

Stack Overflow用户

发布于 2015-02-13 19:07:30

#include <iostream>
#include <stdlib.h>

using namespace std;

template<class T>
class BST
{
    struct TreeNode {
        TreeNode* left;
        TreeNode* right;
        T value;
    };

    //member functions
    void destroyTree(TreeNode* leaf);
    void insert(T key, TreeNode* leaf);
    TreeNode* search(T key, TreeNode* leaf);
    void printInOrder(TreeNode* leaf);
    void printPreOrder(TreeNode* leaf);
    void printPostOrder(TreeNode* leaf);

    //memebr variables
    TreeNode* root;
public:

    enum Traversal { INORDER, PREORDER, POSTORDER };
    BST();
    BST(T key);
    ~BST();

    void insert(T key);
    TreeNode* search(T key);
    void printTree(T option);
    void destroyTree();
};

template <class T>
BST<T>::BST()
{
    root = NULL;
};

template <class T>
BST<T>::BST(T key)
{
    root = new TreeNode;
    root->left = NULL;
    root->right = NULL;
    root->value = key;
};

template <class T>
BST<T>::~BST()
{
    destroyTree();
};

template <class T>
void BST<T>::destroyTree(TreeNode* leaf)
{
    if (leaf->left != NULL) destroyTree(leaf->left);
    if (leaf->right != NULL) destroyTree(leaf->right);
    delete leaf;
    leaf = nullptr;
};

template <class T>
void BST<T>::insert(T key, typename BST<T>::TreeNode* leaf)
{
    if (leaf->value == key)
    {
        cout << "failed inserting node: duplicate item" << endl;
        return;
    }
    else if (leaf->value < key)
    {
        if (leaf->right != NULL) insert(key, leaf->right);
        else
        {
            BST<T>::TreeNode* newNode = new TreeNode;
            newNode->left = NULL;
            newNode->right = NULL;
            newNode->value = key;
            leaf->right = newNode;
        }
    }
    else
    {
        if (leaf->left != NULL) insert(key, leaf->left);
        else
        {
            BST<T>::TreeNode* newNode = new TreeNode;
            newNode->left = NULL;
            newNode->right = NULL;
            newNode->value = key;
            leaf->left = newNode;
        }
    }
};

template <class T>
typename BST<T>::TreeNode* BST<T>::search(T key, typename BST<T>::TreeNode* leaf)
{
    if (leaf == NULL) return NULL;
    if (leaf->value == key) return leaf;
    else if (leaf->vluae < key) return search(key, leaf->right);
    else return search(key, leaf->left);
};

template <class T>
void printInOrder(typename BST<T>::TreeNode* leaf)
{
    if (leaf->left != NULL) printInOrder(leaf->left);
    cout << leaf->value << " ";
    if (leaf->right != NULL) printInOrder(leaf->right);
};

template <class T>
void printPreOrder(typename BST<T>::TreeNode* leaf)
{
    cout << leaf->value << " ";
    if (leaf->left != NULL) printPreOrder(leaf->left);
    if (leaf->right != NULL) printPreOrder(leaf->right);
};

template <class T>
void printPostOrder(typename BST<T>::TreeNode* leaf)
{
    if (leaf->left != NULL) printPostOrder(leaf->left);
    if (leaf->right != NULL) printPostOrder(leaf->right);
    cout << leaf->value << " ";
};

template <class T>
void BST<T>::insert(T key)
{
    if (this->root == NULL)
    {
        this->root = new TreeNode;
        this->root->left = NULL;
        this->root->right = NULL;
        this->root->value = key;
    }
    else insert(key, root);
};

template <class T>
typename BST<T>::TreeNode* BST<T>::search(T key)
{
    search(key, this->root);
};

template <class T>
void BST<T>::printTree(T option)
{
    switch (option)
    {
        case BST<T>::INORDER:
            printInOrder(this->root);
            cout << endl;
            break;
        case BST<T>::POSTORDER:
            printPostOrder(this->root);
            cout << endl;
            break;
        case BST<T>::PREORDER:
            printPreOrder(this->root);
            cout << endl;
            break;
    }
};

template <class T>
void BST<T>::destroyTree()
{
    destroyTree(this->root);
};

现在应该可以工作了，但是充满了一些小错误，比如：TreeNode newNode = new TreeNode;、template <class T> void insert而不是template <class T> void BST<T>::insert

票数 1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/28496714

复制

相似问题

问如何正确使用模板类的嵌套类？
EN

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何正确使用模板类的嵌套类？EN

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何正确使用模板类的嵌套类？
EN