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

2019-11-10 18:07:16

字体：大中小

来源：转载

供稿：网友

大部分摘自，略有不同http://www.cnblogs.com/You0/p/4459719.html PRoblem Description

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

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

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

588 70 61 96 120

Example Output

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

上一篇：Codeforces 100726A 或 POJ 3842

下一篇：mybatis 批量insert , update

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注