Бинарные деревья

Question

Как скопировать данные с первого дерева в другое, и сортировать по годам. Первое дерево сортирует по имени. Код С++:

#include <iostream>
using namespace std;

struct TreeNode     //структура дерева
{
    string name;
    int year;
    int mark;
    TreeNode* Left;
    TreeNode* Right;
};

TreeNode* Create(string name, int year, int mark)   //создание нового узла
{
    TreeNode* t = new TreeNode;
    t->name = name;
    t->year = year;
    t->mark = mark;
    t->Left = nullptr;
    t->Right = nullptr;
    return t;
}

void AddName(string x, int year, int mark, TreeNode* v)//добавляет, сортируя по имени
{
    if (x <= v->name)
    {
        if (v->Left) AddName(x, year, mark, v->Left);
        else v->Left = Create(x, year, mark);
    }
    else
    {
        if (v->Right) AddName(x, year, mark, v->Right);
        else v->Right = Create(x, year, mark);
    }
}

void AddYear(string x, int year, int mark, TreeNode* v)//добавляет, сортируя по годам
{
    if (year <= v->year)
    {
        if (v->Left) AddYear(x, year, mark, v->Left);
        else v->Left = Create(x, year, mark);
    }
    else
    {
        if (v->Right) AddYear(x, year, mark, v->Right);
        else v->Right = Create(x, year, mark);
    }
}

void Show(TreeNode* v)  //вывод дерева
{
    if (v->Left) Show(v->Left);
    cout << v->name << "   " << v->year << "   " << v->mark << endl;
    if (v->Right) Show(v->Right);
}

void Copy(TreeNode* treeNew, TreeNode*& tree) //Функция копирования (не работает)
{
    if (tree->Left) Copy(tree->Left, treeNew);
    AddYear(tree->name, tree->year, tree->mark, treeNew);
    if (tree->Right) Copy(tree->Right, treeNew);
}

int NodesCount(TreeNode* v)//счетчик
{
    int c = 0;
    if (v->Left) c += NodesCount(v->Left);
    c++;
    if (v->Right) c += NodesCount(v->Right);
    return c;
}
void Delete(TreeNode*& v)//удаление
{
    if (v)
    {
        if (v->Left)
            Delete(v->Left);
        if (v->Right)
            Delete(v->Right);
        delete v;
        v = nullptr;
    }
}

int main()
{
    string name[10] = { "Sterling", "Shirl", "Deandrea", "Joe", "Lyle", "Doreen", "Solomon", "Elina", "Lita", "Nicholas"};
    int year[10] = { 2002, 2001, 2001, 1998, 2002, 2003, 2000, 1999, 2000, 2002 };
    int mark[10] = { 5,4,5,5,2,4,5,5,3,4 };

    TreeNode* tree = Create(name[0], year[0], mark[0]);     //создание первого дерева

    cout << "============SORTING BY NAME============="<< endl;
    for (int i = 1; i < 10; i++)
    {
        AddName(name[i], year[i], mark[i], tree);
    }
    Show(tree);
    cout << endl;

    TreeNode* tree1 = Create(tree->name, tree->year, tree->mark); // создание второго дерева
    cout << "===========SORTING BY YEAR===============" << endl;
    for (int i = 1; i < 10; i++)
    {
        Copy(tree1, tree);
    }
    Show(tree1);
    cout << endl;

    Delete(tree);
    Delete(tree1);

    return 0;
}

Answer 1

Вы перепутали аргументы, то новое дерево как первый аргумент, то как второй. А в рекурсивном вызове в левую/правую ветку копируете всё дерево, вместо этих веток. Помогает константность, чтобы не путаться.

Создавать новый узел TreeNode можно внутри функции, а не в main. Так будет проще и понятнее.

void Copy(TreeNode * & treeNew, TreeNode const * const tree ) {
  // если узел конечный
  if ( tree == nullptr ) {
    treeNew = nullptr ;
    return ; }
  // если с данными
  treeNew = Create(tree->name, tree->year, tree->mark);
  // рекурсия влево
  Copy(treeNew->Left, tree->Left);
  // рекурсия вправо
  Copy(treeNew->Right, tree->Right);
}

В функции main вы десять раз делаете копию дерева. Не видно в этом цикле никакого смысла. Пусть этим делом займётся функция Copy.

Неправильно
 TreeNode* tree1 = Create(tree->name, tree->year, tree->mark);
 // создание второго дерева
 cout << "===========SORTING BY YEAR===============" << endl;
 for (int i = 1; i < 10; i++)
 {
    Copy(tree1, tree);
 }
Неправильно

Делаем копию правильно :

TreeNode* tree1 ;
Copy(tree1, tree ) ;

БЛОГ НА HUSL

Бинарные деревья

Ответы (1 шт):