#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <string>
using namespace std;
const int M = 10000;
//Define data node
class dNode{
public:
string name;
int age;
bool sex;
dNode(){
age = 0;
name = "no name";
sex = true;//nan
}
dNode(string name, int age, bool sex):name(name), age(age), sex(sex){}
//Print the node
void show(){
cout << "name: " << this->name << endl;
cout << "age: " << this->age << endl;
cout << "sex: " << this->sex << endl;
cout << "******************************" << endl;
}
//Overloading the assignment symbol
bool operator = (const dNode &d){
this->age = d.age;
this->name = d.name;
this->sex = d.sex;
}
//Overloaded equality symbol
bool operator == (const dNode &d){
return name == d.name && age == d.age && sex == sex;
}
//Overload by age greater than sign
bool operator > (const dNode &d){
return age > d.age;
}
//Overloaded less than sign by age
bool operator < (const dNode &d){
return age < d.age;
}
};
//Define the node of the binary lookup tree
//This specifies that there are no duplicate nodes in the tree, and that you need to record how many times a node is present
class bstNode{
public:
bstNode *left;
bstNode *right;
bstNode *parent; //Execution father, easy to access up, if the data is large, and find up the usage is not to reduce the space
dNode data; //The number of times the node appears in the tree
int count;
bstNode(){
left = right = parent = NULL;
count = 1;
}
};
//Define a binary tree
class bst{
private:
//Clean up the whole tree
//Note that it is important to clean up the methods that are subsequently traversed
void destory(bstNode *cur){
if(NULL == cur){
return;
}
cout << "clearing" << endl;
destory(cur->left);
destory(cur->right);
delete cur; //Subsequent cleaning
}
//Actually delete the node
void _del(bstNode * cur, bstNode *delNode);
public:
bstNode * root = NULL;
bst(){
root = NULL;
}
//Insert, the return value is to facilitate the construction of the parent relationship
bstNode * insert(bstNode *& cur, dNode data);
//search
bstNode * search(bstNode * cur, dNode data);
//The first sequence traversal
void pre_raversal(bstNode *cur);
//Returns the minimum value of a cur root node
bstNode * minNode(bstNode *cur);
//Get the successor of cur node
bstNode * succNode(bstNode *cur);
//Delete the node, if the count is greater than 1, count minus 1, if the count==1, clear the node, return the address of the cleared node
bstNode * del(bstNode *cur, dNode data);
//The constructor does the tree cleanup
virtual ~bst(){
cout << "###start clear###" << endl;
this->destory(root);
cout << "###clear ok###" << endl;
}
};
bstNode * bst::insert(bstNode *& cur, dNode data){
if(NULL == cur){
bstNode * newNode = new bstNode();
newNode->data = data;
cur = newNode;
return cur;
}else if(cur->data == data){
cur->count++;
}else if(cur->data > data){
bst::insert(cur->left, data)->parent = cur;
}else if(cur->data < data){
bst::insert(cur->right, data)->parent = cur;
}
}
bstNode * bst::search(bstNode *cur, dNode data){
if(NULL == cur){
return NULL;
}else if(cur->data == data){
return cur;
}else if(cur->data > data){
return cur->left;
}else if(cur->data < data){
return cur->right;
}
}
void bst::pre_raversal(bstNode *cur){
if(NULL == cur)
return;
bst::pre_raversal(cur->left);
cout << "count: " << cur->count << endl;
cur->data.show();
bst::pre_raversal(cur->right);
}
bstNode * bst::minNode(bstNode *cur){
if(NULL == cur){
return NULL; //If the root node is empty, it returns empty
}else{
if(NULL != cur->left){
return minNode(cur->left);
}
}
}
bstNode * bst::succNode(bstNode *cur){
if(NULL != cur->right){
return minNode(cur);
}
bstNode * parentNode = cur->parent;
while(NULL != parentNode && parentNode->right == cur){
cur = parentNode;
parentNode = parentNode->parent;
}
return parentNode;
}
void bst::_del(bstNode * cur, bstNode *delNode){
if(NULL == delNode->left || NULL == delNode->right){
//To be continued
}
}
bstNode * bst::del(bstNode *cur, dNode data){
//First, find the node that needs to be deleted
bstNode * delNode = this->search(cur, data);
if(NULL == delNode) //The node was not found and does not need to be deleted
return NULL;
if(delNode->count == 1){
_del(this->root, delNode);
}else{
delNode->count--;
}
}
int main(){
bst *root = new bst();
//Construct 50 people, repeating is not inserted repeatedly in the tree, but is counted
int num = 50;
for(int i = 0; i < num; i++){
dNode * newData = new dNode("Luo", rand() % 15, rand() % 2);
root->insert(root->root, *newData);
}
//The former sequence traversal
root->pre_raversal(root->root);
bstNode *searchNode = root->search(root->root, *new dNode("Luo", 3, 1));
cout << "#######search a Node ##########" << endl;
if(NULL == searchNode){
cout << " The node was not found " << endl;
}else{
cout << "count: " << searchNode->count << endl;
searchNode->data.show();
}
//Clean up the whole tree
delete root;
return 0;
}