Форум программистов, компьютерный форум, киберфорум
C для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.52/29: Рейтинг темы: голосов - 29, средняя оценка - 4.52
0 / 0 / 0
Регистрация: 16.12.2015
Сообщений: 45
1

В бинарном дереве найти длину (число ветвей) пути от корня до ближайшей вершины

03.04.2016, 22:44. Показов 6009. Ответов 3
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
В заданном непустом бинарном дереве найти длину (число ветвей) пути от корня до ближайшей вершины со значением, равным заданному. Использовать алгоритм обратного обхода.
Надеюсь, сможете помочь, собственно, с написанием алгоритма для нахождения длины пути. Все остальное написала, но здесь- я в тупике, было несколько идей, но что-то пошло не так.
Заранее благодарна
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
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
 
struct btree {
    btree() :e(), l(), r() {}
    int e;
    btree *l, *r;
};
 
struct list {
    btree *z;
    list *next;
};
typedef list stack;
 
stack *iinput(btree *x, stack *head) {//добавление элемента в стек
    stack *s;
    s = new list;
    s->z = x;
    s->next = head;
    head = s;
    return head;
}
 
btree *gget(stack **head) {//взятие элемента из стека
    btree *x = (*head)->z;
    stack *g = (*head)->next;
    *head = NULL;
    *head = g;
    return x;
}
 
void add(btree **t, int value){//ввод дерева
    if (*t == NULL) {
        *t = new btree;
        (*t)->e = value;
    }
    else  {
        btree *t2 = *t;
        while (t2 != NULL)  {
            if (t2->e < value)  { //Направо 
                if (t2->r == NULL)  {
                    t2->r = new btree;
                    t2->r->e = value;
                    t2 = NULL;  }
                else  {
                    t2 = t2->r; }   }
            else{ //Налево 
                if (t2->l == NULL)  {
                    t2->l = new btree;
                    t2->l->e = value;
                    t2 = NULL;  }
                else  {
                    t2 = t2->l;
}}}}}
 
void obh(btree *d) {//вычисление длины пути до ближайшей вершины с подходящим значением
    stack *S = NULL; int F = 1, x;
    printf("zadaite zna4enie  \n");
    scanf("%d", &x);
    while (F){
        while (d != NULL) {
            S = iinput(d, S);
            d = d->l;
        } 
        if (S != NULL) { 
            d = gget(&S);
 
//добавить действия
 
            d = d->r;
        }
        else F = 0;
    }
    printf("dlina puti= %d \n", p);
}
 
int main(){
    int x;
    btree *T = NULL;
    printf("vvedite derevo \n");
    while ((_kbhit() == 0) && (_getch() != 27)) {
        scanf("%d", &x);
        add(&T, x);
    }
    printf("okon4en vvod dereva \n");
    obh(T);
    _getch();
}
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
03.04.2016, 22:44
Ответы с готовыми решениями:

Найти длину пути от корня до ближайшей вершины с заданным количеством появлений слова в тексте
Здравствуйте, можете разъяснить, как правильно работать с бинарным деревом, как его можно применить...

Как найти количество ветвей в бинарном дереве
Имеется глубина бинарного дерева. Под глубиной подразумевается количество узлов в самом длинном...

Разработать программу, которая находит в непустом дереве Т длину (число ветвей)
Разработать программу, которая находит в непустом дереве Т длину (число ветвей) пути от корня до...

Перечислить вершины в бинарном дереве, находящиеся на заданном уровне
Перечислить вершины в бинарном дереве, находящиеся на заданном уровне

3
Модератор
Эксперт PythonЭксперт JavaЭксперт CЭксперт С++
12456 / 7480 / 1753
Регистрация: 25.07.2009
Сообщений: 13,759
03.04.2016, 23:58 2
Лучший ответ Сообщение было отмечено Памирыч как решение

Решение

Saky, на всякий случай: код у Вас на С++, раздел С. Если это не смущает, один из возможных вариантов закладываясь на то, что высота дерева меньше |INT_MIN|
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <limits.h>
 
int path_length(btree* root, int needed) {
    if ( ! root ) // значение не найдено
        return INT_MIN;
    if ( root->e == needed )
        return 0;
    return 1 + path_length( ( (root->e > needed ) ? root->l : root->r), needed);
}
 
/*...*/
// где-то в программе 
int len, needed;
btree* root;
//...
if ( ( len = path_length(root, needed) ) < 0 )
  // не найдено
else
  // в len длина пути
0
Вездепух
Эксперт CЭксперт С++
11691 / 6370 / 1723
Регистрация: 18.10.2014
Сообщений: 16,053
04.04.2016, 02:31 3
Цитата Сообщение от Saky Посмотреть сообщение
if (t2->e < value)* { //Направо
В условии не сказано, что дерево как-то упорядочено. Вы же в своем коде пытаетесь организовывать и использовать упорядоченность дерева.

Так упорядочено дерево или нет?
0
0 / 0 / 0
Регистрация: 16.12.2015
Сообщений: 45
05.04.2016, 07:45  [ТС] 4
easybudda
Нужно обязательно воспользоваться обратным обходом дерева (его я описала в "obh"), добавив к нему действия.
TheCalligrapher
Решение не должно основываться на его упорядоченности, но задать можно так.
0
05.04.2016, 07:45
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
05.04.2016, 07:45
Помогаю со студенческими работами здесь

Трассировка пути в бинарном дереве
Добрый вечер. Ум за разум заходит уже. Прошу помощи. Реализовал нахождение максимального пути в...

Для графа дерева найти длину пути от вершины U до V (использовать поиск в глубину и счётчик глубины рекурсии WG)
помоги, пожалуйста, нужна программа:wall: Для графа дерева найти длину пути от вершины U до V ...

Определить число ветвей в дереве
Описать процедуру или функцию, которая: a) находит в непустом дереве Т длину (число...

В бинарном дереве подсчитать число его листов
В бинарном дереве подсчитать число его листов и напечатать их значения: при прямом обходидерева.

Найти все вершины графа, к которым от заданной вершины можно добраться по пути не длиннее А
Найти все вершины графа, к которым от заданной вершины можно добраться по пути не длиннее А....

Как в бинарном дереве у всех листьев вычесть введенное число?
вот кусок int main(void) { /* Первоначально дерево пусто*/ sNode *root = NULL; int...


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

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru