数据结构实验之查找二:平衡二叉树

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

大部分摘自,略有不同http://www.cnblogs.com/You0/p/4459719.html 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 <iostream> #include <stdio.h> #include <cstring> #include <cstdlib> using namespace std; bool taller; enum wek{LH, EH, RH}; struct Node { int data; wek TQ; Node *left; Node *right; Node():data(0),TQ(EH),left(NULL), right(NULL){} }; Node *newNode(){return new Node;} int creat(Node *&T, int i); void leftbalance(Node *&T); void rightbalance(Node *&T); void l_xuan(Node *&T); void r_xuan(Node *&T); int main() { int t; while(~scanf("%d", &t)) { Node *T=NULL; while(t--) { int i; scanf("%d", &i); creat(T,i); } printf("%d\n", T->data); } return 0; } int creat(Node *&T, int i) { if(!T) { T=newNode(); taller=true; T->data=i; } else { if(T->data==i)return 0; else if(T->data>i) { if(!creat(T->left, i))return 0; if(taller) switch (T->TQ) { case LH: leftbalance(T); taller=false; break; case EH: taller=true; T->TQ=LH; break; case RH: T->TQ=EH; taller=false; break; } } else { if(!creat(T->right, i))return 0; if(taller) switch (T->TQ) { case LH: T->TQ=EH; taller=false; break; case EH: T->TQ=RH; taller=true; break; case RH: rightbalance(T); taller=false; break; } } } return 1; } void leftbalance(Node *&T) { Node *&L=(T->left); switch (L->TQ) { case LH: T->TQ=EH; L->TQ=EH; r_xuan(T); break; case EH: T->TQ=LH; taller=true; break; case RH: Node *&Lr=(L->right); switch (Lr->TQ) { case RH: T->TQ=EH; L->TQ=LH; break; case EH: T->TQ=EH; L->TQ=EH; break; case LH: T->TQ=RH; L->TQ=EH; } Lr->TQ=EH; l_xuan(L); r_xuan(T); } } void rightbalance(Node *&T) { Node *&R=T->right; switch (R->TQ) { case EH: T->TQ=RH; taller=true; break; case RH: T->TQ=EH; R->TQ=EH; l_xuan(T); break; case LH: Node *&Rl=R->left; switch (Rl->TQ) { case LH: T->TQ=EH;//这部分有小的改动,可能有错 R->TQ=RH; break; case EH: T->TQ=EH; R->TQ=EH; break; case RH: R->TQ=EH; T->TQ=LH; break; } Rl->TQ=EH; r_xuan(R); l_xuan(T); break; } } void r_xuan(Node *&T) { Node *L=T->left; T->left=L->right; L->right=T; T=L; } void l_xuan(Node *&T) { Node *R=T->right; T->right=R->left; R->left=T; T=R; }