Деревья

[stas_rt]

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

#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'<<"===Конец===";
}