#include<iostream.h>

struct tree{

int info;

tree *left,*right;

};

tree *taonode(int x,tree *l, tree *r){

tree *p=new tree;

p->info=x;

p->left=l;

p->right=r;

return p;

};

void taocay(tree *& root)

{

tree *b, *c, *d, *e, *f, *g;

g=taonode(20,NULL,NULL);

f=taonode(15,NULL,NULL);

e=taonode(9,f,g);

d=taonode(10,NULL,NULL);

c=taonode(8,e,NULL);

b=taonode(1,NULL,d);

root=taonode(3,b,c);

}

void tientu(tree *root)

{

if(root!=NULL)

{

cout<<root->info<<"\t";

tientu(root->left);

tientu(root->right);

}

}

int tong(tree *root)

{

if(root==NULL) return 0;

else return root->info + tong(root->left) + tong(root->right);

}

int tongchan(tree *root)

{

if(root==NULL) return 0;

else{

if(root->info%2==0) return root->info+tongchan(root->left)+tongchan(root->right);

else return tongchan(root->left)+tongchan(root->right);

}

}

int dem(tree *root)

{

if(root==NULL) return 0;

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

}

void timmax(tree *root, int &max)

{

if(root!=NULL)

{

if(root->info>max)

max=root->info;

timmax(root->left,max);

timmax(root->right,max);

}

}

int timx(int x,tree *root)

{

if(root==NULL) return 0;

else if(root->info==x) return 1;

else if(timx(x,root->left)) return 1;

else return timx(x,root->right);

}

tree *timnode(int x,tree *root)

{

if(root==NULL) return NULL;

else if(root->info==x) return root;

else if(timx(x,root->right)) return timnode(x,root->right);

else return timnode(x,root->left);

}

int timmuc(tree *root, tree *p)

{

if(root==NULL||p==NULL) return 0;

else if(root==p) return 1;

else if(timx(p->info,root->left)) return 1+ timmuc(root->left,p);

else return 1+ timmuc(root->right,p);

}

void main()

{

int x,max,t,tx,tc,d;

tree *root;

taocay(root);

tientu(root);

cout<<endl;

t=tong(root);

cout<<"Tong cac gia tri trong cay la :"<<t<<"

";

tc=tongchan(root);

cout<<"Tong cac gia tri chan trong cay la: "<<tc<<"

";

d=dem(root);

cout<<"So node trong cay la : "<<d<<"

";

max=root->info;

timmax(root,max);

cout<<"Gia tri lon nhat trong cay la :"<<max<<"

";

cout<<"Tim gia tri x: ";cin>>x;

if(timx(x,root)==1)

cout<<"Gia tri "<<x<<" co trong cay"<<"

";

else cout<<"Gia tri "<<x<<" khong co trong cay"<<"

";

tree *p=timnode(x,root);

//cout<<"

"<<p<<endl;

cout<<"Muc cua gia tri "<<x<<" trong cay la: "<<timmuc(root,p);

}