C++ Binary Tree

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 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() 
{ 
    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

Вам просто нужно изменить структуру структуры 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, так как yo вставить в дерево, вам нужно иметь ссылку на родительский указатель. Надеюсь, это поможет!