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