题目描述
Problem Description
根据给定的输入序列建立一棵平衡二叉树，求出建立的平衡二叉树的树根。
Input
输入一组测试数据。数据的第1行给出一个正整数N(n <= 20)，N表示输入序列的元素个数；第2行给出N个正整数，按数据给定顺序建立平衡二叉树。
Output
输出平衡二叉树的树根。
Sample Input
5
88 70 61 96 120
Sample Output
70
代码 & 分析
要求解平衡二叉树的树根值，直接把整棵BBST建立出来就好了。注意建立BBST的四种情况。
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
struct node{
int data;
int depth;
struct node * left;
struct node * right;
};
typedef struct node * tree;
int maxx(int a, int b){
return a>b? a : b;
}
int deep(tree t){
if(t==NULL)
return -1;
else{
return t->depth;
}
}
tree LL(tree &t){ // LL情况 进行向右的顺时针旋转
tree p;
p=t->left;
t->left = p->right;
p->right = t;
p->depth = maxx(deep(p->left), t->depth) + 1;
t->depth = maxx(deep(t->left), deep(t->right)) + 1;
return p;
}
tree RR(tree &t){ //RR情况 其实很好记的 很对称 向左逆时针旋转
tree p;
p= t->right;
t->right = p->left;
p->left = t;
p->depth = maxx(deep(p->right), t->depth) + 1;
t->depth = maxx(deep(t->left), deep(t->right)) + 1;
return p;
}
tree RL(tree &t){ //搞定前两个基础的情况 直接交给递归 因为剩下的是复合旋转 RL 就是先RR后LL
t->right = LL(t->right);
return RR(t);
}
tree LR(tree &t){ //反之
t->left = RR(t->left);
return LL(t);
}
tree create(tree &t, int x){ //在二叉排序树的基础上稍作改变
if(t==NULL){
t = new node;
t->left = NULL;
t->right = NULL;
t->data = x;
t->depth = 0;
}
else if(x < t->data){
t->left = create(t->left, x);
if(deep(t->left) - deep(t->right) > 1){ //增加的部分就是判断某个点不符合性质则进行改变
if(x < t->left->data)
t=LL(t);
else
t=LR(t);
}
}
else if(x > t->data){
t->right = create(t->right, x);
if(deep(t->right) - deep(t->left) > 1){
if(x > t->right->data)
t = RR(t);
else
t = RL(t);
}
}
t->depth = maxx(deep(t->left), deep(t->right)) + 1; //最后更新这个树节点的深度
return t;
}
int main(){
int n,i,x;
cin>>n;
tree t = NULL;
for(int i=0; i<n; i++){
cin>>x;
t = create(t, x);
}
cout<<t->data<<endl;
}
以上~
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/116782.html
