/**  实现二叉查找树的基本功能 */ #include <iostream> #include <cstring> #include <algorithm> #include <cstdio> #include <string> 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 << "name: " << this->name << endl;   cout << "age: " << this->age << endl;   cout << "sex: " << this->sex << endl;   cout << "******************************" << endl;  }  //重载赋值符号  bool operator = (const dNode &d){   this->age = d.age;   this->name = d.name;   this->sex = d.sex;  }  //重载相等符号  bool operator == (const dNode &d){   return name == d.name && age == d.age && sex == sex;  }  //按照年龄重载大于符号  bool operator > (const dNode &d){   return age > d.age;  }  //按照年龄重载小于符号  bool operator < (const dNode &d){   return age < d.age;  } }; //定义二叉查找树的节点 //这里规定树中没有重复节点，这里需要对一个节点记录出现多少次 class bstNode{ public:   bstNode *left;  bstNode *right;  bstNode *parent; //执行父亲，便于向上访问，如果数据量大，并且向上找的使用率不大就不要来减少空间  dNode data;  //该节点在树中出现的次数  int count;  bstNode(){   left = right = parent = NULL;   count = 1;  } }; //定义二叉树 class bst{ private:  //清理整棵树  //注意，一定一定要后续遍历的方法清理  void destory(bstNode *cur){   if(NULL == cur){    return;   }   cout << "clearing" << endl;   destory(cur->left);   destory(cur->right);   delete cur; //后续清理  }  //真正的删除节点  void _del(bstNode * cur, bstNode *delNode); public:  bstNode * root = NULL;  bst(){   root = NULL;  }  //插入,返回值是便于构造parent关系  bstNode * insert(bstNode *& cur, dNode data);  //搜索  bstNode * search(bstNode * cur, dNode data);  //先序遍历  void pre_raversal(bstNode *cur);  //返回cur为根的节点的最小值  bstNode * minNode(bstNode *cur);  //得到cur节点的后继  bstNode * succNode(bstNode *cur);  //删除节点，如果count大于1就将count - 1，如果count==1就清除该节点,返回清除的节点的地址  bstNode * del(bstNode *cur, dNode data);  //构造函数对树做清理工作  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; //如果根节点是空，就返回空  }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 << "#######search a Node ##########" << endl;  if(NULL == searchNode){   cout << "没有找到该节点" << endl;  }else{   cout << "count: " << searchNode->count << endl;   searchNode->data.show();  }  //清理整棵树  delete root;  return 0; }