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

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

Восстановить пароль Регистрация
 
KateHamgeN
 Аватар для KateHamgeN
0 / 0 / 0
Регистрация: 25.09.2009
Сообщений: 15
02.04.2011, 21:36     Высота n-нарного дерева #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);
    }       
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.04.2011, 21:36     Высота n-нарного дерева
Посмотрите здесь:

C++ Ширина и высота окна консольного приложения(VS 2010)
Ширина (высота) окна winapi C++
Высота конуса C++
C++ Вывод бинарного дерева на экран в виде "дерева"
Высота авл дерева - как считать? C++
Даны основание и высота равнобедренной трапеции, найти периметр (ошибка) C++
Написать шаблон бинарного дерева с функцией распечатки дерева C++
C++ Высота бинарного дерева

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Mr.X
Эксперт С++
 Аватар для Mr.X
2802 / 1578 / 247
Регистрация: 03.05.2010
Сообщений: 3,666
03.04.2011, 01:05     Высота n-нарного дерева #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;
}
Yandex
Объявления
03.04.2011, 01:05     Высота n-нарного дерева
Ответ Создать тему
Опции темы

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