#include<iostream>
#include<cstdio>
#include<queue>
#include<stack>
#include<string.h>
using namespace std;
template <class T>
class BinaryNode
{
public:
T data;
BinaryNode<T> *lchild,*rchild;
BinaryNode(T data,BinaryNode<T> *lc=NULL,BinaryNode<T> *rc=NULL)
{
this->data=data;
this->lchild=lc;
this->rchild=rc;
}
};
template<class T>
class BST
{
private:
BinaryNode<T> *root,*parent;
public:
BST(T *A,int n)
{
root=NULL;
parent=NULL;
for(int i=0; i<n; i++) insert(A[i]);
}
BST()
{
root=NULL;
parent=NULL;
}
void input()
{
char c= 'a';
T e;
while(c!= '\n')
{
cin>>e;
insert(e);
scanf( "%c",&c);
}
}
~BST()
{
destroy(root);
}
void destroy(BinaryNode<T> *p)
{
if(p==NULL) return ;
else
{
destroy(p->lchild);
destroy(p->rchild);
delete p;
}
}
void insert(T e)
{
// printf("%d -\n", e);
if(root==NULL)
{
root=new BinaryNode<T>(e);
return ;
}
search(e);
if (parent==NULL)
{
// printf(">?");
/* if (root->data==e) return;
else if(e<root->data)
{
root->lchild=new BinaryNode<T>(e);
return ;
}
else if(e>root->data)
{
root->rchild=new BinaryNode<T>(e);
return ;
}*/return ;
}
//if (parent)printf("p%d left%p right%p e%d --\n", parent->data, parent->lchild, parent->rchild, e);
// getchar();
// if(parent->lchild!=NULL||parent->rchild!=NULL) {
if((parent->lchild!=NULL && parent->lchild->data==e) || (parent->rchild!=NULL && parent->rchild->data==e)) {
// parent=new BinaryNode<T>(e);
// printf("%d ++\n", e);
//printf("pass %d\n", e);//可能parent的右子树不为空,要插在p的左子树上
return;
}
// */
//{printf("%p %d +\n", parent, e);return ;}
// printf("%d -\n", e);
// if(parent->lchild!=NULL||parent->rchild!=NULL) return ;
else if(e<parent->data)
{
parent->lchild=new BinaryNode<T>(e);
return ;
}
else if(e>parent->data)
{
parent->rchild=new BinaryNode<T>(e);
return ;
}
}
BinaryNode<T>* search(T e)
{
return search(root,e);
}
BinaryNode<T>* search(BinaryNode<T> *r,T e)
{
parent=NULL;
if(r->data==e) return r;
BinaryNode<T> *p=r;
while(p!=NULL)
{
if(p->data==e) return p;
parent=p;
if(e>p->data)
{
p=p->rchild;
}
else if(e<p->data)
{
p=p->lchild;
}
}
// printf("%d +\n", e);
return NULL;
}
void remove()
{
}
void inorder()
{
inorder(root);
}
void inorder(BinaryNode<T> *p)
{
if(p!=NULL)
{
inorder(p->lchild);
cout<<p->data<< " ";
inorder(p->rchild);
}
}
};
int main()
{
int A[20]= {12,66,12,25,37,58,4,54,66,1,21,56,45,3,5,45,2,5,6,4};
BST<int> tree(A,20);
// BST<int> tree;
// tree.input();
// int A[5]= {1,3,2,5,4};
// BST<int> tree(A,5);
tree.inorder();
return 0;
}