#include
#include
#include
#include
#include

using namespace std;

const int M = 10000;

//定义数据节点
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){}
 //打印节点
 void show(){
  cout 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 right);
}
bstNode * bst::minNode(bstNode *cur){
 if(NULL == cur){
  return NULL; //如果根节点是空，就返回空
 }else{
  if(NULL != cur->left){
   return minNode(cur->left);
  }
 }
}
/**
* 非递归
* 后继就是比cur节点刚好大一点儿的节点A（排序之后），那么思
* 路就是找cur节点的右子树中的最小值或者是在cur的祖先中找到第一个比刚好大一点儿的那个节点
* ***找到A有两种情况：
* 1.cur节点有右子树，那么就找右子树的最小值节点就好了
* 2.cur节点没有右子树，那么一级一级的向祖先找，直到某个祖先节点A满足，
*   A的左孩子是cur的祖先，因为当A的左孩子是cur祖先就说明查找路线在想右
*   偏了，之前一直是往左边偏
*/
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节点,这个是最难的
* 规定：要删除的节点是c， c的父节点是p， c的后继是s，c的左孩子是l，有孩子是r
* 删除c整个节点（不是count-1）分三种情况
* 1. c节点没有孩子，直接删除
* 2. c节点有一个孩子，那么直接将孩子节点（l或r）指向c的父节点p（p也要执行l或r）
* 3. c有两个孩子，那么需要用后继节s点里面的数据掉替换c节点里面的数据，然后再删除s节点
*    同时需要将s父子之间的指向关系处理好
*/
void bst::_del(bstNode * cur, bstNode *delNode){
 if(NULL == delNode->left || NULL == delNode->right){
  //待续
 }
}

/**
*接口：
*跟count有关的删除
*/
bstNode * bst::del(bstNode *cur, dNode data){
 //先找到需要删除的节点
 bstNode * delNode = this->search(cur, data);
 if(NULL == delNode) //没有找到该节点，无需删除
  return NULL;
 if(delNode->count == 1){
  _del(this->root, delNode);
 }else{
  delNode->count--;
 }
}

int main(){
 bst *root = new bst();
 //构造50个人， 重复的虽然在树中不会重复插入，但是会被计数
 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