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

本文介绍如何根据给定序列构建平衡二叉树,并实现树的插入操作及四种旋转调整(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

示例输出

70

提示

 

来源

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


评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值