|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
31.03.2016, 12:33 | #1 |
Новичок
Джуниор
Регистрация: 31.03.2016
Сообщений: 1
|
Деревья
Добрый день!
Не могу разобраться со следующим: нужно подсчитать количество листьев не на последнем уровне, имеющем листья. Текст программы, генерирующий дерево приведен ниже, обход дерева в глубину, дерево троичное. Может кто-нибудь помочь? #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'<<"===Конец==="; } |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
деревья | Лиляля | Помощь студентам | 2 | 03.06.2012 16:55 |
Деревья Си++ | СветОК | Общие вопросы C/C++ | 1 | 25.05.2012 07:52 |
VB. Деревья. | TimonCer | Помощь студентам | 4 | 25.06.2010 23:30 |
Деревья | Blond_89 | Паскаль, Turbo Pascal, PascalABC.NET | 1 | 08.06.2010 14:39 |
Деревья | Chudo4258 | Помощь студентам | 3 | 29.04.2009 14:46 |