优秀的企业网站设计,wordpress 退出块引用,网站建设用阿里还是华为云,番禺龙美村做网站题目描述 根据给定的输入序列建立一棵平衡二叉树#xff0c;求出建立的平衡二叉树的树根。 输入 输入一组测试数据。数据的第1行给出一个正整数N(n 20)#xff0c;N表示输入序列的元素个数#xff1b;第2行给出N个正整数#xff0c;按数据给定顺序建立平衡二叉树。 输… 题目描述 根据给定的输入序列建立一棵平衡二叉树求出建立的平衡二叉树的树根。 输入 输入一组测试数据。数据的第1行给出一个正整数N(n 20)N表示输入序列的元素个数第2行给出N个正整数按数据给定顺序建立平衡二叉树。 输出 输出平衡二叉树的树根。 示例输入 5
88 70 61 96 120 示例输出 70 /*#includestdio.h #includestdlib.h #includestring.h #includealgorithm using namespace std; typedef struct BNode { int data; int d;//记录树的深度 BNode *lchild,*rchild; }*BiTree; int deep(BiTree T) { if(!T) return 0; return T-d; } BiTree LL(BiTree T)//向右旋型 { BiTree p; pT-lchild; T-lchildp-rchild; p-rchildT; p-dmax(deep(p-lchild),deep(p-rchild))1; T-dmax(deep(T-lchild),deep(T-rchild))1; return p; } BiTree RR(BiTree T)//向左型旋 { BiTree p; pT-rchild; T-rchildp-lchild; p-lchildT; p-dmax(deep(p-lchild),deep(p-rchild))1; T-dmax(deep(T-lchild),deep(T-rchild))1; return p; } BiTree LR(BiTree T)//旋转分两步1.以a为根结点的RR旋转 2.以x为根结点的LL旋转 { T-lchildRR(T-lchild); return LL(T); } BiTree RL(BiTree T)//旋转分两步1.以a为根结点的LL旋转 2.以x为根结点的RR旋转 { T-rchildLL(T-rchild); return RR(T); } BiTree Insert(BiTree T,int n) { if(!T) { Tnew BNode; T-lchildT-rchildNULL; T-datan; T-d1; } else if(nT-data) { T-lchildInsert(T-lchild,n); if(deep(T-lchild)-deep(T-rchild)1) { if(nT-lchild-data) TLL(T); else TLR(T); } } else if(nT-data) { T-rchildInsert(T-rchild,n); if(deep(T-rchild)-deep(T-lchild)1) { if(nT-rchild-data) TRR(T); else TRL(T); } } T-dmax(deep(T-lchild),deep(T-rchild))1; return T; } int main() { int n,num; scanf(%d,n); BiTree T; TNULL;//树的初始化。 for(int i0;in;i) { scanf(%d,num); Insert(T,num); } printf(%d\n,T-data); return 0; }*/ #includestdio.h #includestdlib.h #includestring.h #includealgorithm//max函数在此头文件中 using namespace std; typedef struct BNode { int data; int d; BNode *lchild,*rchild; }*BiTree; int n; int deep(BiTree T) { if(!T) return -1; return T-d; } BiTree LL(BiTree T) { BiTree p; pT-lchild; T-lchildp-rchild; p-rchildT; p-dmax(deep(p-lchild),deep(p-rchild))1; T-dmax(deep(T-lchild),deep(T-rchild))1; return p; } BiTree RR(BiTree T) { BiTree p; pT-rchild; T-rchildp-lchild; p-lchildT; p-dmax(deep(p-rchild),deep(p-lchild))1; T-dmax(deep(T-rchild),deep(T-lchild))1; return p; } BiTree LR(BiTree T) { T-lchildRR(T-lchild); return LL(T); } BiTree RL(BiTree T) { T-rchildLL(T-rchild); return RR(T); } BiTree Insert(BiTree T,int x) { if(!T) { Tnew BNode; T-lchildT-rchildNULL; T-datax; T-d0; } else if(xT-data) { Insert(T-lchild,x); if(deep(T-lchild)-deep(T-rchild)1) { if(xT-lchild-data) TLL(T); else TLR(T); } } else if(xT-data) { Insert(T-rchild,x); if(deep(T-rchild)-deep(T-lchild)1) { if(xT-rchild-data) TRR(T); else TRL(T); } } T-dmax(deep(T-rchild),deep(T-lchild))1; return T; } int main() { scanf(%d,n); int num; BiTree T; TNULL; for(int i1;in;i) { scanf(%d,num); TInsert(T,num); } printf(%d\n,T-data); }
