第十六周做题总结_数据结构

id:157 A. DS二叉平衡树构建

题目描述

在初始为空的平衡二叉树中依次插入n个结点，请输出最终的平衡二叉树。

要求实现平衡二叉树，不可以使用各类库函数。
AVL代码参考模板：

#include <iostream>
using namespace std;#define LH 1 // 左高 
#define EH 0 // 等高 
#define RH -1 // 右高 class BiNode
{public:int key; // 关键值int bf; // 平衡因子 BiNode *lChild, *rChild;BiNode(int kValue, int bValue){key = kValue;bf = bValue;lChild = NULL;rChild = NULL;}~BiNode(){key = 0;bf = 0;lChild = NULL;rChild = NULL;}
};// 二叉排序树
class BST
{private:BiNode *root; // 根结点指针 void rRotate(BiNode *&p);void lRotate(BiNode *&p);void leftBalance(BiNode *&t);void rightBalance(BiNode *&t);int insertAVL(BiNode *&t, int key, bool &taller); // 插入元素并做平衡处理void inOrder(BiNode *p);public:BST();void insertAVL(int key); // 二叉排序树插入元素 ~BST();void inOrder(); // 中序遍历 
};// 以p为根的二叉排序树作右旋处理 
void BST::rRotate(BiNode *&p)
{// 参考课本236页算法9.9
}// 以p为根的二叉排序树作左旋处理 
void BST::lRotate(BiNode *&p)
{// 参考课本236页算法9.10
}// t为根的二叉排序树作左平衡旋转处理
void BST::leftBalance(BiNode *&t)
{// 参考课本238页算法9.12
}// t为根的二叉排序树作右平衡旋转处理
void BST::rightBalance(BiNode *&t)
{// 参考课本238页算法9.12
}int BST::insertAVL(BiNode *&t, int key, bool &taller)
{// 参考课本237页算法9.11
}void BST::inOrder(BiNode *p)
{if(p){inOrder(p->lChild);cout << p->key << ':' << p->bf << ' ';inOrder(p->rChild);}return;
}// 二叉排序树初始化
BST::BST()
{root = NULL;
}BST::~BST()
{root = NULL;
}// 插入元素并作平衡处理
void BST::insertAVL(int key)
{bool taller = false;insertAVL(root, key, taller);
}// 中序遍历
void BST::inOrder()
{inOrder(root);
}int main(void)
{int t;cin >> t;while(t --){// 构建二叉平衡树，并在插入元素时做平衡处理 int n, elem;cin >> n;BST tree;while(n --){cin >> elem;tree.insertAVL(elem);}tree.inOrder();cout << endl;}return 0;
}

输入

第一行输入测试数据组数t；
每组测试数据，第一行输入结点数n, 第二行输入n个结点值。

输出

对每组测试数据，按中序遍历的顺序输出树中，结点值及平衡因子（测试数据没有空树），即结点值：平衡因子，不同结点之间间隔一个空格。

输入样例1

8
3
64 5 1
3
64 5 13
6
64 78 5 1 13 15
6
64 78 5 1 13 10
3
64 78 100
3
64 80 70
6
64 30 80 90 70 68
6
64 30 80 90 70 75

输出样例1

1:0 5:0 64:0
5:0 13:0 64:0
1:0 5:1 13:0 15:0 64:0 78:0
1:0 5:0 10:0 13:0 64:-1 78:0
64:0 78:0 100:0
64:0 70:0 80:0
30:0 64:0 68:0 70:0 80:-1 90:0
30:0 64:1 70:0 75:0 80:0 90:0

代码实现

#include <iostream>
using namespace std;#define LH 1 // 左高
#define EH 0 // 等高
#define RH -1 // 右高class BiNode
{
public:int key; // 关键值int bf; // 平衡因子 BiNode* lChild, * rChild;BiNode(int kValue, int bValue);~BiNode();
};BiNode::BiNode(int kValue, int bValue)
{key = kValue;bf = bValue;lChild = NULL;rChild = NULL;
}BiNode::~BiNode()
{key = 0;bf = 0;lChild = NULL;rChild = NULL;
}// 二叉排序树
class BST
{
private:int n; // 结点个数BiNode* root; // 根结点指针 void rRotate(BiNode*& p);void lRotate(BiNode*& p);void leftBalance(BiNode*& t);void rightBalance(BiNode*& t);int insertAVL(BiNode*& t, int key, bool& taller); // 插入元素并做平衡处理void inOrder(BiNode* p, int& n);
public:BST(int n1);void insertAVL(int key); // 二叉排序树插入元素 ~BST();void inOrder(); // 中序遍历 
};// 以p为根的二叉排序树作右旋处理(LL
void BST::rRotate(BiNode*& p)
{BiNode* k = p->lChild;p->lChild = k->rChild;k->rChild = p;p = k;
}// 以p为根的二叉排序树作左旋处理(RR
void BST::lRotate(BiNode*& p)
{BiNode* k = p->rChild;p->rChild = k->lChild;k->lChild = p;p = k;
}// t为根的二叉排序树作左平衡旋转处理
void BST::leftBalance(BiNode*& t)
{BiNode* lc;lc