#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <string>

using namespace std;

const int M = 10000;

//定義數(shù)據(jù)節(jié)點(diǎn)
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){}
 //打印節(jié)點(diǎn)
 void show(){
  cout << "name: " << this->name << endl;
  cout << "age: " << this->age << endl;
  cout << "sex: " << this->sex << endl;
  cout << "******************************" << endl;
 }
 //重載賦值符號(hào)
 bool operator = (const dNode &d){
  this->age = d.age;
  this->name = d.name;
  this->sex = d.sex;
 }
 //重載相等符號(hào)
 bool operator == (const dNode &d){
  return name == d.name && age == d.age && sex == sex;
 }
 //按照年齡重載大于符號(hào)
 bool operator > (const dNode &d){
  return age > d.age;
 }
 //按照年齡重載小于符號(hào)
 bool operator < (const dNode &d){
  return age < d.age;
 }

};
//定義二叉查找樹(shù)的節(jié)點(diǎn)
//這里規(guī)定樹(shù)中沒(méi)有重復(fù)節(jié)點(diǎn)，這里需要對(duì)一個(gè)節(jié)點(diǎn)記錄出現(xiàn)多少次
class bstNode{
public: 
 bstNode *left;
 bstNode *right;
 bstNode *parent; //執(zhí)行父親，便于向上訪問(wèn)，如果數(shù)據(jù)量大，并且向上找的使用率不大就不要來(lái)減少空間
 dNode data;  //該節(jié)點(diǎn)在樹(shù)中出現(xiàn)的次數(shù)
 int count;
 bstNode(){
  left = right = parent = NULL;
  count = 1;
 }
};
//定義二叉樹(shù)
class bst{
private:
 //清理整棵樹(shù)
 //注意，一定一定要后續(xù)遍歷的方法清理
 void destory(bstNode *cur){
  if(NULL == cur){
   return;
  }
  cout << "clearing" << endl;
  destory(cur->left);
  destory(cur->right);
  delete cur; //后續(xù)清理
 }
 //真正的刪除節(jié)點(diǎn)
 void _del(bstNode * cur, bstNode *delNode);
public:
 bstNode * root = NULL;
 bst(){
  root = NULL;
 }
 //插入,返回值是便于構(gòu)造parent關(guān)系
 bstNode * insert(bstNode *& cur, dNode data);
 //搜索
 bstNode * search(bstNode * cur, dNode data);
 //先序遍歷
 void pre_raversal(bstNode *cur);
 //返回cur為根的節(jié)點(diǎn)的最小值
 bstNode * minNode(bstNode *cur);
 //得到cur節(jié)點(diǎn)的后繼
 bstNode * succNode(bstNode *cur);
 //刪除節(jié)點(diǎn)，如果count大于1就將count - 1，如果count==1就清除該節(jié)點(diǎn),返回清除的節(jié)點(diǎn)的地址
 bstNode * del(bstNode *cur, dNode data);
 //構(gòu)造函數(shù)對(duì)樹(shù)做清理工作
 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; //如果根節(jié)點(diǎn)是空，就返回空
 }else{
  if(NULL != cur->left){
   return minNode(cur->left);
  }
 }
}
/**
* 非遞歸
* 后繼就是比cur節(jié)點(diǎn)剛好大一點(diǎn)兒的節(jié)點(diǎn)A（排序之后），那么思
* 路就是找cur節(jié)點(diǎn)的右子樹(shù)中的最小值或者是在cur的祖先中找到第一個(gè)比剛好大一點(diǎn)兒的那個(gè)節(jié)點(diǎn)
* ***找到A有兩種情況：
* 1.cur節(jié)點(diǎn)有右子樹(shù)，那么就找右子樹(shù)的最小值節(jié)點(diǎn)就好了
* 2.cur節(jié)點(diǎn)沒(méi)有右子樹(shù)，那么一級(jí)一級(jí)的向祖先找，直到某個(gè)祖先節(jié)點(diǎn)A滿足，
*   A的左孩子是cur的祖先，因?yàn)楫?dāng)A的左孩子是cur祖先就說(shuō)明查找路線在想右
*   偏了，之前一直是往左邊偏
*/
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;
}

/**
*
* 刪除c節(jié)點(diǎn),這個(gè)是最難的
* 規(guī)定：要?jiǎng)h除的節(jié)點(diǎn)是c， c的父節(jié)點(diǎn)是p， c的后繼是s，c的左孩子是l，有孩子是r
* 刪除c整個(gè)節(jié)點(diǎn)（不是count-1）分三種情況
* 1. c節(jié)點(diǎn)沒(méi)有孩子，直接刪除
* 2. c節(jié)點(diǎn)有一個(gè)孩子，那么直接將孩子節(jié)點(diǎn)（l或r）指向c的父節(jié)點(diǎn)p（p也要執(zhí)行l(wèi)或r）
* 3. c有兩個(gè)孩子，那么需要用后繼節(jié)s點(diǎn)里面的數(shù)據(jù)掉替換c節(jié)點(diǎn)里面的數(shù)據(jù)，然后再刪除s節(jié)點(diǎn)
*    同時(shí)需要將s父子之間的指向關(guān)系處理好
*/
void bst::_del(bstNode * cur, bstNode *delNode){
 if(NULL == delNode->left || NULL == delNode->right){
  //待續(xù)
 }
}

/**
*接口：
*跟count有關(guān)的刪除
*/
bstNode * bst::del(bstNode *cur, dNode data){
 //先找到需要?jiǎng)h除的節(jié)點(diǎn)
 bstNode * delNode = this->search(cur, data);
 if(NULL == delNode) //沒(méi)有找到該節(jié)點(diǎn)，無(wú)需刪除
  return NULL;
 if(delNode->count == 1){
  _del(this->root, delNode);
 }else{
  delNode->count--;
 }
}

int main(){
 bst *root = new bst();
 //構(gòu)造50個(gè)人， 重復(fù)的雖然在樹(shù)中不會(huì)重復(fù)插入，但是會(huì)被計(jì)數(shù)
 int num = 50;
 for(int i = 0; i < num; i++){
  dNode * newData = new dNode("Luo", rand() % 15, rand() % 2);
  root->insert(root->root, *newData);
 }
 //前序遍歷
 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 << "沒(méi)有找到該節(jié)點(diǎn)" << endl;
 }else{
  cout << "count: " << searchNode->count << endl;
  searchNode->data.show();
 }
 //清理整棵樹(shù)
 delete root;

 return 0;
}