數(shù)據(jù)結(jié)構(gòu)實驗之查找二：平衡二叉樹 Time Limit: 400MS Memory Limit: 65536KB PRoblem Description
根據(jù)給定的輸入序列建立一棵平衡二叉樹，求出建立的平衡二叉樹的樹根。 Input
輸入一組測試數(shù)據(jù)。數(shù)據(jù)的第1行給出一個正整數(shù)N(n <= 20)，N表示輸入序列的元素個數(shù)；第2行給出N個正整數(shù)，按數(shù)據(jù)給定順序建立平衡二叉樹。 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;}新聞熱點
疑難解答
