C++簡單實(shí)現(xiàn)
涉及練習(xí)題目：平衡二叉樹的基本操作
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
using namespace std;
//二叉樹節(jié)點(diǎn)定義，由于需要算平衡因子故在一般二叉樹的基礎(chǔ)上增加height屬性
struct node{
int data, height;
struct node *lchild;
struct node *rchild;
};
//獲取某個(gè)節(jié)點(diǎn)的高度片仿，高度從葉子節(jié)點(diǎn)算起砂豌，葉子節(jié)點(diǎn)高度為1
int getHeight(node *root){
if(root == NULL)
return 0;
return root->height;
}
//更新某個(gè)節(jié)點(diǎn)的高度，取其左右子樹中較大的一個(gè)
void updateHeight(node *root){
root->height = max(getHeight(root->lchild), getHeight(root->rchild)) + 1;
}
//獲取某個(gè)節(jié)點(diǎn)的平衡因子筐摘，為左子樹高度減去右子樹高度
int getBaFa(node *root){
return getHeight(root->lchild) - getHeight(root->rchild);
}
//平衡二叉樹的左旋操作
void L(node* &root){
//使用temp首先指向需要左旋的節(jié)點(diǎn)的右子樹
node *temp = root->rchild;
//進(jìn)行左旋操作咖熟，前提保證二叉樹的大小順序不變馍管，即仍是一棵二叉查找樹
root->rchild = temp->lchild;
temp->lchild = root;
//左旋后更新兩個(gè)變換后的節(jié)點(diǎn)的高度，注意順序首先更新root因?yàn)楝F(xiàn)在root已經(jīng)成為temp的子節(jié)點(diǎn)
//應(yīng)該從上到下更新
updateHeight(root);
updateHeight(temp);
//左旋后的根結(jié)點(diǎn)變?yōu)榱藅emp
root = temp;
}
//右旋操作罗捎，和左旋操作相同
void R(node* &root){
node *temp = root->lchild;
root->lchild = temp->rchild;
temp->rchild = root;
updateHeight(root);
updateHeight(temp);
root = temp;
}
//平衡二叉樹的元素插入桨菜，和一般二叉查找樹的不同是需要在插入后判斷是否平衡
//即需要實(shí)時(shí)更新節(jié)點(diǎn)的高度雷激，計(jì)算平衡因子承桥，并進(jìn)行旋轉(zhuǎn)操作
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);
//更新當(dāng)前節(jié)點(diǎn)的高度
updateHeight(root);
//如果平衡因子變?yōu)?了凶异，表示出現(xiàn)了不平衡現(xiàn)象
if(getBaFa(root) == 2){
//不平衡的現(xiàn)象有兩種剩彬，一種是LL型，一種是LR型母廷，需根據(jù)左孩子的平衡因子判斷
//為1時(shí)是LL型氓鄙，直接對前節(jié)點(diǎn)右旋即可
//為-1時(shí)是LR型抖拦，需要先對左孩子進(jìn)行左旋态罪，再對當(dāng)前節(jié)點(diǎn)進(jìn)行右旋
if(getBaFa(root->lchild) == 1)
R(root);
else if(getBaFa(root->lchild) == -1){
L(root->lchild);
R(root);
}
}
}
else{
//插入右子樹复颈，相關(guān)的情況和插入左子樹相同君纫，不平衡的情況仍然有兩種
//一種是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;
//等于查找的數(shù)即返回1表示查找到
if(x == root->data)
return 1;
//小于時(shí)在左子樹查找
else if(x < root->data)
search(root->lchild, x);
//大于時(shí)在右子樹查找
else
search(root->rchild, x);
}
int main() {
int n, k;
while(scanf("%d%d", &n, &k) != EOF) {
node *root = NULL;
int a;
//輸入n個(gè)數(shù)構(gòu)建平衡二叉樹
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;
}
