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

2019-11-10 18:24:17

字体：大中小

来源：转载

供稿：网友

数据结构实验之查找二：平衡二叉树 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

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

上一篇：jrtplib使用CMake进行编译

下一篇：算法训练未名湖边的烦恼 dp