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

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

Войти
Регистрация
Восстановить пароль
 
KateHamgeN
0 / 0 / 0
Регистрация: 25.09.2009
Сообщений: 15
#1

Высота n-нарного дерева - C++

02.04.2011, 21:36. Просмотров 856. Ответов 1
Метки нет (Все метки)

Подскажите алгоритм нахождения высоты n-нарного дерева, я написала, но высота находится не всегда точно. Не знаю как избежать этого.
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
struct tree
    {
        int k; //элемент дерева
        int kol_child; //количество потомков
        tree **child;
    };
    tree *root=NULL; //корень дерева
    int *n=new int[5]; //допустим пять ветвей в дереве
    for (int i=0;i<5;i++)
        n[i]=0;
    cout<<visota_root(root,n,0);
 
int visota_root (tree *p,int *n,int i)
{
    if  (!p) 
        return (0); 
    else
    {   
        for (i=0;i<p->kol_child;i++)
                n[i]=visota_root(p->child[i],n,i);
        if (n[i]>=n[0])
            return (n[i]+1);
        else
            return (n[0]+1);
 
    }       
}
Добавлено через 12 минут
еще вот так пробовала, но безполезно:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int visota (tree *p,tree *p_root,int n,int m) 
{
    if  (!p) 
        return (0); 
    else
    {   
        for (int i=0;i<p->kol_child;i++)
        {
            m=i+1;
            n=visota(p->child[i],p_root,n,m);
        }
        if (p==p_root || m==1 || n==0)
            return (n+1);
        else 
            return (n);
    }       
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.04.2011, 21:36
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Высота n-нарного дерева (C++):

Высота бинарного дерева - C++
Надо найти высоту бинарного дерева.

Высота авл дерева - как считать? - C++
Добрый вечер. Забавно. Предположим, что пустой указатель равен -1, высота пр - высота лев. А как посчитать высоту авл дерева с...

Высота бинарного дерева поиска - C++
Что неправильно в программе? Полное условие #include &lt;iostream&gt; #include &lt;cstdio&gt; #pragma comment (linker,...

Запись бинарного дерева в файл и восстановление из него этого дерева - C++
Задача такая: есть бинарное дерево. Каждый элемент дерева содержит 3 указателя - 1 указатель на структуру с данными, 2 и 3й указатель на...

Написать шаблон бинарного дерева с функцией распечатки дерева - C++
Не понимаю, что от меня хотят. Дано такое задание: Написать шаблон бинарного дерева с функцией распечатки дерева *(+(d,e),c) в виде...

Вывод бинарного дерева на экран в виде "дерева" - C++
основная задача: подсчет количества листьев. проблема: при просмотре хочу выводить бин. дерево, в красивом виде, возможно использование...

1
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
03.04.2011, 01:05 #2
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
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <iostream>
#include <vector>
/////////////////////////////////////////////////////////////////////////////////////////
template<size_t  N>
struct  T_node
{
    static const size_t  CHILDREN_TOTAL_MAX = N;
    //-----------------------------------------------------------------------------------
    typedef std::vector<T_node<N>*>  T_p_children;
    //-----------------------------------------------------------------------------------
    int           val_;
    T_p_children  p_children_;
    //-----------------------------------------------------------------------------------
    T_node(int  val) 
        : val_         (val),
          p_children_  (CHILDREN_TOTAL_MAX, 0)
    {}
    //-----------------------------------------------------------------------------------
    bool  add_child(T_node&  node)
    {
        T_p_children::iterator  zero_p_it 
            = std::find(p_children_.begin(), p_children_.end(), static_cast<T_node<N>*>(0));    
        bool  bool_res = zero_p_it != p_children_.end();
        if(bool_res)
        {
            *zero_p_it = &node;
        }
        return  bool_res; 
    }
    //-----------------------------------------------------------------------------------
    size_t  tree_height()
    {
        size_t  child_heght_max = 0;
        for(T_p_children::iterator  p_child_it = p_children_.begin();
            p_child_it != p_children_.end(); ++p_child_it)
        {
            if(*p_child_it == 0) continue;
            size_t  cur_child_heght = (*p_child_it)->tree_height();
            if(cur_child_heght > child_heght_max)
            {
                child_heght_max = cur_child_heght;
            }
        }
        return  1 + child_heght_max;
    }
};
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    typedef T_node<4>  T_node_4;
    T_node_4  tree(1);
    T_node_4  a(2);
    T_node_4  b(3);
    T_node_4  c(4);
    T_node_4  d(5);
 
    std::cout << "Высота дерева равна "
              << tree.tree_height()
              << "."
              << std::endl;
 
    tree.add_child(a);   
    tree.add_child(b);    
 
    std::cout << "Высота дерева равна "
              << tree.tree_height()
              << "."
              << std::endl;
 
    a.add_child(c);
    a.add_child(d);
 
    std::cout << "Высота дерева равна "
              << tree.tree_height()
              << "."
              << std::endl;
}
2
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.04.2011, 01:05
Привет! Вот еще темы с ответами:

Высота конуса - C++
Построить график зависимости расстояния от водной поверхности до верхней точки плавающего на воде тела от плотности материала данного тела,...

Ширина (высота) окна winapi - C++
Подскажите как узнать ширину (высоту) окна?

Ширина и высота окна консольного приложения(VS 2010) - C++
Всем привет. Подскажите как настроить высоту и ширину консольного окошка. Это то, которое открывается при нажатии кнопочки &quot;Запуск с...

Даны основание и высота равнобедренной трапеции, найти периметр (ошибка) - C++
1&gt;d:\учеба\2 семестр\с++\л1\задание3\задание3\исходный код.cpp(20): warning C4551: в вызове функции отсутствует список аргументов ...


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

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