Matematické Fórum

#include <iostream>
#include <iomanip>
#include <cstdlib>

#include"stack.h"

using namespace std;

struct Node 
{
  int info;
  Node *left, *right;
  Node(int x, Node* l, Node* r) 
  {
    info = x; left = l; right = r;
  }
};

inline int random(int m) 
{
// vysledkem je pseudonahodne cislo z intervalu 0 az m-1
  return rand()%m;
}

Node *randTree(int depth) 
{
  if(depth<=0 || random(10)>7) return NULL;
  return new Node(random(100),randTree(depth-1), randTree(depth-1));
}
//------------------------------------------------------------------------------

// vypíše ve tvaru stromu (hodnoty pod sebe)
void print(Node *p, int s) 
{
  cout << setw(s) << ' ';
  if(p) 
  {
    cout <<  p->info << endl;
    print(p->left, s+1);
    print(p->right, s+1);
  }
  else
    cout << "x" << endl;
}

//vypíše ve tvaru: hodnota uzlu(levý podstrom, pravý podstrom) - rekurzivně
void print2(Node *p) 
{
  if(p) 
  {
    cout <<  p->info << " (" ;
    print2(p->left); 
    cout << ",";
    print2(p->right);
    
    cout << ")";
  }
  else
    cout << "x";
}

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
//vypíše ve tvaru: hodnota uzlu(levý podstrom, pravý podstrom) - nerekurzivně (s použitím zásobníku)
struct Pair 
{
  Node *ptr;
  int spc;
  Pair(Node *p) 
  {
    ptr = p;
  }
};
void print2Nerek(Node *p) 
{
  Stack<Pair> stc;
  stc.push(Pair(p));
  while(!stc.empty()) 
  {
    Pair pair = stc.pop();
    if(!pair.ptr)
       cout << "x" ;
    else if(pair.ptr) 
    {     
      cout << pair.ptr->info;
      cout << " (";
      stc.push(Pair(pair.ptr->right));
      cout << ",";
      stc.push(Pair(pair.ptr->left));
      cout << ")";
    }
  }
}
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------

//sečte hodnoty všech uzlů - rekurivně
int soucet(Node *p) 
{
  if(p)
    return p->info+soucet(p->left)+ soucet(p->right);
  else
    return 0;
}
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
//sečte hodnoty všech uzlů s použitím zásobníku - nerekurzivně (s použitím zásobníku)
int soucetNerek(Node *p) 
{
  Stack<Node*> stc;
  int soucet = 0;
  stc.push(p);
  while(!stc.empty()) 
  {
    Node *q = stc.pop();
    if(q) 
    {
      soucet+=q->info;
      stc.push(q->right);
      stc.push(q->left);
      soucet++;
    }
  } 
  return soucet;
}
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------

int main() 
{
  Node *root = randTree(4);
  cout << "vypis (rekurzivne)" << endl;
  print2(root);
  
  cout << endl << endl;
  
  cout << "vypis (nerekurzivne)" << endl;
  print2Nerek(root);
  
  cout << endl << endl;
  //print(root, 1);
  cout << "soucet uzlu stromu (rekurzivne):   " << soucet(root) << endl;
  cout << "soucet uzlu stromu (nerekurzivne): " << soucetNerek(root) << endl << endl;
  
  system("PAUSE");
  return 0;
}