数据结构之 平衡二叉树的建立

2/10/2017来源:ASP.NET技巧人气:252

数据结构实验之查找二:平衡二叉树 Time Limit: 400MS Memory Limit: 65536KB PRoblem Description

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

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

输出平衡二叉树的树根。 Example Input

5 88 70 61 96 120

Example Output

70

#include<stdio.h> #include<string.h> #include<stdlib.h> typedef struct node { int data, d; struct node *lt, *rt; }ST; int max(int a, int b) { if(a < b) return b; else return a; } int deep(ST *root) { if(!root) return -1; else return root->d; } ST *LL(ST *root) { ST *p; p = root->lt; root->lt = p->rt; p->rt = root; root->d = max(deep(root->lt), deep(root->rt)) + 1; return p; } ST *RR(ST *root) { ST *p; p = root->rt; root->rt = p->lt; p->lt = root; root->d = max(deep(root->lt), deep(root->rt)) + 1; return p; } ST *LR(ST *root) { root->lt = RR(root->lt); root = LL(root); return root; } ST *RL(ST *root) { root->rt = LL(root->rt); root = RR(root); return root; } ST *insert(int x, ST *root) { if(!root) { root = (ST *)malloc(sizeof(ST)); root->data = x; root->d = 0; root->lt = NULL; root->rt = NULL; } else { if(x < root->data) { root->lt = insert(x, root->lt); if(deep(root->lt) - deep(root->rt) > 1) { if(root->lt->data > x) root = LL(root); else root = LR(root); } } else if(x > root->data) { root->rt = insert(x, root->rt); if(deep(root->rt) - deep(root->lt) > 1) { if(root->rt->data < x) root = RR(root); else root = RL(root); } } } root->d = max(deep(root->rt),deep(root->lt)) + 1; return root; } int main() { ST *root; int n, x; while(~scanf("%d", &n)) { root = NULL; while(n--) { scanf("%d", &x); root = insert(x, root); } printf("%d\n", root->data); } return 0; }