c++实现二叉查找树示例
代码如下:
/**
实现二叉查找树的基本功能
*/
#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;
}
