数据结构实验之查找二：平衡二叉树

最新推荐文章于 2020-03-28 15:56:44 发布

原创最新推荐文章于 2020-03-28 15:56:44 发布

· 327 阅读

0 ·

版权

二叉树专栏收录该内容

18 篇文章

订阅专栏

本文介绍如何根据给定序列构建平衡二叉树，并实现树的插入操作及四种旋转调整（LL、RR、LR、RL）。通过示例演示了算法的具体实现过程。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

数据结构实验之查找二：平衡二叉树

Time Limit: 400MS Memory limit: 65536K

题目描述

根据给定的输入序列建立一棵平衡二叉树，求出建立的平衡二叉树的树根。

输入

输入一组测试数据。数据的第1行给出一个正整数N(n <= 20)，N表示输入序列的元素个数；第2行给出N个正整数，按数据给定顺序建立平衡二叉树。

输出

输出平衡二叉树的树根。

示例输入

5
88 70 61 96 120

示例输出

提示

来源

xam

示例程序

注意这四种旋转LL，RR，LR，RR，

其实就是两种旋转。

LR可以转化成RR+LL；

RL可以转化成LL+RR;

具体转化过程见上一篇博客。

#include<stdio.h>
 #include<stdlib.h>
 #include<string.h>
 #include<iostream>
 #include<algorithm>
 using namespace std;
 struct node
 {
     int height;
     int data;
     node *lc;
     node *rch;
 };
 int max(int x,int y)
 {
     return x>y?x:y;
 }
 int height (node *p)
 {
     if(p==NULL)
         return -1;
     else return p->height;
 }
 node *LL(node *p2)
 {
     node *p1;
     p1=p2->lc;
     p2->lc=p1->rch;
     p1->rch=p2;
     p2->height=max(height(p2->lc),height(p2->rch))+1;
     p1->height=max(height(p1->lc),height(p1->rch))+1;
     return p1;
 }
 node *RR(node *t2)
 {
     node *t1;
     t1=t2->rch;
     t2->rch=t1->lc;
     t1->lc=t2;
     t2->height=max(height(t2->lc),height(t2->rch))+1;
     t1->height=max(height(t1->rch),t2->height)+1;
     return t1;
 }
 node *LR(node *p3)
 {
     p3->lc=RR(p3->lc);
     return LL(p3);
 }
 node *RL(node *t3)
 {
     t3->rch=LL(t3->rch);
     return RR(t3);      //此处有return 就相当于有了返回的东西
}
node *Insert(node *root, int x)
 {
     if(root==NULL)
     {
         root=new node;
         root->data=x;
         root->height=0;
         root->lc=root->rch=NULL;
     }
     else if (x<root->data)
     {
         root->lc=Insert(root->lc,x);
         if(height(root->lc)-height(root->rch)==2)
         {
             if(x<root->lc->data)
                 root=LL(root);      //对于有返回值的函数调用时，一定要有返回的的东西，此处不能写成LL(root)
             else root=LR(root);
         }
     }
     else if (x>root->data)
     {
         root->rch=Insert(root->rch,x);
         if(height(root->rch)-height(root->lc)==2)
         {
             if(x>root->rch->data)
                 root=RR(root);
             else root=RL(root);
         }
     }


     root->height=max(height(root->rch),height(root->lc))+1;
     return root;
 }
 int main()
 {
     int n,m;
     struct node *root=NULL;
     cin>>n;
     while(n--)
     {

        cin>>m;
         root=Insert(root,m);
     }
     cout<<root->data<<endl;
     return 0;
 }