// treestucts.cpp : Defines the entry point for the console application.

//

#include "stdafx.h"

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

typedef struct nodetree

{

int data;

nodetree *pleft;

nodetree *pright;

} tnode,*tree;

void add1node(int n,tree &t)

{

if (t==NULL)

{

t=new tnode;

if (t!=NULL)

{

t->data=n;

t->pleft=t->pright=NULL;

}

}

else

{

if (t->data==n) return;

if (t->data>n) add1node(n,t->pleft);

else add1node(n,t->pright);

}

}

void nlr(tree root)

{

if (root!=NULL)

{

printf(" %2d ",root->data);

nlr(root->pleft);

nlr(root->pright);

}

}

tree searchnode(int n,tree t)

{

if(t)

{

if (t->data==n) return t;

if (n>t->data) return searchnode(n,t->pright);

if (n<t->data) return searchnode(n,t->pleft);

}

return NULL;

}

int heighttree(tree t)

{

int h1=0,h2=0;

if (t==NULL) return 0;

h1=1+heighttree(t->pleft);

h2=1+heighttree(t->pright);

if (h1>h2) return h1;

else return h2;

}

int countleave(tree t)

{

int n1,n2;

if (t!=NULL)

{

if (t->pleft==NULL && t->pright==NULL) return 1;

n1=countleave(t->pleft);

n2=countleave(t->pright);

return n1+n2;

}

else return 0;

}

void changetree(tree &p,tree &q)

{

if (q->pright!=NULL)

{

changetree(p,q->pright);

}

else

{

p->data=q->data;

p=q;

q=q->pleft;

}

}

tree delnode(tree &t,int n)

{

if (t!=NULL)

{

if (n>t->data) delnode(t->pright,n);

else if (n<t->data) delnode(t->pleft,n);

else

{

tree p=t;

if(t->pleft==NULL)

t=t->pright;

else if (t->pright==NULL)

t=t->pleft;

else

{

tree *q;

q=&(t->pleft);

changetree(p,*q);

}

free(p);

}

}

return NULL;

}

void main()

{

tree t;

t=NULL;

int n;

srand(unsigned(time(NULL)));

for (int i=0;i<10;i++)

{

n=rand()%100;

add1node(n,t);

}

nlr(t);

printf("

nhap so can tim : ");

scanf("%d",&n);

tree k=searchnode(n,t);

if (k) printf("

co");

else printf("

ko");

int h=heighttree(t);

printf("

chieu cao cua cay: %d",h);

h=countleave(t);

printf("

so nut la la: %d",h);

printf("

nhap so can xoa : ");

scanf("%d",&n);

if (delnode(t,n)!=NULL) printf("

del NOT sucessful...");

nlr(t);

}