#include

#include

typedef int elemtype；

typedef struct Node

{

elemtype data；

struct Node *Lchild；

struct Node *Rchild；

}TreeNode；

typedef TreeNode *bt；

int

Search_data(TreeNode *t,TreeNode **p,TreeNode **q， elemtype x) //查詢函式

{

int flag=0；

*p=NULL；

*q=t；

while(*q)

{

if (x>(*q)->data)

{

*p=*q；

*q=(*q)->Rchild；

}

else{

if (x<(*q)->data)

{

*p=*q；

*q=(*q)->Lchild；

}

else{

flag=1；

break；

}

}

}

return flag；

}

int

InsertNode(TreeNode **t,elemtype x) //插入函式

{

int flag =0；

TreeNode *q，*s；

TreeNode *p=*t；

if (，Search_data(*t，&p，&q,x))

{

s=(TreeNode *)malloc(sizeof(TreeNode))；

s->data=x；

s->Lchild=NULL；

s->Rchild=NULL；

flag=1；

if(，p) t=s；

else{

if(x>p->data)

p->Rchild=s；

else

p->Lchild=s；

}

}

return flag；

}

int

{

int flag=0；

TreeNode *q，*s，**f；

TreeNode *p=*t；

if (Search_data(*t，&p，&q,x))

{

flag=1；

if(p==q) f=&(*t)；

else

{

f=&(p->Lchild)；

if(x>p->data)

f=&(p->Rchild)；

}

if(，q->Rchild)

*f=q->Lchild；

else{

if(，q->Lchild)

*f=q->Rchild；

else{

p=q->Rchild；

s=p；

while(p->Lchild){

s=p；

p=q->Lchild；

}

*f=p；

p->Lchild=q->Lchild；

if (s，=p)

{

s->Lchild=p->Rchild；

p->Rchild=q->Rchild；

}

}

}

free(q)；

}

return flag；

}

void

visit(bt t)

{

printf("%c"，t->data)；

}

TreeNode *

creat_Tree()

{

char ch；

bt t；

ch=getchar()；

if(ch==" ") return (NULL)；

else{

t=(TreeNode *)malloc(sizeof(TreeNode))；

t->data=ch；

t->Lchild=creat_Tree()；

t->Rchild=creat_Tree()；

printf("%x\n"，&t)；

return (t)；

}

}

void

mid_oderTree(bt t)

{

if (t，=NULL)

{

mid_oderTree(t->Lchild)；

visit(t)；

mid_oderTree(t->Rchild)；

}

}

int

count_leafTree(bt t)

{

int i；

if(t==NULL) return 0；

else

if(t->Lchild==NULL&&t->Rchild==NULL)

i=1；

else i=count_leafTree(t->Lchild)+

count_leafTree(t->Rchild)；

return i；

}

main()

{

TreeNode *t，*p，*q；

elemtype x；

x="M"；

printf("creat Tree:\n")；

//二叉樹在遍歷最後一個節點之後，遇到結束符結束建立樹。

t=creat_Tree()；

printf("中根遍歷樹:\n")；

mid_oderTree(t)；

printf("\n中根序插入%c成功輸出（是1否0）:%d\n"，x,InsertNode(&t,x))；

printf("插入%c後的查詢成功輸出（是1否0）:%d\n"，x,Search_data(t，&p，&q， x))；

printf("插入後的中根遍歷樹:\n")；

mid_oderTree(t)；

mid_oderTree(t)；

printf("\n求樹的葉子數:%d \n"，count_leafTree(t))；。