平衡二叉树的基本操作

平衡二叉树定义及操作原理

C++简单实现

涉及练习题目：平衡二叉树的基本操作

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>


using namespace std;

//二叉树节点定义，由于需要算平衡因子故在一般二叉树的基础上增加height属性 
struct node{
    int data, height;
    struct node *lchild;
    struct node *rchild;
};

//获取某个节点的高度，高度从叶子节点算起，叶子节点高度为1 
int getHeight(node *root){
    if(root == NULL)
        return 0;
    return root->height;
}

//更新某个节点的高度，取其左右子树中较大的一个 
void updateHeight(node *root){
    root->height = max(getHeight(root->lchild), getHeight(root->rchild)) + 1;
}
//获取某个节点的平衡因子，为左子树高度减去右子树高度 
int getBaFa(node *root){
    return getHeight(root->lchild) - getHeight(root->rchild);
}
//平衡二叉树的左旋操作 
void L(node* &root){
    //使用temp首先指向需要左旋的节点的右子树 
    node *temp = root->rchild;
    //进行左旋操作，前提保证二叉树的大小顺序不变，即仍是一棵二叉查找树 
    root->rchild = temp->lchild;
    temp->lchild = root;
    //左旋后更新两个变换后的节点的高度，注意顺序首先更新root因为现在root已经成为temp的子节点
    //应该从上到下更新 
    updateHeight(root);
    updateHeight(temp);
    //左旋后的根结点变为了temp 
    root = temp;
}
//右旋操作，和左旋操作相同 
void R(node* &root){
    node *temp = root->lchild;
    root->lchild = temp->rchild;
    temp->rchild = root;
    updateHeight(root);
    updateHeight(temp);
    root = temp;
}
//平衡二叉树的元素插入，和一般二叉查找树的不同是需要在插入后判断是否平衡
//即需要实时更新节点的高度，计算平衡因子，并进行旋转操作 
void insert(node* &root, int x){
    if(root == NULL){
        root = new node;
        root->data = x;
        root->height = 1;
        root->lchild = root->rchild = NULL;
        return ;
    }
    if(x < root->data){
        //插入到左子树 
        insert(root->lchild, x);
        //更新当前节点的高度 
        updateHeight(root);
        //如果平衡因子变为2了，表示出现了不平衡现象 
        if(getBaFa(root) == 2){
            //不平衡的现象有两种，一种是LL型，一种是LR型，需根据左孩子的平衡因子判断 
            //为1时是LL型，直接对前节点右旋即可
            //为-1时是LR型，需要先对左孩子进行左旋，再对当前节点进行右旋 
            if(getBaFa(root->lchild) == 1)
                R(root);
            else if(getBaFa(root->lchild) == -1){
                L(root->lchild);
                R(root);
            }
        }
        
    }
    else{
        //插入右子树，相关的情况和插入左子树相同，不平衡的情况仍然有两种
        //一种是RR型，一种是Rl型 
        insert(root->rchild, x);
        updateHeight(root);
        if(getBaFa(root) == -2){
            if(getBaFa(root->rchild) == -1)
                L(root);
            else if(getBaFa(root->rchild) == 1){
                R(root->rchild);
                L(root);
            }
        }
    }
}
//平衡二叉树的查找操作 
int search(node* root, int x){
    //为空则返回，表示查找完后仍未查找到 
    if(root == NULL)
        return 0;
    //等于查找的数即返回1表示查找到 
    if(x == root->data)
        return 1;
    //小于时在左子树查找 
    else if(x < root->data)
        search(root->lchild, x);
    //大于时在右子树查找 
    else
        search(root->rchild, x);
}

int main() {
    int n, k;
    while(scanf("%d%d", &n, &k) != EOF) {
        node *root = NULL;
        int a;
        //输入n个数构建平衡二叉树 
        for(int i = 0; i < n; i++){
            scanf("%d", &a);
            insert(root, a);
        }
        //输入元素查找 
        for(int i = 0; i < k; i++){
            scanf("%d", &a);
            if(search(root, a))
                printf("1 ");
            else
                printf("0 "); 
        }
        printf("\n");
    }

    return 0;
}