Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.83/6: Рейтинг темы: голосов - 6, средняя оценка - 4.83
0 / 0 / 0
Регистрация: 29.03.2016
Сообщений: 3
1

Подсчитать количество листьев дерева не на последнем уровне, имеющем листья.

29.03.2016, 15:44. Просмотров 1112. Ответов 3
Метки нет (Все метки)

Добрый день!
Не могу разобраться со следующим: нужно подсчитать количество листьев не на последнем уровне, имеющем листья.
Текст программы, генерирующий дерево приведен ниже, обход дерева в глубину, дерево троичное.

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
132
133
134
135
136
137
138
139
140
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
 
//Класс узел дерева
class Node {char d;
    Node *lft; //левый сын
    Node *mdl; //средний сын
    Node *rgt; //правый сын
public:
    Node(): lft(NULL), mdl(NULL), rgt(NULL){} //конструктор узла
    ~Node(){if(lft) delete lft; //деструктор
    if(mdl) delete mdl;
    if(rgt) delete rgt;}
friend class Tree; //дружественный класс дерево
};
//класс дерево
class Tree
{
    Node *root; //указатель на корень дерева
    char num, maxnum; //счетчик тегов и максимальный тег
    int maxrow, offset; //максимальная глубина, смещение корня
    char **SCREEN; //память для выдачи на экран
    void clrscr(); //очистка рабочей памяти
    Node *MakeNode(int depth);// создание поддерева
    void OutNodes(Node *v, int r, int c); //выдача поддерева
    Tree(const Tree&); //фиктивный конструктор копии
    Tree operator=(const Tree&) const; //фиктивное присваивание
public:
    Tree(char num, char maxnum, int maxrow);
    ~Tree();
    void MakeTree() //ввод - генерация дерева
    {
        root=MakeNode(0);
    }
    bool exist(){return root!=NULL;} //проверка - дерево не пусто?
    int DFS(); //обход дерева
    void OutTree(); //выдача на экран
};
Tree::Tree(char nm, char mnm, int mxr):
    num(nm), maxnum(mnm), maxrow(mxr), offset(40), root(NULL),
    SCREEN(new char* [maxrow])
    {
        for(int i=0; i<maxrow; i++) SCREEN[i]=new char[80];
    }
Tree::~Tree()
{
    for(int i=0; i<maxrow; i++) delete []SCREEN[i];
    delete []SCREEN;
    delete root;
}
//функция-член для генерации случайного дерева
Node* Tree::MakeNode(int depth)
{
    Node* v=NULL;
    int Y=(depth<rand()%6+1)&&(num<='z');
    //cout<<"Node("<<num<<','<<depth<<")1/0:"; cin>>Y;
    if(Y){//создание узла, если Y=1
        v=new Node;
        v->lft=MakeNode(depth+1);
        v->d=num++;
        v->mdl=MakeNode(depth+1);
        v->rgt=MakeNode(depth+1);
        }
    return v;
}
void Tree::OutTree()
{
    clrscr();
    OutNodes(root, 1, offset);
    for(int i=0; i<maxrow; i++){
        SCREEN[i][79]=0;
    cout<<'\n'<<SCREEN[i];
}
cout<<'\n';
}
void Tree::clrscr()
{
    for(int i=0; i<maxrow; i++)
        memset(SCREEN[i],'.',80);
}
void Tree :: OutNodes(Node* v, int r, int c)
{
    if(r&&c&&(c<80)) SCREEN[r-1][c-1]=v->d; //вывод метки
    if(r<maxrow){
        if(v->lft) OutNodes(v->lft, r+1,  c-(offset>>r)); //левый сын
        if(v->mdl) OutNodes(v->mdl, r+1, c); //средний сын
        if(v->rgt) OutNodes(v->rgt, r+1, c+(offset>>r)); //правый сын
        }
}
template<class Item> class STACK
{
    Item *S;
    int t;
public:
    STACK(int maxt):S(new Item[maxt]), t(0){}
    int empty() const{return t==0;}
    void push(Item item) {S[t++]=item;}
    Item pop(){return(t? S[--t]:0);}
};
 
//Нерекурсивный обход дерева в глубину
 
int Tree::DFS()
{
    const int MaxS=20; //максимальный размер стека
    int count=0;
    STACK<Node*> S(MaxS); //создание стека указателей на узлы
    S.push(root);
    while(!S.empty()) //пока стек не пуст...
    {
        Node *v=S.pop(); //поднять узел из стека
        cout<<v->d<<'_';//выдать тег, счет узлов
        count++;
        if(v->rgt) S.push(v->rgt); //STACK<-(правый сын)
        if(v->mdl) S.push(v->mdl); //STACK<-(средний сын)
        if(v->lft) S.push(v->lft); //STACK<-(левый сын)
    }
    return count;
}
 
int main()
{
    int n=0;
    Tree Tr('a','z',8);
    srand(time(NULL));
    setlocale(LC_ALL,"Russian");
    Tr.MakeTree();
    if(Tr.exist()){
        Tr.OutTree();
        cout<<'\n'<<"Обход в глубину:";
        n=Tr.DFS();
        cout<<"Пройдено узлов="<<n;
    }
    else cout<<"Дерево пусто!";
    cout<<'\n'<<"===Конец===";
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
29.03.2016, 15:44
Ответы с готовыми решениями:

Определить количество листьев на каждом уровне дерева итеративным способом
Здравствуйте, необходима помощь. Необходимо написать процедуру, определяющую количество листьев на...

Подсчитать количество элементов на n-м уровне бинарного дерева
Помогите пожалуйста написать рекурсивную функцию или процедуру, которая подсчитывает количество...

Определить число листьев на каждом уровне дерева
Нужно составить такую функцию. Именно на каждом отдельном уровне, а не по дереву вообще.

Определить число листьев на каждом уровне бинарного дерева
Помогите! Нужно написать программу Определение число листьев на каждом уровне БИНАРНОГО дерева....

3
Грамотный. Безпорно.
16860 / 9756 / 1880
Регистрация: 27.09.2012
Сообщений: 24,170
Записей в блоге: 2
29.03.2016, 15:49 2
В общем случае, для оформления кода,
выделите код и нажмите на кнопку соответствующего языка (см. изображение)
0
0 / 0 / 0
Регистрация: 29.03.2016
Сообщений: 3
29.03.2016, 19:52  [ТС] 3
Поиском пользовался, не могу до конца разобраться как реализовать алгоритм
0
0 / 0 / 0
Регистрация: 29.03.2016
Сообщений: 3
31.03.2016, 12:18  [ТС] 4
может кто-нибудь помочь?
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
31.03.2016, 12:18

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Подсчитать кол-во красных листьев на заданном уровне Н
Добрый вечер. Помогите с реализацией программы, пожалуйста. Задание: Подсчитать кол-во листьев...

Дан текст, в котором слова разделены одним пробелом. а) Подсчитать количество слов в данной строке. б) Подсчитать количество букв а в последнем слове
Дан текст, в котором слова разделены одним пробелом. а) Подсчитать количество слов в данной строке....

Подсчитать количество слов в данной строке, подсчитать количество букв а в последнем слове
Дан текст. а) Подсчитать количество слов в данной строке. б) Подсчитать количество букв а в...


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

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

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