#include<stdio.h>
#include<stdlib.h>
typedef struct BTNode
{
int data;
int count;
struct BTNode *lchild;
struct BTNode *rchild;
}BTNode;
/*
int insert(BTNode *&T,int key)//递归方法解决
{
if(T==NULL)
{
T=(BTNode*)malloc(sizeof(BTNode));
T->data=key;
T->count=1;
T->lchild=T->rchild=NULL;
return 1;
}
else if(key<T->data)
insert(T->lchild,key);
else if(key>T->data)
insert(T->rchild,key);
else
{
T->count++;
return 0;
}
}
*/
int insert(BTNode *&T,BTNode *&pr,int key)//非递归
{
BTNode *p=T;
while(p!=NULL)
{
if(p->data!=key)
{
pr=p;
if(p->data>key)
p=p->lchild;
else if(p->data<key)
p=p->rchild;
}
else
{
(p->count)++; //此处如果找到，如果找不到两种情况
//1、T为空树 2、T不为空，但没有key
return 0;
}
}
BTNode *s=(BTNode*)malloc(sizeof(BTNode));
s->data=key;
s->count=1;
s->lchild=s->rchild=NULL;
if(pr==NULL)
T=s;
else if(pr->data>key)
pr->lchild=s;
else
pr->rchild=s;
return 1;
}
void pre(BTNode *T)
{
if(T!=NULL)
{
printf("\ndata=%d count=%d \n",T->data,T->count);
pre(T->lchild);
pre(T->rchild);
}
}
int main()
{
int a[]={1,3,2,1,2,3,2,7,6,5,5,6};
BTNode *T=NULL,*pr=NULL;
for(int i=0;i<12;i++)
printf("%d ",insert(T,pr,a[i]));
pre(T);
}
