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;
}
