C++ 二叉树

Question

我目前正在使用 C++ 开发一个项目，该项目要求我将文本文件中的字母存储在二叉树中。我应该遍历字符串并将字母与字母出现的次数一起存储在树中。我不确定如何编写插入函数以使其同时存储字母和整数。到目前为止，这就是我在树中存储单个值的方式。

void BinaryTree::insert(TreeNode *&nodePtr, TreeNode *&newNode)
{
    if (nodePtr == NULL)
        nodePtr = newNode;
    else if (newNode->value < nodePtr->value)
        insert(nodePtr->left, newNode);
    else
        insert(nodePtr->right, newNode);
}

void BinaryTree::insertNode(int num)
{
    TreeNode *newNode = NULL;
    newNode = new TreeNode;
    newNode->value = num;
    newNode->left = newNode->right = NULL;
    insert(root, newNode);
}

这是程序的class：

class BinaryTree
{
    private:
        struct TreeNode
        {
            int value;
            TreeNode *left;
            TreeNode *right;
        };

        TreeNode *root;

        void insert(TreeNode *&, TreeNode *&);

    public:
        BinaryTree()
        {
            root = NULL;
        }
        void insertNode(int);
};

和 int main:

int main()
{
    string filename;
    string filedata;
    BinaryTree tree;
    fstream file;
    cout << "Please enter a filename: ";
    cin >> filename;

    file.open(filename.c_str(), ios::in);
    if (file)
    {
        while (file)
        {
            file >> filedata;
            //tree.insertNode(filedata, );
        }
        file.close();
    }
    else
    {
        cout << "ERROR: Cannot open file.";
    }

    return 0;
}

我假设我需要向 insertNode 函数添加一个字符串元素，但我不确定如何将这两个值一起存储在树中。

感谢您的帮助。

Answer 1

你只需要将 struct TreeNode 的结构更改为这个 ::

struct TreeNode
{
    char value; // to store the char value of string
    int count; // number of times the character has occured
    TreeNode *left;
    TreeNode *right; 
};

从您的代码看来，您打算使用 BST（如果节点的值小于根值，则向左移动，如果值大于根值，则向左移动），在这种情况下，您的 insertNode 和 insert 函数完全错误。

你应该首先遍历树，使用正在考虑的字符，如果已经有一个特定值的节点，你增加它的计数，如果你命中一个空，那么你添加一个新节点。

因此，您的 insert 和 insertNode 函数应如下所示::

void BinaryTree::insertNode(char value)
{
    if(root == NULL) {
        root = new TreeNode;
        root->value = value;
        root->count = 1;
        root->left = root->right = NULL;
    } else {
        if(root->value > value)
            insert(root->left, root, value);
        else
            insert(root->right, root, value);
    }
}

void BinaryTree::insert(TreeNode *current, TreeNode *parent, char value)
{
    if (current == NULL) {
        TreeNode *newNode = new TreeNode;
        newNode->value = value;
        newNode->count = 1;
        newNode->left = newNode->right = NULL;
        if(parent->value > newNode->value)
            parent->left = newNode;
        else
            parent->right = newNode;
    }
    else if (current->value > value)
        insert(current->left, current, value);
    else
        insert(current->right, current, value);
}

在这里，我正在考虑您希望字符串的第一个字符作为二叉树的根。我不明白你为什么要为每个角色创建一个新节点。此外，您也不需要将指针的引用传递给函数，因为您在任何时候都不会修改指针。而且，我将 2 个变量传递给 insert 函数，因为您要插入到树中，所以您需要引用父指针。希望这能有所帮助！

C++ 二叉树

C++ Binary Tree

c++

binary-tree