#include<iostream>
using namespace std;
struct Node {
int data;
Node * left,*right;
Node (int n_data){
data=n_data;
left = NULL;
right = NULL;
}
};
class Tree{
public:
Node *root;
Tree(int data){
root = new Node(data);
//root = new Node(data);
}
friend ostream& operator << (ostream& out,Node * r)
{
if(!r){return out;}
out<<r->data<<" ";
if(r->left){out<<r->left;}
if(r->right){out<<r->right;}
return out;
}
Node getRoot()
{
return (*root);
}
~Tree()
{
while(root)
{
remove(root,root->data);
}
}
void add(Node *&n,int data){
if(!n){
n = new Node(data);
return;
}
if(n->data >= data){
add(n->left,data);
}
else {
add(n->right,data);
}
}
void remove(Node *&n, int data){
if(!n)return;
if(n->data == data){
if(!n->left){
Node *tmp = n;
n = n->right;
delete tmp;
}
else if(!n->right){
Node *tmp = n;
n = n->left;
delete tmp;
}
else n->data = min(n->left);
}
else {
if(n->data > data){
remove(n->left,data);
}
else remove(n->right,data);
}
}
int min(Node *n)
{
if(n->left) return min(n->left);
int i = n->data;
Node * tmp = n;
n = n->right;
delete tmp;
return i;
}
void print(Node *n){
if (n == NULL) {
return;
}
print(n->left);
if (!(n-> left || n->right)) {
cout<<n->data;
}
print(n->right);
}
int getSize(){
int i=0;
return size(root,i);
}
int size(Node *r,int br){
if(r==NULL){return br;}
if(r->left){
size(r->left,++br);
}
if(r->right){
size(r->right,++br);
}
}
};
int main (){
Tree p(10);
Node * r = &p.getRoot();
p.add(r,1);
p.add(r,2);
p.add(r,3);
p.add(r,4);
p.add(r,5);
p.add(r,6);
p.add(r,7);
//p.remove(r,6);
//p.print(r);
cout<<p.getSize();
return 0;
}
No comments:
Post a Comment