Форум программистов, компьютерный форум CyberForum.ru

Копирование бинарного дерева - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 29, средняя оценка - 4.86
patriot2008
 Аватар для patriot2008
70 / 70 / 4
Регистрация: 04.12.2008
Сообщений: 463
28.12.2010, 14:45     Копирование бинарного дерева #1
Имеется бинарное дерево типа
C++
1
2
3
4
5
6
7
8
9
class TreeNode 
{
public:
    TreeNode(); //конструктор
    virtual ~TreeNode();    //деструктор
    TreeNode  *left;    //указатель на левое поддерево
    TreeNode  *right;   //указатель на правое поддерево
    int data;   //информационное поле
};
Также имеется класс для работы с деревом
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class SearchTree
{
public:
    SearchTree();   //конструктор по умолчанию
    ~SearchTree();  //деструктор
    TreeNode* CreateNode(int val);  //создание элемента (листка) дерева
    void Copy(TreeNode*  src, TreeNode* tg);    //копирование одного дерева в другое (функций 
    TreeNode *root; //указатель на корень дерева
};
 
//создание нового элемента дерева
TreeNode* SearchTree::CreateNode(int val)
{
    TreeNode* nd = new TreeNode(val);
    return nd;
}
 
void SearchTree::Copy(TreeNode* src, TreeNode* tg)
{
    if(src == NULL)
        tg = NULL;
    //проход, пока исходное дерево не достигло конца
    if (src != NULL) 
    {
        //создание нового элемента дерева
        tg = CreateNode(src->data);
        if(src->left != NULL)
        {
            Copy(src->left,tg->left);
        }
        else
            tg->left = NULL;
        
        if(src->right != NULL)
        {
            Copy(src->right,tg->right);
        }
        else
            tg->right = NULL;
    }
}
Так вот: проблема вся в том, что метод копирования дерева корректно не работает. Теоретически все вроде верно, находил кучу алгоритмов и примеров решения, все сходится. Но на самом деле - не создает копию дерева. Прогонял через отладчик - тоже ничего не нашел. В чем может быть проблема?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.12.2010, 14:45     Копирование бинарного дерева
Посмотрите здесь:

C++ Обход бинарного дерева
C++ Шаблон бинарного дерева
C++ Построение бинарного дерева на основе не бинарного
C++ Вывод бинарного дерева
Построение бинарного дерева C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
kukuruku310
197 / 184 / 6
Регистрация: 14.02.2010
Сообщений: 538
29.12.2010, 00:30     Копирование бинарного дерева #2
А где у Вас вообще копирование? Я так понимаю, что скопировать надо не только поле ID, но и левых/правых потомков, а у Вас вообще нигде нет присваивания элементам right и left чего-то кроме нуля. Да, честно говоря, даже присваивания ID не заметил, т.к. тело Вашего конструктора узла не приведено. Или приведен как-то непонятно усеченный код, или то, что написано вообще неработоспособно.
patriot2008
 Аватар для patriot2008
70 / 70 / 4
Регистрация: 04.12.2008
Сообщений: 463
29.12.2010, 01:01  [ТС]     Копирование бинарного дерева #3
Точно! Нет присваивания поддеревьям, которые копируем. А не подскажите, как это правильно организовать, чтобы также все рекурсивно осталось?

Вот само тело конструктора
C++
1
2
3
4
5
6
TreeNode::TreeNode( int d )
{
    data=d;
    left=NULL;
    right = NULL;
}
P.S.: Просто решение то было найдено другим путем, но все же интересно, как это возможно осуществить именно этим методом.
Надеюсь на Вашу помощь.
kukuruku310
197 / 184 / 6
Регистрация: 14.02.2010
Сообщений: 538
29.12.2010, 18:38     Копирование бинарного дерева #4
Так я себе это представляю
Млин, не то подцепил, как удалить не знаю, короче Ваш - tree.rar
Вложения
Тип файла: rar 123.RAR (4.0 Кб, 59 просмотров)
Тип файла: rar Tree.rar (3.3 Кб, 367 просмотров)
Yandex
Объявления
29.12.2010, 18:38     Копирование бинарного дерева
Ответ Создать тему
Опции темы

Текущее время: 17:16. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru