数据结构实验之查找二:平衡二叉树
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
Hint
Author
xam
#include <stdio.h>
#include <stdlib.h>
struct node
{int data;int d;struct node *lchild,*rchild;
};int max(int x,int y)
{return x>y ? x:y;
}int Deep(struct node *head)
{if (!head)return -1;else return head->d;
}struct node *LL(struct node *head)//右旋
{struct node *p = head->lchild;head->lchild = p->rchild;p->rchild = head;p->d = max(Deep(p->lchild),Deep(p->rchild))+1;head->d = max(Deep(head->lchild),Deep(head->rchild))+1;return p;
}struct node *RR(struct node *head)//左旋
{struct node *p = head->rchild;head->rchild = p->lchild;p->lchild = head;p->d = max(Deep(p->lchild),Deep(p->rchild))+1;head->d = max(Deep(head->lchild),Deep(head->rchild))+1;return p;
}struct node *LR(struct node *head)
{head->lchild = RR(head->lchild);//先做左旋return LL(head);//在做右旋
}
struct node *RL(struct node *head)
{head->rchild = LL(head->rchild);//先做右旋return RR(head);//在做左旋
}struct node *Creat(struct node *head,int x)
{if (head == NULL){head = (struct node *)malloc (sizeof (struct node));head->data = x;head->d = 0;head->rchild = head->lchild = NULL;}else if (head->data > x){head->lchild = Creat(head->lchild,x);if (Deep(head->lchild)-Deep(head->rchild)>1){if (head->lchild->data > x)head = LL(head);elsehead = LR(head);}}else if (head->data < x){head->rchild = Creat(head->rchild,x);if (Deep(head->rchild)-Deep(head->lchild)>1){if (head->rchild->data > x)head = RL(head);elsehead = RR(head);}}head->d = max(Deep(head->lchild),Deep(head->rchild))+1;return head;
}int main()
{int n,m;scanf ("%d",&n);struct node *head = NULL;for (int i=0; i<n; i++){scanf ("%d",&m);head = Creat(head,m);}printf ("%d\n",head->data);return 0;
}