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

Опредилить, являются ли два дерева зеркально подобнымм - C++

Восстановить пароль Регистрация
 
MILAN
 Аватар для MILAN
883 / 777 / 86
Регистрация: 21.02.2009
Сообщений: 1,722
14.09.2010, 23:14     Опредилить, являются ли два дерева зеркально подобнымм #1
Здраствуйте. Есть такое задание: Два бинарных дерева дзеркально подобные, если либо оба они пустые, либо оба не пустые, и при етом левое поддерево одного с них подобное правому поддереву другого, и наоборот. Опредилить, есть ли два дерева дзеркально подобними.

Подскажите алгоритм, потому как вообще никогда не имел дело с деревьями, или литературу чтоб разобраться. Заранее благодарен!!!!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.09.2010, 23:14     Опредилить, являются ли два дерева зеркально подобнымм
Посмотрите здесь:

C++ ввести с клавиатуры два числа, узнать являются ли они соседними по коду Грея
C++ Заданы два человека – p и q. Ответить, являются ли они родственниками
Ввести с клавиатуры два слова. Проверить, являются ли они анаграммами C++
Построение идеально сбалансированного дерева, значения читаются из текстового файла C++
Рекурсивно и нерекурсивно описать логическую функцию, проверяющую на равенство два бинарных дерева C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
asics
Freelance
Эксперт C++
 Аватар для asics
2838 / 1775 / 144
Регистрация: 09.09.2010
Сообщений: 3,842
14.09.2010, 23:54     Опредилить, являются ли два дерева зеркально подобнымм #2
Посмтори,может пригодитсо.
Вложения
Тип файла: rar Деревья.rar (3.7 Кб, 30 просмотров)
MILAN
 Аватар для MILAN
883 / 777 / 86
Регистрация: 21.02.2009
Сообщений: 1,722
15.09.2010, 10:10  [ТС]     Опредилить, являются ли два дерева зеркально подобнымм #3
Может у кого еще есть какая инфа?

Добавлено через 9 часов 39 минут
Неужели никто не имел дело с деревьями?
Mr.X
Эксперт С++
 Аватар для Mr.X
2801 / 1577 / 247
Регистрация: 03.05.2010
Сообщений: 3,666
15.09.2010, 11:39     Опредилить, являются ли два дерева зеркально подобнымм #4
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
///////////////////////////////////////////////////////////////////////////////////
//  Есть такое задание: Два бинарных дерева дзеркально подобные, 
//  если либо оба они пустые, либо оба не пустые, и при етом левое поддерево 
//  одного с них подобное правому поддереву другого, и наоборот. 
//  Опредилить, есть ли два дерева дзеркально подобними.
///////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <vector>
 
typedef std::vector<int>  T_inums;
///////////////////////////////////////////////////////////////////////////////////
struct T_node
{
    int      data;
    T_node*  left;
    T_node*  right;
};
///////////////////////////////////////////////////////////////////////////////////
void make_node(T_node*& rp_node, int val)
{
    rp_node         = new T_node;
    rp_node->data   = val;
    rp_node->left   = 0;
    rp_node->right  = 0;
}
///////////////////////////////////////////////////////////////////////////////////
void sort_insert(T_node*& rp_tree, int val)
{   
    if(rp_tree == 0)
    {
        make_node(rp_tree, val);        
    }
    else if(val < rp_tree->data)
    {        
        sort_insert(rp_tree->left, val);
    }
    else
    {
        sort_insert(rp_tree->right, val);
    }
}
///////////////////////////////////////////////////////////////////////////////////
void sort_insert(T_node*&  rp_tree, T_inums  inums)
{
    for(T_inums::const_iterator  it = inums.begin(); it != inums.end(); ++it)
    {
        sort_insert(rp_tree, *it);
    }
}
///////////////////////////////////////////////////////////////////////////////////
void reverse_sort_insert(T_node*&  rp_tree, int val)
{
    if(rp_tree == 0)
    {
        make_node(rp_tree, val);        
    }
    else if(val < rp_tree->data)
    {
        reverse_sort_insert(rp_tree->right, val);
    }
    else
    {
        reverse_sort_insert(rp_tree->left, val);
    }
}
///////////////////////////////////////////////////////////////////////////////////
void reverse_sort_insert(T_node*&  rp_tree, T_inums  inums)
{
    for(T_inums::const_iterator  it = inums.begin(); it != inums.end(); ++it)
    {
        reverse_sort_insert(rp_tree, *it);
    }
}
///////////////////////////////////////////////////////////////////////////////////
bool are_specularly_similar(T_node*  p_treeA, T_node*  p_treeB)
{
    if(p_treeA == 0 && p_treeB == 0)
    {
        return true;
    }
    if(p_treeA == 0 || p_treeB == 0)
    {
        return false;
    }
    if(p_treeA->data != p_treeB->data)
    {
        return false;
    }
    return    are_specularly_similar(p_treeA->left, p_treeB->right)
           && are_specularly_similar(p_treeA->right, p_treeB->left);
 
}
///////////////////////////////////////////////////////////////////////////////////
int main()
{    
    T_inums  inums;
    inums.push_back(2);
    inums.push_back(7);
    inums.push_back(1);
    inums.push_back(8);
    inums.push_back(2);
        
    T_node*  p_tree_l = 0;
    sort_insert(p_tree_l, inums);
    
    T_node*  p_tree_r = 0;
    reverse_sort_insert(p_tree_r, inums);
 
    if(are_specularly_similar(p_tree_l, p_tree_r))    
    {
        std::cout << "Are specularly similar tree_l and tree_r.";
    }
    else
    {
        std::cout << "Are NOT specularly similar tree_l and tree_r.";
    }
 
    std::cout << std::endl;
 
    if(are_specularly_similar(p_tree_l, p_tree_l))    
    {
        std::cout << "Are specularly similar tree_l and tree_l.";
    }
    else
    {
        std::cout << "Are NOT specularly similar tree_l and tree_l.";
    }
 
    std::cout << std::endl;
    return 0;
}
MILAN
 Аватар для MILAN
883 / 777 / 86
Регистрация: 21.02.2009
Сообщений: 1,722
15.09.2010, 22:03  [ТС]     Опредилить, являются ли два дерева зеркально подобнымм #5
Спасибо, но если вас не затруднит, дайте несколько коментарий!!!

Добавлено через 9 часов 21 минуту
Может кто посоветует литературу по даной теме для чайника?
Yandex
Объявления
15.09.2010, 22:03     Опредилить, являются ли два дерева зеркально подобнымм
Ответ Создать тему
Опции темы

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