#include <bits/stdc++.h>
using namespace std;

struct node {
   char c;
   node *sag;
   node *sad;
};
typedef struct node *tree;

tree make_node(char c,tree sag,tree sad) {
   tree t;
   t = (tree)malloc(sizeof(t));
   t->c = c;
   t->sag = sag;
   t->sad = sad;
   return t;
}

tree make_leaf(int x) {
   return make_node(x,NULL,NULL);
}

tree make_tree() {
   return make_node('*',make_node('+',make_leaf('14'),make_node('/',make_leaf('8'),make_leaf('2'))),make_node('-',make_leaf('5'),make_leaf('3')));
}

void prefix(tree t) {
   if(t != NULL) {
      cout << t->c << " ";
      prefix(t->sag);
      prefix(t->sad);
   }
}

void infix(tree t) {
   if(t != NULL) {
      infix(t->sag);
      cout << t->c << " ";
      infix(t->sad);
   }
}

void postfix(tree t) {
   if(t != NULL) {
      postfix(t->sag);
      postfix(t->sad);
      cout << t->c << " ";
   }
}

queue<tree> q;

void bfs(tree t) {
   if(t != NULL)
      q.push(t);
   while(!q.empty()) {
      tree x = q.front();
      q.pop();
      cout << x->c << " ";
      if(x->sag != NULL)
         q.push(x->sag);
      if(x->sad != NULL)
         q.push(x->sad);
   }
}

int height(tree t) {
   if(t == NULL)
      return 0;
   else {
      int maxL = height(t->sag);
      int maxR = height(t->sad);
      return max(maxL,maxR)+1;
   }
}

bool isLeaf(tree node) {
   return node->sad == NULL && node->sag == NULL;
}

int leaf(tree t) {
   if(t == NULL)
      return 0;
   if(isLeaf(t))
      return 1;
   return leaf(t->sad)+leaf(t->sag);
}

tree srch(tree t,char c) {
   tree found;
   if(t == NULL)
      found = NULL;
   else {
      found = srch(t->sag,c);
      if(!found)
         found = srch(t->sad,c);
   }
   return found;
}

int main() {
   tree root;
   root = make_tree();
   cout << "Prefix : ";
   prefix(root);
   cout << "\nInfix : ";
   infix(root);
   cout << "\nPostfix : ";
   postfix(root);
   cout << "\nEn largeur : ";
   bfs(root);
   cout << "\nHeigth : " << height(root);
   cout << "\nLeaf : " << leaf(root);
   cout << endl;
   if(srch(root,'*') != NULL)
      cout << srch(root,'*')->c;
   else
      cout << "NOT found";
}