#include <stdio.h>

#include <alloc.h>

#include <stdlib.h>

#define ESC 27

typedef struct nutds

  { int info;

    struct nutds *next;

  } NUTDS;

typedef struct node

 {

   int info;

   struct node *left;

   struct node *right;

 } NODE;

NUTDS *first,*pds,*qds;

NODE *root,*Top=NULL;

int Dequy(int n);

void DSLK(NUTDS *first);

NODE *Nut(int x, struct node *L, struct node *R);

int Sonutbac2(NODE *root);

void main()

{ int so,n;

   Top = Nut(7,Nut(4,NULL,Nut(6,NULL,NULL)),

      Nut(5,Nut(2,NULL,NULL),Nut(1,NULL,NULL)));

   do

     {

       clrscr();

       printf("

1. Bai toan de quy");

       printf("

2. Danh sach lien ket");

       printf("

3. Bai toan cay");

       printf("

4. Thoat

");

do

  { printf("Bam so de chon (1/2/3/4)");

    scanf("%d",&so);

  } while (so < 1 || so > 4);

       switch (so)

{

  case 1 : printf("Nhap n = ");scanf("%d",&n);

   printf("Tong de quy la %d",Dequy(n));

   getch();

   break;

  case 2 : DSLK(first);

   getch();

   break;

  case 3 : printf("

So nut bac hai cua cay la %d ",Sonutbac2(Top));

   getch();

   break;

  case 4 : exit(0);

}

     } while (so !=4);

  }

 int Dequy(int n)

  { if (n==1) return(2);

    else return(Dequy(n-1) + 2*n);

  }

 NODE *Nut(int x, struct node *L, struct node *R)

  { NODE *p;

    p = (NODE *)malloc(sizeof(NODE));

    p -> info = x;

    p -> left = L;

    p -> right = R;

    return (p);

  }

int Sonutbac2(NODE *root)

  { if (root == NULL) return(0);

    else

       if (root -> left == NULL) return(Sonutbac2(root -> right));

       else

 if (root -> right == NULL) return(Sonutbac2(root -> left));

 else return(1 + Sonutbac2(root -> left) + Sonutbac2(root -> right));

  }

void DSLK(NUTDS *first)

 { char tl;

   int dem=0;

   first = NULL;

    do

     {

       pds = calloc(1,sizeof(NUTDS));

       printf("

Nhap thong tin cho nut ");scanf("%d",&pds->info);

       pds -> next = NULL;

       if (first == NULL) first = pds;

       else qds -> next = pds;

       qds = pds;

       printf("

Bam phim bat ky de tiep tuc, ESC de dung");

       tl = getch();

     } while (tl != ESC);

    pds = first;

    while (pds != NULL)

      { if ((pds -> info)%2 !=0) dem++;

pds = pds -> next;

      }

    printf("

So nut ma truong Info co gia tri le: %d",dem);

    getch();

 }