梦里京华

用户名：508304482

访问量：8697

签　名：

等　　级
排　　名	876
经　　验	3561
参赛次数	4
文章发表	18
年　　龄	0
在职情况	学生
学　　校	XJTU
专　　业

　　自我简介：

TA的其他文章

信息学奥赛一本通T1291-数字组合（C++代码）
浏览：954

数据结构-一元多项式加法-题解(C++代码)
浏览：770

数据结构-无向图的连通分量和生成树-题解(C++代码)
浏览：672

你可能喜欢

C语言训练-求PI* （C语言代码）（正确结果竟然是谜一样的3.141591）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）用函数传参的方法

数据结构-平衡二叉树的基本操作-题解(C++代码)

　　作者: 梦里京华　　　　发表时间：2020-03-17 12:31:26 浏览：505　|　评论：0　

原题链接：数据结构-平衡二叉树的基本操作

```cpp
#include <iostream>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef struct Node
{
    int data;
    int height;
    struct Node *lchild = NULL;
    struct Node *rchild = NULL;
} * PNode;
int getHeight(PNode p);
int balance(PNode p);
PNode ll_rotate(PNode y);
PNode rr_rotate(PNode y);
PNode lr_rotate(PNode y);
PNode rl_rotate(PNode y);
PNode insert(PNode p, int a);
void search(PNode T, bool &is, int a);
void postOrder(PNode &p);
int main()
{
    PNode T = NULL;
    int n, m, a;
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
    {
        cin >> a;
        T = insert(T, a);
    }
    for (int i = 0; i < m; ++i)
    {
        bool is = false;
        cin >> a;
        search(T, is, a);
        if (is)
        {
            cout << "1 ";
        }
        else
        {
            cout << "0 ";
        }
    }
    cout << endl;
    postOrder(T);
    system("pause");
    return 0;
}

int getHeight(PNode p)
{
    if (p)
    {
        return p->height;
    }
    else
    {
        return 0;
    }
}

int balance(PNode p)
{
    if (p)
    {
        return getHeight(p->lchild) - getHeight(p->rchild);
    }
    else
    {
        return 0;
    }
}
PNode insert(PNode p, int a)
{
    if (p)
    {
        if (p->data > a)
        {
            p->lchild = insert(p->lchild, a);
        }
        if (p->data < a)
        {
            p->rchild = insert(p->rchild, a);
        }
    }
    else
    {
        p = new Node;
        p->data = a;
    }
    p->height = max(getHeight(p->lchild), getHeight(p->rchild)) + 1;
    int b = balance(p);
    if (b > 1 && a < p->lchild->data)
    { //LL型
        return ll_rotate(p);
    }
    if (b > 1 && a > p->lchild->data)
    { //LR
        return lr_rotate(p);
    }
    if (b < -1 && a < p->rchild->data)
    { //RL
        return rl_rotate(p);
    }
    if (b < -1 && a > p->rchild->data)
    { //RR
        return rr_rotate(p);
    }
    return p;
}

PNode ll_rotate(PNode y)
{
    PNode x = y->lchild;
    y->lchild == x->rchild;
    x->rchild = y;
    y->height = max(getHeight(y->lchild), getHeight(y->rchild)) + 1;
    x->height = max(getHeight(x->lchild), getHeight(x->rchild)) + 1; //必须先计算子树(y)的高度再计算根(x)的高度。
                                                                     //这两行不可换位置
    return x;
}

PNode rr_rotate(PNode y)
{
    PNode x = y->rchild;
    y->rchild = x->lchild;
    x->lchild = y;
    y->height = max(getHeight(y->lchild), getHeight(y->rchild)) + 1;
    x->height = max(getHeight(x->lchild), getHeight(y->rchild)) + 1;
    return x;
}

PNode lr_rotate(PNode y)
{
    y->lchild = rr_rotate(y->lchild);
    return ll_rotate(y);
}

PNode rl_rotate(PNode y)
{
    y->rchild = ll_rotate(y->rchild);
    return rr_rotate(y);
}

void search(PNode T, bool &is, int a)
{
    if (T)
    {
        if (T->data == a)
        {
            is = true;
        }
        else if (a < T->data)
        {
            search(T->lchild, is, a);
        }
        else
        {
            search(T->rchild, is, a);
        }
    }
    else
    {
        is = false;
    }
}

void postOrder(PNode &p)
{
    if (p)
    {
        postOrder(p->lchild);
        postOrder(p->rchild);
        delete p;
    }
}
```

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

梦里京华

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

（格式错误） qq290048663 碰巧告知我吧

C语言训练-求PI* （C语言代码）（正确结果竟然是谜一样的3.141591）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）用函数传参的方法

【回文数(二)】（C语言代码）

数据结构-平衡二叉树的基本操作-题解(C++代码)

评论区

精彩推荐

C语言训练-计算：t=1-1/(22)-1/(33)-...-1/(m*m) （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

ASCII帮了大忙

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

求组合数（C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

出圈】指针malloc版

简单的a+b （C语言代码）

简单的a+b （C语言代码）

梦里京华

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

（格式错误） qq290048663 碰巧告知我吧

C语言训练-求PI* （C语言代码）（正确结果竟然是谜一样的3.141591）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码） 用函数传参的方法

【回文数(二)】 （C语言代码）

数据结构-平衡二叉树的基本操作-题解(C++代码)

评论区

精彩推荐

C语言训练-计算：t=1-1/(2*2)-1/(3*3)-...-1/(m*m) （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

ASCII帮了大忙

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

求组合数 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

出圈】指针malloc版

简单的a+b （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）用函数传参的方法

【回文数(二)】（C语言代码）

　　评论区

C语言训练-计算：t=1-1/(22)-1/(33)-...-1/(m*m) （C语言代码）

求组合数（C语言代码）