C++ 在二叉树中存储文件

Question

我正在完成一个 C++ 项目，在该项目中我将文本文件作为字符串读取并将其存储在二叉树中。我必须将文件中的每个字母连同该字母出现的次数一起存储在二叉树中。然后我必须存储 2 个字母出现，依此类推到用户给出的 k 次出现。例如，如果一个文件包含 abcdef，我必须在树中存储 a、b、c、d、e、f，然后我再次遍历该字符串并存储 ab、bc、cd、de、ef 和 abc、bcd， cde、def 等，直到用户输入的数字为止。这些存储有它们出现的次数，如果一个字符串曾经传递给树并且树已经包含该字符串，则该字符串的数量简单地增加一个。我的代码适用于单次和两次出现，但对于大于 2 次的出现，它总是将最后一次两次出现传递给树两次。

这是 main.cpp 文件：

#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include "binarytree.h"
using namespace std;

int main()
{
    string filename;
    string filedata;
    string a;
    string b;
    int num;
    BinaryTree tree;
    fstream file;

    cout << "Please enter a filename: ";
    cin >> filename;

    file.open(filename.c_str(), ios::in);

    if (!file)
    {
    cout << "ERROR: Cannot open file.";
    }

    else
    {
        cout << "Please enter the maximum number of consecutive letters to count the occurrences of: ";
        cin >> num;

        while (num < 1)
        {
            cout << "Please enter a number greater than 0: ";
            cin >> num;
        }
    }

    while (getline(file, a))
    {
        filedata += a;
    }

    cout << "File data: " << filedata << endl;
    filedata.erase(remove(filedata.begin(),filedata.end(),' '),filedata.end());
    cout << "File data: " << filedata << endl;

    for (unsigned int i = 0; i < filedata.size(); i++)
    {
        if (filedata[i] != ' ')
        {
            string a(1, filedata[i]);
            tree.insertNode(a);
        }
    }

    if (num > 1)
    {
        for (int i = 2; i < num + 1; i++)
        {
            int k = 1;
            for (unsigned int j = 0; j < filedata.size()-1; j++)
            {
                if (filedata[j+k] == '[=10=]')
                    cout << "null" << endl;
                else if (filedata[j+k] != '[=10=]')
                {
                    b = "";
                    b += filedata.substr(j, i);
                    tree.insertNode(b);
                }
            }
            k++;
        }
    }

    file.close();

    tree.displayInOrder();

    return 0;
}

这是 binarytree.cpp 文件：

#include <iostream>
#include <cstdlib>
#include "binarytree.h"
using namespace std;

void BinaryTree::insert(TreeNode *&nodePtr, TreeNode *&newNode, string letter)
{

    if (nodePtr == NULL)
    {
        TreeNode *newTreeNode = new TreeNode;
        newTreeNode->letter = letter;
        newTreeNode->value = 1;
        newTreeNode->left = newTreeNode->right = NULL;
        if(newNode->letter > newTreeNode->letter)
            newNode->left = newTreeNode;
        else
            newNode->right = newTreeNode;
    }
    else if (nodePtr->letter > letter)
        insert(nodePtr->left, nodePtr, letter);
    else if (nodePtr->letter < letter)
        insert(nodePtr->right, nodePtr, letter);
    else if (nodePtr->letter == letter)
        nodePtr->value += 1;
}

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

void BinaryTree::destroySubTree(TreeNode *nodePtr)
{
    if (nodePtr)
    {
        if (nodePtr->left)
            destroySubTree(nodePtr->left);
        if (nodePtr->right)
            destroySubTree(nodePtr->right);
        delete nodePtr;
    }
}

void BinaryTree::displayInOrder(TreeNode *nodePtr) const
{
    if (nodePtr)
    {
        displayInOrder(nodePtr->left);
        cout << nodePtr->letter << ": " << nodePtr->value << endl;
        displayInOrder(nodePtr->right);
    }
}

这是 binarytree.h 文件：

#include <iostream>
#include <string>
#ifndef BINARYTREE_H_
#define BINARYTREE_H_
using namespace std;

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

        TreeNode *root;

        void insert(TreeNode *&, TreeNode *&, string);
        void destroySubTree(TreeNode *);
        void deleteNode(int, TreeNode *&);
        void makeDeletion(TreeNode *&);
        void displayInOrder(TreeNode *) const;

    public:
        BinaryTree()
        {
            root = NULL;
        }
        ~BinaryTree()
        {
            destroySubTree(root);
        }
        void insertNode(string);
        void remove(int);
        void displayInOrder() const
        {
            displayInOrder(root);
        }
};

#endif

这是文本文件：

j a z uu e uu a

当在程序中输入文本文件以及出现次数 num 3 时，屏幕上会显示：

一：2 阿兹：1 阿祖：1 电子：1 欧盟：1 欧盟：1 j: 1 贾：1 爵士乐：1 你：4 美国：2 UE：1 UEU：1 你：2 乌阿：1 uue: 1 z: 1 祖：1 zuu: 1 //（每行一个）

如您所见，ua 在本应只计算一次的情况下被计算了两次。这仅在 num > 2 时发生。问题出在 if(num > 1) 语句中的某处。我试图避免将 null 字符传递给树，并且我添加了一个 cout 语句来显示 "null" 如果达到 null 但这从未显示过，我不确定是什么导致了问题。

感谢您的帮助。

Answer 1

这个循环有问题：for (unsigned int j = 0; j < filedata.size()-1; j++)。

这不能保证所有插入的元素的大小都是 i。

如果将其替换为 for (unsigned int j = 0; j < filedata.size()-i+1; j++)，则 j 将上升到长度为 i 的字符串的最后一个索引，这就是您要查找的内容。

C++ 在二叉树中存储文件

C++ Storing File in Binary Tree

c++

string

binary-tree