Поиск листьев в дереве

void Tree::PrintTreeVn(TreeNode *t, int level)  
{
     
    if (t!=NULL)
    {
        PrintTree(t->right, level+1);
       
        IndentBlanks(6*level);
        cout << t->data << endl;
        PrintTree(t->left, level+1);
        
        
    }
}

//////////////////////////////////////////////// Ïîèñê è âûâîä  âíóòðåííèõ ëèñòüåâ
void Tree::PrintTreeVnesh(TreeNode *t, int level)  
{
    
   if (t!=NULL)
  
    {
       
                     
        PrintTreeVnesh(t->right, level+1);
                    
  if ((t->right!=NULL && t->left!=NULL) || (t->right!=NULL || t->left!=NULL)) cout << t->data <<",";
  ;
                        
  
        PrintTreeVnesh(t->left, level+1);
       
        
    
}
     
}

if  (t->right!=NULL || t->left!=NULL)

#include <iostream>
using namespace std;
 
//////////////////////////////////////////////////////////////
class TreeNode
{
public:
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int item, TreeNode *l = NULL, TreeNode *r = NULL);
};
 
TreeNode::TreeNode(int item, TreeNode *l, TreeNode *r)
{
    data = item;
    left = l;
    right = r;
}
//////////////////////////////////////////////////////////////
 
class Tree
{
public:
    Tree();
    ~Tree(void);
    TreeNode *FindNode(int, TreeNode *&);
    void Insert(int);
    void Delete(int);
    void DeleteTree(TreeNode *);
    void PrintTree(TreeNode *, int);
    void PrintTreeVn(TreeNode *, int); /// Поиск внешних вершин
    void PrintTreeVnesh(TreeNode *, int);/// Поиск внутренних вершин
    void PrintDoch(TreeNode *, int);
    void PrintUrovnya(TreeNode *, int, int);/// Поиск вершин на уровне
    void MaxLen(TreeNode *, int); ///Поиск самой длинной ветки
    void SecondMax(TreeNode *);// Поиск второго максимального числа
    void PrintBalance(TreeNode *);// Определить сбалансированное дерево
    void Inorder(TreeNode *);
    TreeNode* GetTreeNode(int item, TreeNode *l = NULL, TreeNode *r = NULL);
    void FreeTreeNode(TreeNode *p);
    
    int size,tempdlina, max1,max2, levoe, pravoe;
   
    
    TreeNode *root;
    TreeNode *current;
    
};
 
 
Tree::Tree()
{
    root = NULL;
    size = 0;
    tempdlina=0;
    max1=0;
    max2=0;
    levoe=0;
    pravoe=0;
   
   
    
    
}
 
 
Tree::~Tree()
{
    DeleteTree(root);
}
 
TreeNode* Tree::GetTreeNode(int item, TreeNode *l, TreeNode *r)
{
    TreeNode *p;
    p = new TreeNode(item, l, r);
    return p;
}
 
 
void Tree::FreeTreeNode(TreeNode *p)
{
    delete p;
}
 
void Tree::DeleteTree(TreeNode *t)
{
    if (t!=NULL)
    {
        DeleteTree(t->left);
        DeleteTree(t->right);
        FreeTreeNode(t);
    }       
}
 
 
void IndentBlanks(int num)
{
    for(int i=0; i<num; i++)
       cout << " ";
}    
 
 
void Tree::PrintTree(TreeNode *t, int level)
{
    if (t!=NULL)
    {
        PrintTree(t->right, level+1);
        IndentBlanks(6*level);
        
        cout << t->data << endl;
        
        PrintTree(t->left, level+1);
        
    }
}     
//////////////////////////////////////////////// Поиск и вывод  внешних вершин
void Tree::PrintTreeVn(TreeNode *t, int level)  
{
    
   if (t!=NULL )
  
    {
         if (level==0)
         cout<<root->data<<",";
        PrintTreeVn(t->right, level+1);
                    
  if (t->right==NULL && t->left==NULL) cout << t->data <<",";
                        
  
        PrintTreeVn(t->left, level+1);
        
       
    }
 
     
}     
//////////////////////////////////////////////// Поиск и вывод  внутренних вершин
void Tree::PrintTreeVnesh(TreeNode *t, int level)  
{
    
   if (t!=NULL)
  
    {
       
                     
        PrintTreeVnesh(t->right, level+1);
                    
  if  (level!=0 && (t->right!=NULL || t->left!=NULL)) cout << t->data <<",";
  ;
                        
  
        PrintTreeVnesh(t->left, level+1);
       
        
    
}
     
} 
//////////////////////////////////////////////Поиск дочерних вершин и замена значении  
 void Tree::PrintDoch(TreeNode *t, int level)
{
    if (t!=NULL)
    {
        PrintDoch(t->right, level+1);
         if (t->data==3)
               
        t->data=23; 
        
        PrintDoch(t->left, level+1);
        
    }
}      
//////////////////////////////////////////////// Поиск и вывод  вершин на одном уровне
void Tree::PrintUrovnya(TreeNode *t, int level, int urov)  
{
    
  if (t!=NULL)
    {
        PrintUrovnya(t->right, level+1,urov);
      
        if (level==urov && (t->right!=NULL || t->left!=NULL))
        cout << t->data <<",";
        
        PrintUrovnya(t->left, level+1, urov);
        
    }
 
     
}  
/////////////////////////////////////////////////Поиск самой длинной ветки
 void Tree::MaxLen(TreeNode *t, int level)
{
    if (t!=NULL)
    {
        MaxLen(t->right, level+1);
    
       
        if (tempdlina<level)
       
           tempdlina=level;
         if (tempdlina==level && (t->right==NULL && t->left==NULL))
         cout<< "Samaya dlinnaya vetka= "<<tempdlina<<endl; 
           
       
        
        MaxLen(t->left, level+1);
        
    }
} 
////////////////////////////////////////////////Поиск вторго максимального числа      
void Tree::SecondMax(TreeNode *t)
{
    if (t!=NULL)
    {
        SecondMax(t->right);
       
                if (t->data>max1)
                max1=t->data;
                if (t->data!=max1)
                {
                if (t->data>max2)
                max2=t->data;
                }
                
                
        cout << max2 << endl;
        
        SecondMax(t->left);
        
    }
}
////////////////////////////////////////////////Определить сбалансированное дерево или нет.
void Tree::PrintBalance(TreeNode *t)
{
    if (t!=NULL)
    {
        PrintBalance(t->right);
        if ((t->right!=NULL && t->left!=NULL)||  (t->right==NULL && t->left==NULL))
        pravoe=1;
        if ((t->right==NULL && t->left!=NULL) || (t->right!=NULL && t->left==NULL))
        levoe++;
                      
        PrintBalance(t->left);
        if (pravoe==1 && (levoe==0||levoe==1))
        cout<<"***Derevo sbalansirovannoe!!!***"<<endl;
        else
        cout<<"***Derevo ne sbalansirovannoe!!!***"<<endl;
    }
}          
/////////////////////////////////////////////////////////////
void Tree::Inorder(TreeNode *t)
{
    if (t!=NULL)
    {
        Inorder(t->left);
        cout << t->data << " ";
        Inorder(t->right);
    }
}    
 
 
TreeNode* Tree::FindNode(int item, TreeNode *&parent)
{
    TreeNode *t = root;
    parent = NULL;
    while(t!=NULL)
    {
        if (item == t->data)
            break;
        else
        {
            parent = t;
            if (item < t->data)
                t = t->left;
            else
                t = t->right;
        }
    }
    return t;
}              
 
 
void Tree::Insert(int item)
{
    TreeNode *t = root, *parent = NULL, *newNode;
    newNode = GetTreeNode(item, NULL, NULL);
    
    while(t!=NULL)
    {
        parent = t;
        if (item < t->data)
            t = t->left;
        else
            t = t->right;
    }
    
    if (parent == NULL)
        root = newNode;
    else if (item < parent->data)
        parent->left = newNode;
    else
        parent->right = newNode;
        
    current = newNode;
    size++;
    
}  
  
 
int main()
 
{
    int u;
  Tree tree;
  tree.Insert(5);
  tree.Insert(7);
  tree.Insert(2);
//  tree.Insert(8);
//  tree.Insert(15);
  tree.Insert(3);
  tree.Insert(1);
//  tree.Insert(4);
 // tree.Insert(7);
  ///tree.Insert(16);
//  tree.Insert(9);
  
  
  
  
 tree.Inorder(tree.root);
 cout << endl << endl;
  cout<< "************Vivod dereva*****************"<<endl; 
  tree.PrintTree(tree.root, 0);
  cout<<endl;
  cout<< "************2.Vivod vneshnih vershin*****************"<<endl;
 
  tree.PrintTreeVn(tree.root,0);
   cout<<endl;
  cout<< "************3.Vivod vnutrennih vershin*****************"<<endl;
  tree.PrintTreeVnesh(tree.root,0);
  cout<<endl;
  cout<< "************4.Pomenyat znacheniya dochernih vershin*****************"<<endl;
 // tree.PrintDoch(tree.root,0);
  cout<<endl;
  cout<< "************Vivod dereva*****************"<<endl; 
  tree.PrintTree(tree.root, 0);
  cout<<endl;
  cout<< "************5.Vivod vseh vershin na odnom urovne*****************"<<endl;
  cout <<"**Kakoi uroven vivesti?- ";
  cin>>u;
  
  tree.PrintUrovnya(tree.root,0,u);
   cout<<endl;
  cout<< "************6.Poisk samoi dlinnoi vetki*****************"<<endl;
  tree.MaxLen(tree.root,0);
  cout<<endl;
  cout<< "************7.Poisk vtorogo maksimalnogo chisla*****************"<<endl;
  tree.SecondMax(tree.root);
  cout<<endl;
  cout<< "************8.Proverka sbalansirovannosti dereva*****************"<<endl;
  tree.PrintBalance(tree.root);
  cout<<endl;
 
 // tree.Delete(50);
 // cout << endl << endl;
 // tree.PrintTree(tree.root, 0);
  
  system("PAUSE");  
  return 0;
}

bool Tree::balanced(TreeNode *t, int& size)
{
    if (t!=NULL)
    {
        int leftsize, rightsize;
        size=1;
        if (!foo(t->left, leftsize))  return false;
        size+=leftsize;
        if (!foo(t->right, rightsize)) return false;
        size+=rightsize;
      
        if (leftsize>rightsize) return (leftsize-rightsize<=1);
        else                    return (rightsize-leftsize<=1);
 
    }
    else{
        size=0;
        return true;
    }    
}

void Tree::PrintDoch(Node *obj)
{
    if (obj!=NULL)
   {
      Change(obj->right);
      
        if ((obj->left!=NULL) && (obj->right!=NULL))    
        swap (obj->left->data, obj->right->data);       //#include <algorithm> , среда "Dev-CPP"
  
      Change(obj->left);
   }
}

void Tree::MaxLen(Node *obj, int level)
{
    if(obj!=NULL)
   {
      MaxLen(obj->right, level+1);
         
        if(tempdlina < level && (obj->right==NULL && obj->left==NULL))
        {   
             tempdlina = level;
        }
        
        MaxLen(obj->left, level+1);
   }
} 
 
int main()
{
    //...
    cout<< "************6.Поиск самой длинной ветки:*****************"<<endl;
    koks.MaxLen(tree.root, 0);
    cout<<endl;
    cout << "Самая длинная ветка - " << tree.tempdlina << endl;
    //...
}

//В класс добавляем три переменных: 
int min; 
int max;
bool balance;
 
 
 
void Tree::PrintBalance(Node *obj, int level)  
{ 
    if(obj != NULL)
    {
        Balance(obj->right, level+1);                   //Рекурсивно направо!
        
        if (obj->right!=NULL && obj->left==NULL)                    //Односторонняя внутренняя вершина (правая):
        {
            if (obj->right->right!=NULL || obj->right->left!=NULL)  //Признаки нарушения балансировки
                balance = false;    
        }
      
        if (obj->left!=NULL && obj->right==NULL)                    //Односторонняя внутренняя вершина (левая):
        {
            if (obj->left->left!=NULL || obj->left->right!=NULL)        //Признаки нарушения балансировки
                balance = false;                    
        }
 
        if (obj->right==NULL  &&  obj->left==NULL)              //Проверяются листья
        {
            if (min==0  ||  min > level)                        
                min = level;
            if (max < level)                
                max = level;
            if ((max - min) > 1)                        //Проверяется разница уровней
            balance = false;                            
        }
                        
      Balance(obj->left, level+1);                  //Рекурсивно налево!
   } 
} 
 
int main()
{
    //...
    cout << "************8.Proverka sbalansirovannosti dereva*****************" << endl;
    tree.Balance(tree.root, 0);     
 
    if (tree.balance==false )
       cout << "Дерево НЕ сбалансировано!" << endl;
    else
       cout << "Дерево сбалансировано!" << endl;
    //...
}