当前位置：首页 > article >正文

第十六周做题总结_数据结构_AVL与哈希查找

article 2024/12/23 23:26:30

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