數據結構實驗之查找二：平衡二叉樹

2019-11-10 18:26:12

字體：大中小

來源：轉載

供稿：網友

大部分摘自，略有不同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;}

上一篇：ffmpeg結構體總結

下一篇：算法學習 -- a+b