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

Несбалансированное бинарное дерево с рекурсивным обходом в обратном порядке - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.93
cop
0 / 0 / 0
Регистрация: 10.03.2010
Сообщений: 67
24.06.2011, 21:20     Несбалансированное бинарное дерево с рекурсивным обходом в обратном порядке #1
добрый день. помогите пожалуйста с реализацией кода:
.Несбалансированное бинарное дерево с рекурсивным обходом в обратном порядке (левое поддерево – правое поддерево – узел).
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.06.2011, 21:20     Несбалансированное бинарное дерево с рекурсивным обходом в обратном порядке
Посмотрите здесь:

Бинарное дерево C++
C++ Бинарное дерево с прямым обходом
Бинарное дерево C++
Бинарное дерево C++
Бинарное дерево C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
kravam
быдлокодер
 Аватар для kravam
1512 / 872 / 44
Регистрация: 04.06.2008
Сообщений: 5,270
24.06.2011, 21:57     Несбалансированное бинарное дерево с рекурсивным обходом в обратном порядке #2
Это чё, формулировка так стоит?
cop
0 / 0 / 0
Регистрация: 10.03.2010
Сообщений: 67
24.06.2011, 22:00  [ТС]     Несбалансированное бинарное дерево с рекурсивным обходом в обратном порядке #3
Реализовать бинарное дерево с операциями добавления, поиска:
Несбалансированное бинарное дерево с рекурсивным обходом в обратном порядке (левое поддерево – правое поддерево – узел).
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
25.06.2011, 00:34     Несбалансированное бинарное дерево с рекурсивным обходом в обратном порядке #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
#include <stdio.h>
#include <stdlib.h>
 
typedef struct NODE {
    int val;
    struct NODE * left;
    struct NODE * right;
} node_t;
 
int add_node(node_t ** root, int val){
    if ( ! *root ){
        if ( ( *root = (node_t*)calloc(1, sizeof(node_t)) ) == NULL )
            return -1;
        (*root)->val = val;
        return 0;
    }
    else if ( (*root)->val > val )
        return add_node(&((*root)->left), val);
    else if ( (*root)->val < val )
        return add_node(&((*root)->right), val);
    else
        return 0;
}
 
void del_nodes(node_t ** root){
    if ( *root ){
        del_nodes(&((*root)->left));
        del_nodes(&((*root)->right));
        free(*root);
        *root = NULL;
    }
}
 
void print_ascendant(const node_t * root){
    if ( root ){
        print_ascendant(root->left);
        printf("%d ", root->val);
        print_ascendant(root->right);
    }
}
 
void print_descendant(const node_t * root){
    if ( root ){
        print_descendant(root->right);
        printf("%d ", root->val);
        print_descendant(root->left);
    }
}
 
node_t * find_value(const node_t * root, int val){
    return ( ! root ) ? NULL : ( root->val == val ) ? (node_t*)root : ( root->val > val ) ? find_value(root->left, val) : find_value(root->right, val);
}
 
int main(void){
    node_t * root = NULL;
    int toFind;
 
    add_node(&root, 5);
    add_node(&root, 3);
    add_node(&root, 7);
    add_node(&root, 2);
    add_node(&root, 1);
    add_node(&root, 6);
    add_node(&root, 4);
 
    printf("Ascendant:  ");
    print_ascendant(root);
    printf("\nDescendant: ");
    print_descendant(root);
    
    printf("\nValue to search: ");
    scanf("%d", &toFind);
    printf("Value %sfound.\n", ( find_value(root, toFind) ) ? "" : "not ");
 
    printf("Another value to search: ");
    scanf("%d", &toFind);
    printf("Value %sfound.\n", ( find_value(root, toFind) ) ? "" : "not ");
 
    system("pause");
    del_nodes(&root);
    return 0;
}
ValeryLaptev
Эксперт C++
1005 / 784 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
25.06.2011, 05:07     Несбалансированное бинарное дерево с рекурсивным обходом в обратном порядке #5
Цитата Сообщение от cop Посмотреть сообщение
добрый день. помогите пожалуйста с реализацией кода:
.Несбалансированное бинарное дерево с рекурсивным обходом в обратном порядке (левое поддерево – правое поддерево – узел).
Открываем книжку Вирта и читаем: это обратный порядок обхода дерева.
Рекурсивная процедура обхода - тривиальна:

C++
1
2
3
void postorder(node *t)
{ if(!t) { postorder(t.left); postorder(t.right); print(t); }
}
t - указатель на узел дерева.
Элемент дерева имеет структуру:
C++
1
2
3
4
5
struct node
{ info;     // - данные узла
   node *left;
   node *right;
};
Первый вызов:
C++
1
postorder(root);
где
C++
1
node *root;
корень дерева.
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
25.06.2011, 08:16     Несбалансированное бинарное дерево с рекурсивным обходом в обратном порядке #6
Цитата Сообщение от ValeryLaptev Посмотреть сообщение
...
Рекурсивная процедура обхода - тривиальна:

C++
1
2
3
void postorder(node *t)
{ if(!t) { postorder(t.left); postorder(t.right); print(t); }
}
Ну не на столько, на сколько кажется. Фактически у Вас при условии t == NULL происходит попытка обратиться к полям несуществующего объекта, то есть Null pointer exception (или как там её). Восклицательный знак перед t лишний.
ValeryLaptev
Эксперт C++
1005 / 784 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
25.06.2011, 08:36     Несбалансированное бинарное дерево с рекурсивным обходом в обратном порядке #7
easybudda, нет уж! Восклицательный - это важно. Ведь тут проверка:
если указатель не нуль, то делай то, что в скобочках. А иначе - ВОЗВРАТ из процедуры.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
25.06.2011, 09:30     Несбалансированное бинарное дерево с рекурсивным обходом в обратном порядке #8
Цитата Сообщение от ValeryLaptev Посмотреть сообщение
easybudda, нет уж! Восклицательный - это важно. Ведь тут проверка:
если указатель не нуль, то делай то, что в скобочках. А иначе - ВОЗВРАТ из процедуры.
C++
1
if (!t)
эквивалентно
C++
1
if (t == NULL)
так что кто-то не проснулся и пытается завалить программу доступом именно по нулевому указателю
ValeryLaptev
Эксперт C++
1005 / 784 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
25.06.2011, 18:14     Несбалансированное бинарное дерево с рекурсивным обходом в обратном порядке #9
Цитата Сообщение от grizlik78 Посмотреть сообщение
C++
1
if (!t)
эквивалентно
C++
1
if (t == NULL)
так что кто-то не проснулся и пытается завалить программу доступом именно по нулевому указателю
А, понял...
Конечно
C++
1
if(t)...
Все же в 4 утра я последний раз писал лет эдак 25 назад...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.06.2011, 13:17     Несбалансированное бинарное дерево с рекурсивным обходом в обратном порядке
Еще ссылки по теме:

Бинарное дерево C++
Бинарное дерево C++
C++ Бинарное дерево

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

Или воспользуйтесь поиском по форуму:
cop
0 / 0 / 0
Регистрация: 10.03.2010
Сообщений: 67
26.06.2011, 13:17  [ТС]     Несбалансированное бинарное дерево с рекурсивным обходом в обратном порядке #10
правильная реализация как будет выглядеть?тоесть сам код
Yandex
Объявления
26.06.2011, 13:17     Несбалансированное бинарное дерево с рекурсивным обходом в обратном порядке
Ответ Создать тему
Опции темы

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