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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
MILAN
 Аватар для MILAN
883 / 777 / 86
Регистрация: 21.02.2009
Сообщений: 1,722
#1

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

14.09.2010, 23:14. Просмотров 720. Ответов 4
Метки нет (Все метки)

Здраствуйте. Есть такое задание: Два бинарных дерева дзеркально подобные, если либо оба они пустые, либо оба не пустые, и при етом левое поддерево одного с них подобное правому поддереву другого, и наоборот. Опредилить, есть ли два дерева дзеркально подобними.

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

C++ Определить являются ли два целых числа взаимно простыми ,если числа имеют общие делители
опредилить общую стоимость C++
C++ ввести с клавиатуры два числа, узнать являются ли они соседними по коду Грея
C++ Даны два натуральных числа. Определить сколько чисел на отрезке между ними являются факториалами
C++ Заданы два человека – p и q. Ответить, являются ли они родственниками
Ввести с клавиатуры два слова. Проверить, являются ли они анаграммами C++
Рекурсивно и нерекурсивно описать логическую функцию, проверяющую на равенство два бинарных дерева C++
C++ Являются ли два массивы похожими?
Проверить истинность высказывания: «Ровно два из чисел A, B, C являются положительными» C++
Проверить на эквивалентность два AVL-дерева C++
C++ Определить, являются ли два заданных числа дружными
Определить, являются ли два заданных натуральных числа взаимно простыми C++

Искать еще темы с ответами

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

Добавлено через 9 часов 39 минут
Неужели никто не имел дело с деревьями?
Mr.X
Эксперт С++
 Аватар для Mr.X
3021 / 1677 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
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     Опредилить, являются ли два дерева зеркально подобнымм
Ответ Создать тему
Опции темы

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