SHARE
TWEET

Untitled

a guest May 20th, 2019 57 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2. using namespace std;
  3.  
  4. struct nodo{
  5.     int info;
  6.     nodo* left;
  7.     nodo* right;
  8.  
  9.     nodo(int x=0, nodo* l=0, nodo* r=0){
  10.         info = x;
  11.         left = l;
  12.         right = r;
  13.     }
  14. };
  15.  
  16. // FUNZIONI AUSILIARIE FORNITE
  17. nodo* buildTree(int arr[], int i, int n)  {
  18.  
  19.     if (i >= n) {
  20.         return NULL;
  21.     }
  22.     nodo* root = new nodo(arr[i]);
  23.     // insert left child
  24.     root->left = buildTree(arr, 2 * i + 1, n);
  25.     // insert right child
  26.     root->right = buildTree(arr, 2 * i + 2, n);
  27.  
  28.     return root;
  29.  
  30. }
  31.  
  32. int height(nodo* root) {
  33.     if(!root) {
  34.         return 0;
  35.     }
  36.     return 1 + max(height(root->left), height(root->right));
  37. }
  38.  
  39. void printGivenLevel(nodo* root, int level)
  40. {
  41.     if (root == NULL)
  42.         return;
  43.     if (level == 1)
  44.        cout << root->info;
  45.     else if (level > 1)
  46.     {
  47.         printGivenLevel(root->left, level-1);
  48.         printGivenLevel(root->right, level-1);
  49.     }
  50. }
  51.  
  52. // STAMPA L'ALBERO LIVELLO PER LIVELLO
  53. void printLevelOrder(nodo* root) {
  54.     int h = height(root);
  55.     int i;
  56.     for (i=1; i<=h; i++)
  57.     {
  58.         printGivenLevel(root, i);
  59.         cout << endl;
  60.     }
  61. }
  62.  
  63.  
  64. // DA IMPLEMENTARE
  65. // PRE=(albero(root) ben formato e non vuoto)
  66. int cercaFoglia(nodo* root, int key, nodo* &t) {
  67.     int h1;
  68.     if(root->info==key) {
  69.         return 0;
  70.     }
  71.     if(!root->left && !root->right) {
  72.         return -1;
  73.     }
  74.     if(root->left) {
  75.         h1=cercaFoglia(root->left, key, t);
  76.     }
  77.     if(root->right) {
  78.         h1=cercaFoglia(root->right, key, t);
  79.     }
  80.     return h1+1;
  81. }
  82. // POST=(se c'è una foglia con info=x, allora restituisce col return la profondità minima di tale foglia e assegna a t il puntatore ad essa, altrimenti restituisce -1)
  83.  
  84. // Driver program to test above function
  85. int main() {
  86.     int a[100], n, key;
  87.     cin >> n;
  88.     for (int i=0; i<n; i++) {
  89.         cin >> a[i];
  90.     }
  91.     cin >> key;
  92.    
  93.     nodo* root = NULL;
  94.     root = buildTree(a, 0, n);
  95.    
  96.     //printLevelOrder(root); // decommentare per vedere la stampa dell'albero livello-per-livello
  97.     nodo* tmp = root;
  98.    
  99.     cout << "start" << endl;
  100.     int altezza = cercaFoglia(root, key, tmp);
  101.    
  102.     if(altezza!=-1) {
  103.         cout<<"La foglia si trova ad altezza "<<altezza<<endl;
  104.     } else {
  105.         cout<<"Foglia non trovata"<<endl;
  106.     }
  107.     cout << "end" << endl;
  108. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top