欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

平衡二叉查找树实现(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();
}