c++完成二叉查找樹示例。本站提示廣大學習愛好者：（c++完成二叉查找樹示例）文章只能為提供參考，不一定能成為您想要的結果。以下是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;
}
