C++求大佬,C\C++交流,技术交流,鱼C论坛

发哥发表于 2020-12-3 13:25:58

C++求大佬

【问题描述】
利用平衡二叉树实现一个动态查找表。
【基本要求】
实现动态查找表的三种基本功能:查找、插入和删除。
【测试数据】
由读者自行设定。
【实现提示】
(1)初始，平衡二叉树为空树，操作界面给出查找、插入和删除三种操作供选择。每种操作均要提示输入关键字。每次插入或删除一个结点后，应更新平衡二叉树的显示。
(2)平衡二叉树的显示可采用凹入表形式，也可以采用图形界面画出树形。
(3)教科书已给出查找和插入算法，本题重点在于对删除算法的设计和实现。
假设要删除关键字为x的结点。
如果x不在叶子结点上，则用它左子树中的最大值或右子树中的最小值取代x。
如此反复取代，直到删除动作传递到某个叶子结点。
删除叶子结点时，若需要进行平衡变换，可采用插入的平衡变换的反变换(如，左子树变矮对应于右子树长高)。
【选作内容】
(1)合并两棵平衡二叉树。
(2)把一棵平衡二叉树分裂为两棵平衡二叉树，使得在一棵树中的所有关键字都小于或等于根节点，另一棵树中的任一关键字都大于根节点关键字

昨非发表于 2020-12-3 13:25:59

仅供参考

/*
Author：昨非
Date:2020.5.21
*/

#include <iostream>
#include <algorithm>
using namespace std;

//结点结构体
template<class T>
class BiNode
{
public:
   T data;
   BiNode <T>* lch;
   BiNode <T>* rch;
   int height;       //节点高度，判断平衡关键
   BiNode<T>(const T _data) : data(_data), lch(NULL), rch(NULL), height(0) {}//初始化
};
//平衡二叉树类
template<class T>
class AVLTree
{
public:
   BiNode<T>* root;

   AVLTree<T>() { root = NULL; }                   //默认构造
   void CreateAVL(T a[], int n);                   //建树
   void InsertAVL(BiNode<T>*& R, T key);          //插入
   BiNode<T>* SearchAVL(BiNode<T>* R, T key);    //按值查找
   BiNode<T>* DeleteAVL(BiNode<T>*& R, T key);    //按值删除
   void Inorder(BiNode<T>* R);                   //中序遍历检验
   void printAVLTree(BiNode<T>* root, int height, ostream& out);//直观打印
   ~AVLTree<T>()                                  //递归析构
   {
            Release(root);
            cout << "平衡二叉树已销毁！(析构)" << endl;
   }

private:
   int GetHeight(BiNode<T>* t);             //求结点的高度
   BiNode<T>* LL(BiNode<T>* t);          //单旋转左
   BiNode<T>* RR(BiNode<T>* t);                //单旋转右
   BiNode<T>* LR(BiNode<T>* t);                //双旋转右左
   BiNode<T>* RL(BiNode<T>* t);          //双旋转左右
   void Release(BiNode<T>* R);                //析构辅助函数
   BiNode<T>* MinNode(BiNode<T>* t) const;    //获取树中的最小值辅助判断
   BiNode<T>* MaxNode(BiNode<T>* t) const;    //获取树中的最大值辅助判断
};
//获取树中的最小值辅助判断
template<class T>
BiNode<T>* AVLTree<T>::MinNode(BiNode<T>* t) const
{
   if (NULL == t)
   {
            return NULL;
   }
   while (NULL != t->lch)
   {
            t = t->lch;
   }
   return t;
}

//获取树中的最大值辅助判断
template<class T>
BiNode<T>* AVLTree<T>::MaxNode(BiNode<T>* t) const
{
   if (NULL == t)
   {
            return NULL;
   }
   while (NULL != t->rch)
   {
            t = t->rch;
   }
   return t;
}

//获得结点高度辅助判断
template <class T>
int AVLTree<T>::GetHeight(BiNode<T>* t)
{
   if (t == NULL)
            return -1;
   else
            return t->height;
}

//建树：循环调用InsertAVL
template<class T>
void AVLTree<T>::CreateAVL(T a[], int n)
{
   for (int i = 0; i < n; i++)
   {
            InsertAVL(root, a);
   }
   cout << "平衡二叉树构造完成！" << endl;
}

//插入函数
template<class T>
void AVLTree<T>::InsertAVL(BiNode<T>*& R, T key)
{
   if (R == NULL) //结点为空
   {
            R = new BiNode<T>(key);
   }//判断当前结点应该插入根节点的左子树还是右子树
   else if (key < R->data)
   {
            InsertAVL(R->lch, key);
                           //判断平衡情况
            if ((GetHeight(R->lch) - GetHeight(R->rch)) > 1)//插入后失衡
            {
                     if (key < R->lch->data)
                     {
                           R = RR(R);//左左的旋转
                     }
                     else
                           R = LR(R);//左右的旋转
            }
   }
   else if (key > R->data)
   {
            InsertAVL(R->rch, key);
            if ((GetHeight(R->rch) - GetHeight(R->lch)) > 1)// 右插后失衡
            {
                     if (key < R->rch->data)
                     {
                           R = RL(R);//右左
                     }
                     else
                           R = LL(R); //右右
            }
   }
   R->height = max(GetHeight(R->lch), GetHeight(R->rch)) + 1;
}

//按值查找
template<class T>
BiNode<T>* AVLTree<T>::SearchAVL(BiNode<T>* R, T key)
{
   while (R != NULL)
   {
            if (key == R->data)
                     return R;
            else if (key < R->data)
                     R = R->lch;
            else
                     R = R->rch;
   }
   return NULL;
}

//删除给定值
template<class T>
BiNode<T>* AVLTree<T>::DeleteAVL(BiNode<T>*& R, T key)
{
   if (NULL == R) //空
   {
            return NULL;
   }
   if (key < R->data)
   {
            R->lch = DeleteAVL(R->lch, key);
            //相当于在右子树上插入节点
            if (GetHeight(R->rch) - GetHeight(R->lch) == 2)
            {
                     //相当于在右子树上插入左节点造成的失衡（情况四）
                     if (GetHeight(R->rch->lch) > GetHeight(R->rch->rch))
                     {
                           R = RL(R);//相当与插入的右左
                     }
                     else
                     {
                           R = RR(R);//相当于插入的右右
                     }
            }
   }
   else if (key > R->data)
   {
            R->rch = DeleteAVL(R->rch, key);
            if (GetHeight(R->lch) - GetHeight(R->rch) == 2)
            {
                     //判断插入位置
                     if (GetHeight(R->lch->lch) > GetHeight(R->lch->rch))
                           R = LL(R);//左左
                     else
                           R = LR(R);
            }
   }
   else
   {
            //1 当前节点是不是叶节点
            //2 删除之后还要看看是否破坏了平衡性
            if (NULL != R->lch && NULL != R->rch)
            {
                     if (GetHeight(R->lch) > GetHeight(R->rch))//左边子树高度大
                     {
                           BiNode<T>* _MaxNode = MaxNode(R->lch);//获取左结点最大值
                           R->data = _MaxNode->data;
                           R->lch = DeleteAVL(R->lch, _MaxNode->data);
                     }
                     else
                     {
                           BiNode<T>* _MinNode = MinNode(R->rch);
                           R->data = _MinNode->data;
                           R->rch = DeleteAVL(R->rch, _MinNode->data);
                     }
            }
            else //只有一个为NULL
            {
                     BiNode<T>* NowNode = R;
                     if (NULL != R->lch)
                     {
                           R = R->lch;
                     }
                     else if (NULL != R->rch)
                     {
                           R = R->rch;
                     }
                     else
                     {
                           R = NULL;// 当前节点是叶节点没有子节点
                     }
                     delete NowNode;
            }
   }
   return R;//返回该结点
}

//左左插入导致的不平衡->顺时针
template <typename T>
BiNode<T>* AVLTree<T>::LL(BiNode<T>* t)
{
   BiNode<T>* q = t->rch;
   t->rch = q->lch;
   q->lch = t;
   t->height = max(GetHeight(t->lch), GetHeight(t->rch)) + 1;
   q->height = max(GetHeight(q->lch), GetHeight(q->rch)) + 1;
   return q;
}

//右右插入导致的不平衡->逆时针
template <typename T>
BiNode<T>* AVLTree<T>::RR(BiNode<T>* t)
{
   BiNode<T>* q = t->lch;
   t->lch = q->rch;
   q->rch = t;
   t->height = max(GetHeight(t->lch), GetHeight(t->rch)) + 1;
   q->height = max(GetHeight(q->lch), GetHeight(q->rch)) + 1;
   return q;
}

//插入点位于t的左儿子的右子树 ->先逆再顺
template <typename T>
BiNode<T>* AVLTree<T>::LR(BiNode<T>* t)
{
   t->lch = LL(t->lch);
   return RR(t);
}

//插入点位于t的右儿子的左子树 ->先顺再逆
template <typename T>
BiNode<T>* AVLTree<T>::RL(BiNode<T>* t)
{
   t->rch = RR(t->rch);
   return LL(t);
}

//中序遍历用以验证
template<class T>
void AVLTree<T>::Inorder(BiNode<T>* R)
{
   if (R != NULL)
   {
            Inorder(R->lch);
            cout << R->data << "";
            Inorder(R->rch);
   }
}

//递归调用用以析构
template<class T>
void AVLTree<T>::Release(BiNode<T>* R)
{
   if (R != NULL)
   {
            Release(R->lch);
            Release(R->rch);
            delete R;
   }
}

//递归实现直观打印
template<class T>
void AVLTree<T>::printAVLTree(BiNode<T>* root, int height, ostream& out)
{
   char branches[] = { " /\\<" }; //树枝
   if (root != NULL)
   { //打印当前结点右子树，深度+1
            printAVLTree(root->rch, height + 1, out);//递归
            for (int i = 0; i < height; i++) out << "\t";//根据深度，右移
            out << "(" << root->data << ")";
            //打印树枝
            out << branches[((root->lch != NULL) << 1) | (root->rch != NULL)];
            out << endl;//换行，打印当前结点的左子树
            printAVLTree(root->lch, height + 1, out);//递归
   }
}

int main()          //测试
{
   int a[] = { 63, 90, 70, 55, 67, 42, 98 };//测试数据
   AVLTree<int>avltree;             //默认构造

   avltree.CreateAVL(a, 7);       //依据数组建树
   cout << "当前测试数据，整型 { 63, 90, 70, 55, 67, 42, 98 }; " << endl;
   cout << "查找测试数据：67" << endl << "插入测试数据：101" << endl << "测试删除数据：70" << endl;
   cout << "**********************************************************" << endl;
   cout << "原平衡二叉树中序遍历如下：";
   avltree.Inorder(avltree.root);
   cout << endl;
   cout << "打印如下：" << endl;
   avltree.printAVLTree(avltree.root, 0, cout);
   cout << endl << endl;

   cout << "***************************************************\n";
   cout << " * │1.打印AVL树    2.插入给定值    │ *\n";
   cout << " * │                                  │ *\n";
   cout << " * │3.删除给定值    4.中序遍历检验 │ *\n";
   cout << " * │                                  │ *\n";
   cout << " * │5.查找给定值    6.退出程序    │ *\n";
   cout << "***************************************************\n";
   cout << endl;
   BiNode<int>* p = avltree.SearchAVL(avltree.root, 67); //初始化查找指针，避免被case标签跳过
   int select;
   do
   {
            cout << "请选择操作方式 (1~6):" << endl;
            cin >> select;
            if (select > 6)
                     cout << "错误操作，请重新输入！"<<endl;
            else

            switch (select) {

            case 1:
                     avltree.printAVLTree(avltree.root, 0, cout);
                     cout << endl << endl;
                     break;

            case 2:
                     avltree.InsertAVL(avltree.root, 101);
                     cout << "插入成功!" << endl;
                     break;

            case 3:
                     avltree.DeleteAVL(avltree.root, 70);
                     cout << "删除成功！" << endl;
                     break;

            case 4:
                     cout << "中序遍历结果：";
                     avltree.Inorder(avltree.root);
                     cout << endl << endl;
                     break;

            case 5:
                     cout << "查找AVL: ";
                     if (p != NULL)
                           cout << p->data << endl;
                     else
                           cout << "给定值未找到" << endl;
                     break;

            case 6:
                     cout << "感谢使用！" << endl;
                     cout << "***********************************************************" << endl;
            }
   } while (select != 6);
   return 0;
}

发哥发表于 2020-12-3 19:21:53

昨非发表于 2020-12-3 18:47
仅供参考

大佬能不能帮着把选做题也做一下{:5_105:}

昨非发表于 2020-12-3 19:24:01

发哥发表于 2020-12-3 19:21
大佬能不能帮着把选做题也做一下

你再想桃子？

自己的事情还是需要自己做的
有参考就不错了

别人给你写永远都是别人的

发哥发表于 2020-12-3 19:31:34

昨非发表于 2020-12-3 19:24
你再想桃子？

自己的事情还是需要自己做的

好吧

听大佬的话

昨非发表于 2020-12-3 19:34:52

发哥发表于 2020-12-3 19:31
好吧

听大佬的话

所以帖子可以结了吗{:10_256:}

发哥发表于 2020-12-3 19:47:04

昨非发表于 2020-12-3 19:34
所以帖子可以结了吗

刚在研究那个代码
给忘了

马上马上

昨非发表于 2020-12-3 19:49:42

发哥发表于 2020-12-3 19:47
刚在研究那个代码
给忘了

私货
平衡二叉树C++实现（萌新分享）
https://fishc.com.cn/thread-174208-1-1.html
(出处: 鱼C论坛)

页: [1]

鱼C论坛's Archiver

C++求大佬