长沙市人事局,潍坊交通事故,江苏常州邮编
#include <iostream>
using namespace std;
struct node {
int val;
struct node *left, *right;
};
node *rotateleft(node *root) {//左旋 可以记下来 余下都可反推
node *t = root->right;
root->right = t->left;
t->left = root;
return t;
}
node *rotateright(node *root) {//右旋
node *t = root->left;
root->left = t->right;
t->right = root;
return t;
}
node *rotateleftright(node *root) {//先左子树左旋在整体右旋
root->left = rotateleft(root->left);
return rotateright(root);
}
node *rotaterightleft(node *root) {//先右子树右旋在整体左旋
root->right = rotateright(root->right);
return rotateleft(root);
}
int getheight(node *root) {//获取二叉树高度,用于判断时候需要平衡调整
if(root == null) return 0;
return max(getheight(root->left), getheight(root->right)) + 1;
}
node *insert(node *root, int val) {//此为二叉排序树的插入算法加入平衡调整
if(root == null) {
root = new node();
root->val = val;
root->left = root->right = null;
} else if(val < root->val) {
root->left = insert(root->left, val);
if(getheight(root->left) - getheight(root->right) == 2)//左右子树不平衡时
root = val < root->left->val ? rotateright(root) : rotateleftright(root);
} else {
root->right = insert(root->right, val);
if(getheight(root->left) - getheight(root->right) == -2)
root = val > root->right->val ? rotateleft(root) : rotaterightleft(root);
}
return root;
}
int main() {
int n, val;
scanf("%d", &n);
node *root = null;
for(int i = 0; i < n; i++) {
scanf("%d", &val);
root = insert(root, val);
}
printf("%d", root->val);
return 0;
}
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论