平衡二叉查找树实现(C 实现)
程序员文章站
2022-03-23 09:23:00
...
AVL树的简单实现代码。
主要理解了左旋、右旋还有双旋就好写了。
- 需要旋转的地方就是插入和删除的时候判断一下balance是不是满足旋转的条件(也就是左右子树不平衡)。
- 在插入子树的时候改变一下父节点的height,从子叶递归上来,最后整条路上节点的height都会修改,也就完成了高度变化。
当然在旋转的时候因为节点会往下转,所以不管左旋右旋都需要根据左右子树的高度重新获得height。下面是代码。
#include <iostream>
#include <string>
#define BALANCE_FACTOR 1
using namespace std;
typedef struct student{
int sid;
int age;
int score;
char * name;
char * expert;
char * phone;
}student;
typedef struct avlnode{
int id;
int height;
struct student * studentpoint;
struct avlnode * left;
struct avlnode * right;
}node;
node * findMin(node * root){
while(root->left)
root = root->left;
return root;
}
int height(node * root){
if(root){
return root->height;
}
else{
return -1;
}
}
node * routateWithRight(node * root){
node * leftChlid = root->left;
root->left = leftChlid->right;
root->height = max(height(root->left),height(root->right))+1;
leftChlid->right = root;
leftChlid->height = max(height(leftChlid->left),height(leftChlid->right))+1;
return leftChlid;
}
node * routateWithLeft(node * root){
node * rightChlid = root->right;
root->right = rightChlid->left;
root->height = max(height(root->left),height(root->right))+1;
rightChlid->left = root;
rightChlid->height = max(height(rightChlid->left),height(rightChlid->right))+1;
return rightChlid;
}
/*
* 以下为两个双旋为试作功能
*/
node * routateWithLeftAndRight(node * root){
root->left = routateWithLeft(root->left);
root = routateWithRight(root);
return root;
}
node * routateWithRightAndLeft(node * root){
root->right = routateWithRight(root->right);
root = routateWithLeft(root);
return root;
}
node * balance(node * root){
if(root) {
int lheight = height(root->left);
int rheight = height(root->right);
if (lheight - rheight > BALANCE_FACTOR) {
if (height(root->left->left) >= height(root->left->right)) {
root = routateWithRight(root);
} else {
root = routateWithLeftAndRight(root);
}
} else if (rheight - lheight > BALANCE_FACTOR) {
if (height(root->right->right) >= height(root->right->left)) {
root = routateWithLeft(root);
} else {
root = routateWithRightAndLeft(root);
}
}
}
return root;//如果空树,直接返回
}
student * getTemplet(){
int sid;
int age;
int score;
char * name;
char * expert;
char * phone;
cout<<"输入学生学号 "<<endl;
cin>>sid;
cout<<"输入学生姓名 "<<endl;
name = new char[30];
cin>>name;
cout<<"输入学生年龄"<<endl;
cin>>age;
cout<<"输入学生手机号"<<endl;
phone = new char[11];
cin>>phone;
cout<<"输入学生专业"<<endl;
expert = new char[30];
cin>>expert;
cout<<"输入学生成绩"<<endl;
cin>>score;
student * student1 = new student;
student1->sid = sid;
student1->age = age;
student1->name = name;
student1->expert = expert;
student1->phone = phone;
student1->score = score;
return student1;
}
node * insert(node * root,int id,student * s){
if(root == NULL){
root = new node;
root->id = id;
root->studentpoint = s;
root->height = 0;
root->left = root->right = NULL;
cout<<"添加成功"<<endl;
return root;
}
else {
if (root->id > id) {
root->left = insert(root->left, id,s);
} else if (root->id < id) {
root->right = insert(root->right, id,s);
} else {
cout << "Exist the node" << endl;//因为没有创建节点,所以所有节点的高度都不变,而插入中算高度时根据左右子树最大值计算出来的,所以不用担心这
}
}
root->height = max(height(root->left),height(root->right))+1;
return balance(root);
}
node * deleted(node * root,int id){
if(root){
if(root->id>id){
root->left = deleted(root->left,id);
}
else if(root->id<id){
root->right = deleted(root->right,id);
}
else{
cout<<"删除了 id: "<<root->id<<endl;
if(root->left && root->right) {
node *minNode = findMin(root->right);
root->id = minNode->id;
root->studentpoint = minNode->studentpoint;
root->right = deleted(root->right,minNode->id);
}
else if(root->left){
node * leftChlid = root->left;
free(root);
return leftChlid;
}
else{
node * rightChlid = root->right;
free(root);
return rightChlid;
}
}
}
else{
cout<<"Not exist node"<<endl;
}
return balance(root);
}
node * update(node * root,int id,student * s){
if(root){
if(root->id>id){
root->left = update(root->left,id,s);
}
else if(root->id<id){
root->right = update(root->right,id,s);
}
else{
root->id = s->sid;
root->studentpoint = s;
cout<<"修改成功"<<endl;
}
}
else{
cout<<"Not exist node"<<endl;
}
return root;
}
node* query(node * root,int id){
if(root){
if(root->id>id){
root->left = query(root->left,id);
}
else if(root->id<id){
root->right = query(root->right,id);
}
else{
cout<<"-------------------------------------"<<endl;
cout<<"id: "<<root->id<<" tree-height: "<<root->height<<endl;
cout<<"name: "<<root->studentpoint->name<<endl;
cout<<"age: "<<root->studentpoint->age<<endl;
cout<<"expert: "<<root->studentpoint->expert<<endl;
cout<<"phone: "<<root->studentpoint->phone<<endl;
cout<<"|score: "<<root->studentpoint->score<<endl;
cout<<"-------------------------------------"<<endl;
}
}
else{
cout<<"Not exist node"<<endl;
}
return root;
}
void queryAll(node * root){
if(root){
queryAll(root->left);
cout<<"-------------------------------------"<<endl;
cout<<"|id: "<<root->id<<" tree-height: "<<root->height<<endl;
cout<<"|name: "<<root->studentpoint->name<<endl;
cout<<"|age: "<<root->studentpoint->age<<endl;
cout<<"|expert: "<<root->studentpoint->expert<<endl;
cout<<"|phone: "<<root->studentpoint->phone<<endl;
cout<<"|score: "<<root->studentpoint->score<<endl;
cout<<"-------------------------------------"<<endl;
queryAll(root->right);
}
}
void queryByName(node * root,char * expert){
if(root){
if(strcmp(root->studentpoint->expert,expert)==0){
cout<<"-------------------------------------"<<endl;
cout<<"id: "<<root->id<<" tree-height: "<<root->height<<endl;
cout<<"name: "<<root->studentpoint->name<<endl;
cout<<"age: "<<root->studentpoint->age<<endl;
cout<<"expert: "<<root->studentpoint->expert<<endl;
cout<<"phone: "<<root->studentpoint->phone<<endl;
cout<<"score: "<<root->studentpoint->score<<endl;
cout<<"-------------------------------------"<<endl;
}
queryByName(root->left,expert);
queryByName(root->right,expert);
}
}
void queryByScore(node * root,int low,int high){
if(root){
if(root->studentpoint->score>=low && root->studentpoint->score<=high){
cout<<"id: "<<root->id<<" tree-height: "<<root->height<<endl;
cout<<"name: "<<root->studentpoint->name<<endl;
cout<<"age: "<<root->studentpoint->age<<endl;
cout<<"expert: "<<root->studentpoint->expert<<endl;
cout<<"phone: "<<root->studentpoint->phone<<endl;
cout<<"score: "<<root->studentpoint->score<<endl;
}
queryByScore(root->left,low,high);
queryByScore(root->right,low,high);
}
}
void countStudent(node * root,student * stu[],int & n){
if(root){
stu[n] = root->studentpoint;
n++;
countStudent(root->left,stu,n);
countStudent(root->right,stu,n);
}
}
void sort(node * root,int judge){
student * stu[1000];
int count = 0;
countStudent(root,stu,count);
if(judge == 0){
int j;
for(int i = 1;i<count;i++){
student * temp = stu[i];
for(j= i ;j>0 && temp->score<stu[j-1]->score;j--){
stu[j] = stu[j-1];
}
stu[j] = temp;
}
for(int i=0;i<count;i++){
cout<<"-------------------------------------"<<endl;
cout<<"id: "<<stu[i]->sid<<endl;
cout<<"name: "<<stu[i]->name<<endl;
cout<<"age: "<<stu[i]->age<<endl;
cout<<"expert: "<<stu[i]->expert<<endl;
cout<<"phone: "<<stu[i]->phone<<endl;
cout<<"score: "<<stu[i]->score<<endl;
cout<<"-------------------------------------"<<endl;
}
}
else if(judge == 1){
queryAll(root);
}
}
void handler(){
int botton;
student * stu;
node * root = NULL;
while(1){
cout<<"#########################################################################"<<endl;
cout<<"# Student Manager System v_1.0.0.1 #"<<endl;
cout<<"# #"<<endl;
cout<<"# #"<<endl;
cout<<"# 1.插入学生信息 请按1 #"<<endl;
cout<<"# 2.删除学生信息 请按2 #"<<endl;
cout<<"# 3.修改学生信息 请按3 #"<<endl;
cout<<"# 4.按学号查询学生信息 请按4 #"<<endl;
cout<<"# 5.按姓名查询学生信息 请按5 #"<<endl;
cout<<"# 6.按学生成绩分段查找学生信息 请按6 #"<<endl;
cout<<"# 7.查询所有学生 请按7 #"<<endl;
cout<<"# 8.成绩排序 请按8 #"<<endl;
cout<<"# 9.学号排序 请按9 #"<<endl;
cout<<"#########################################################################"<<endl;
fflush(stdin);
cin>>botton;
switch (botton){
case 1:{
stu = getTemplet();
root = insert(root,stu->sid,stu);
break;
}
case 2:{
int id;
cout<<"输入要删除的学生id"<<endl;
cin>>id;
root = deleted(root,id);
break;
}
case 3:{
int id;
cout<<"输入要修改的学生id"<<endl;
cin>>id;
cout<<"输入修改内容"<<endl;
stu = getTemplet();
root = update(root,id,stu);
break;
}
case 4:{
int id;
cout<<"输入要查找的学生id"<<endl;
cin>>id;
root = query(root,id);
break;
}
case 5:{
char * name;
name = new char[30];
cout<<"输入要查询的姓名"<<endl;
cin>>name;
queryByName(root,name);
break;
}
case 6:{
int low;
int high;
cout<<"输入低分段"<<endl;
cin>>low;
cout<<"输入高分段"<<endl;
cin>>high;
queryByScore(root,low,high);
break;
}
case 7:{
queryAll(root);
break;
}
case 8:{
sort(root,0);
break;
}
case 9:{
sort(root,1);
break;
}
case 0:{
exit(0);
break;
}
default:{
cout<<"错误指令"<<endl;
}
}
}
}
int main() {
handler();
}
上一篇: 备战NOIP——模板复习1
下一篇: 金融数据库TDSQL