C++笔记:从零开始一步步手撕高阶数据结构AVL树

文章目录

  • 高度平衡二叉搜索树
  • 实现一颗AVL树
    • 结点与树的描述——定义类
    • AVL树的插入操作
      • 步骤1:按照二叉搜索树的方法插入结点
      • 步骤2:自底向上调整平衡因子
      • 步骤3:触发旋转操作(AVL树平衡的精髓)
        • 右单旋
        • 左单旋
        • 左右双旋
        • 右左双旋
    • 验证AVL树是否平衡
  • 参考文章

高度平衡二叉搜索树

二叉搜索树是一种特殊的树形数据结构,一般情况下,该树能够缩短查找的效率,但是它有个缺陷,在结点的插入或删除顺序较为特殊时结构会退化成链表,导致搜索、插入和删除等操作的时间复杂度从O(log n)退化到O(n)。

【二叉搜索树退化成链表的例子】
在这里插入图片描述

高度平衡二叉搜索树是针对二叉搜索树的缺陷所发明出来的一种改良结构。

高度平衡二叉搜索树常被称为 “ AVL树 ”,这主要是为了纪念发明它两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis,AVL是两位数学家的名字的缩写。

一颗AVL树或者是空树,或者是具有以下性质的二叉搜索树:

  • 左右子树高度之差(简称为平衡因子)的绝对值不超过1。
  • 在这里平衡因子的求法定义为:右子树的高度 - 左子树的高度。
  • 结点的左右两棵子树也都是一棵平衡二叉树。

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

实现一颗AVL树

概念部分讲的差不多了,至于AVL树相较于二叉搜索树是如何保持平衡结构,就在接下来的实现过程中一步步讲解。

结点与树的描述——定义类

namespace ljh
{template<class K, class V>struct AVLTreeNode{AVLTreeNode(const pair<K, V> kv) : _kv(kv) {}AVLTreeNode<K, V>* _parent = nullptr;	// A pointer to node's fatherAVLTreeNode<K, V>* _left = nullptr;		// A pointer to node's left childAVLTreeNode<K, V>* _right = nullptr;	// A pointer to node's right childint _bf = 0;		// balance factorpair<K, V> _kv;		// key-value};template<class K, class V>class AVLTree{typedef AVLTreeNode<K, V> Node;public:// AVL树的操作方法protected:Node* _root = nullptr;};
}

【说明】

  1. 模板化设计:
    • 使用template<class K, class V>来定义AVLTreeNodeAVLTree,使得该数据结构能够处理任意类型的键(Key)和值(Value),提高了代码的复用性和灵活性。
    • K代表键的类型,V代表值的类型。使用者可以根据自己的需求,在AVL树存储任何类型的键值对。
  2. AVLTreeNode类:
    • AVLTreeNode结构体定义了AVL树中每个节点的结构,用struct定义是为了方便在树类访问。
    • _parent指针:指向父节点,用于在旋转等操作中快速定位父节点(记住这里的旋转,这将是后面的重点)。
    • _left_right指针:分别指向左孩子和右孩子,是二叉树结构的基础。
    • _bf(平衡因子):存储节点的平衡因子,用于衡量树是否平衡。
    • _kv:存储于结点中的键值对,其中K是键的类型,V是值的类型。
  3. 构造函数:
    • AVLTreeNode的构造函数接收一个pair<K, V>对象,并初始化_kv成员变量。这样,当创建新节点时,可以方便地传入键值对。
  4. AVLTree类:
    • AVLTree类代表整个AVL树结构。
    • typedef AVLTreeNode<K, V> Node;,在内部使用定义了一个类型别名Node,目的是简化代码书写。
    • _root指针:指向AVL树的根节点,是整棵树的入口点。
  5. 保护成员:
    • _root成员变量被设计为protected,意味着它只能在AVLTree类及其派生类中被访问。这种设计是为了将AVL树的内部实现细节隐藏起来,而只暴露必要的公共接口给外部使用。
  6. 命名空间:
    • 为了方便使用库函数,使用using namespace std;展开标准库,但这容易引发同名类或函数发生冲突,因而将所有定义放在ljh命名空间中。

AVL树的插入操作

AVL树的插入操作实现起来大致分成以下三个大步骤

步骤1:按照二叉搜索树的方法插入结点

  1. 树为空,则构造新结点,让_root 指针指向该结点,返回true
  2. 树不空,按key的大小寻找插入位置,如果已存在,按插入失败处理,返回false
  3. 走到空表示找到合适位置,然后插入构造的新结点,插入时要判断左边插入或者右边插入。

此时插入并未结束,接下来进行步骤二的平衡因子更新操作!

【步骤1的代码如下:】

bool insert(pair<K, V> kv)
{// empty tree -> 直接插入if(_root == nullptr){_root = new Node(kv);return true;}// not empty tree -> 找到合适的位置再插入else{Node* child = _root;Node* parent = nullptr;while (child){// 大,往右走if (child->_kv.first < kv.first){parent = child;child = child->_right;}// 小,往左走else if (child->_kv.first > kv.first){parent = child;child = child->_left;}// 相同,插入失败else{return false;}}// child == nullptr, 找到合适的位置child = new Node(kv);if (child->_kv.first > parent->_kv.first)	parent->_right = child;else	parent->_left = child;child->_parent = parent;// 自底向上更新平衡因子// ...}
}

步骤2:自底向上调整平衡因子

我们将新插入结点称为child,新插入结点的双亲结点称为parent

平衡因子的更新规则如下:

  • 如果childparent的左孩子,parent的平衡因子-1。
  • 如果childparent的右孩子,parent的平衡因子+1。

这是第一次更新,更新完之后要不要继续向上更新取决于以parent为根结点的这棵树的高度是否变化,情况有以下3种:

  1. 平衡因子更新后,parent的平衡因子为0
    这意味着parent->_bf从-1 -> 0或者 从1 -> 0,以parent为根结点的这棵树的高度没有发生变化,不用再向上更新平衡因子,可以返回true,表示插入成功。

  2. 平衡因子更新后,parent的平衡因子为-1+1
    这意味着parent->_bf从0 -> -1或者 从0 -> 1,以parent为根结点的这棵树的高度发生了变化,但还没有达到需要旋转的程度。
    在这种情况下,更新child = child->_parent,更新parent = parent->_parent,继续更新parent 的平衡因子,直到情况1:找到平衡因子为0的节点;或者情况2:到达根节点(parent == nullptr)。

  3. 平衡因子更新后,parent的平衡因子为-2+2
    这意味着此时以parent为根结点的这棵树已经违反了AVL树的规则,需要进行旋转处理,处理完之后,可以直接返回true

【步骤2的代码如下:】

// 自底向上更新平衡因子
while (parent)
{if (child == parent->_left){--parent->_bf;}else{++parent->_bf;}if (parent->_bf == 0){return true;}else if (parent->_bf == 1 || parent->_bf == -1){child = child->_parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){// 违反规则,旋转处理// ...}else{// 理论上没错误不会走到这里assert(false);}
}

步骤3:触发旋转操作(AVL树平衡的精髓)

根据节点插入位置的不同,AVL树的旋转分为以下4种:

由于具象图的种类繁多,根本不可能画得完,下面AVL树旋转的图解中大多画的是抽象图。

右单旋

这里给出了一棵以结点90作为根节点的AVL树的抽象图,图中 a / b / c 代表三棵高度为 h 的子树。
这颗AVL树的左子树高度高于右子树高度

在这里插入图片描述


首先,以90为根结点的这棵树有三种可能:

  1. 它是某棵AVL树的左子树;
  2. 它是某棵AVL树的右子树;
  3. 它就是AVL树的根结点;

在这里插入图片描述


当新结点插入在了较高左子树的左侧,即 a 子树时,child 和 parent 自底向上更新平衡因子,当出现parent->_bf == -2, child->_bf == -1时,该树违反了AVL树的规则,需要进行右单旋操作。
在这里插入图片描述


在右单旋中,涉及到改变链接关系的结点主要有以下4个:
在这里插入图片描述


当 a / b / c 3棵子树高度为零时插入新结点,平衡因子为 -2 的结点向右旋转:
在这里插入图片描述

当 a / b / c 3棵子树高度不为零时插入新结点,平衡因子为 -2 的结点向右旋转:
在这里插入图片描述


【右单旋操作的代码如下】

void R_Rotate(Node* parent)
{Node* ppnode = parent->_parent;Node* subL = parent->_left;Node* subLR = subL->_right;// subL and parentsubL->_right = parent;parent->_parent = subL;// parent and subLRparent->_left = subLR;if (subLR)	subLR->_parent = parent;// ppnode and subLif (ppnode == nullptr){_root = subL;subL->_parent = nullptr;}else{subL->_parent = ppnode;if (parent == ppnode->_left){ppnode->_left = subL;}else{ppnode->_right = subL;}}parent->_bf = subL->_bf = 0;
}
左单旋

这里给出了一棵以结点30作为根节点的AVL树的抽象图,图中 a / b / c 代表三棵高度为 h 的子树。
这颗AVL树的右子树高度高于左子树高度

在这里插入图片描述


首先,以30为根结点的这棵树有三种可能:

  1. 它是某棵AVL树的左子树;
  2. 它是某棵AVL树的右子树;
  3. 它就是AVL树的根结点;

在这里插入图片描述


当新结点插入在了较高右子树的右侧,即 c 子树时,child 和 parent 自底向上更新平衡因子,当出现parent->_bf == 2, child->_bf == 1时,该树违反了AVL树的规则,需要进行左单旋操作。
在这里插入图片描述


在左单旋中,涉及到改变链接关系的结点同样有4个:
在这里插入图片描述


当 a / b / c 3棵子树高度为零时插入新结点,平衡因子为 2 的结点向左旋转:
在这里插入图片描述

当 a / b / c 3棵子树高度不为零时插入新结点,平衡因子为 2 的结点向左旋转:
在这里插入图片描述


【左单旋操作的代码如下】

void L_Rotate(Node* parent)
{Node* ppnode = parent->_parent;Node* subR = parent->_right;Node* subRL = subR->_left;// subR and parentsubR->_left = parent;parent->_parent = subR;// parent and subRLparent->_right = subRL;if (subRL)	subRL->_parent = parent;//ppnode and subRif (ppnode == nullptr){_root = subR;subR->_parent = nullptr;}else{subR->_parent = ppnode;if (parent == ppnode->_left){ppnode->_left = subR;}else{ppnode->_right = subR;}}parent->_bf = subR->_bf = 0;
}
左右双旋

这里给出了一棵以结点90作为根节点的AVL树的抽象图,图中 a / b / c / d 代表四棵子树。
这颗AVL树的左子树高度高于右子树高度

在这里插入图片描述


首先,以90为根结点的这棵树有三种可能:

  1. 它是某棵AVL树的左子树;
  2. 它是某棵AVL树的右子树;
  3. 它就是AVL树的根结点;

在这里插入图片描述


下面三种情况都有一个共同给特点,就是parent->_bf == -2, child->_bf == 1
我们不难发现,左右双旋可以视为先左旋再右旋,即结点30先左旋,结点90再右旋。
在这里插入图片描述


在这里插入图片描述


单旋中的subLR不管怎么操作,它的平衡因子都是 0,但是在双旋中,subLR有可能是 -1、0、1中任意一种,因此,虽然双旋操作我们可以复用单旋的代码,但是双旋之后的平衡因子调整需要单独处理。
在这里插入图片描述

【左右双旋的代码如下】

void LR_Rotate(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;// 双旋之后要靠bf来更新平衡因子int bf = subLR->_bf;L_Rotate(subL);R_Rotate(parent);if (bf == 0){subLR->_bf = 0;subL->_bf = 0;parent->_bf = 0;}else if (bf == -1){subLR->_bf = 0;subL->_bf = 0;parent->_bf = 1;}else{subLR->_bf = 0;subL->_bf = -1;parent->_bf = 0;}
}
右左双旋

这里给出了一棵以结点30作为根节点的AVL树的抽象图,图中 a / b / c / d 代表四棵子树。
这颗AVL树的右子树高度高于左子树高度

在这里插入图片描述


首先,以30为根结点的这棵树有三种可能:

  1. 它是某棵AVL树的左子树;
  2. 它是某棵AVL树的右子树;
  3. 它就是AVL树的根结点;

在这里插入图片描述


下面三种情况都有一个共同给特点,就是parent->_bf == 2, child->_bf == -1
我们不难发现,右左双旋可以视为先右旋再左旋,即结点90先右旋,结点30再左旋。
在这里插入图片描述


在这里插入图片描述


单旋中的subRL不管怎么操作,它的平衡因子都是 0,但是在双旋中,subRL有可能是 -1、0、1中任意一种,因此,虽然双旋操作我们可以复用单旋的代码,但是双旋之后的平衡因子调整需要单独处理。
在这里插入图片描述

【右左双旋的代码如下】

void RL_Rotate(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;// 双旋之后要靠bf来更新平衡因子int bf = subRL->_bf;R_Rotate(subR);L_Rotate(parent);if (bf == 0){subRL->_bf = 0;parent->_bf = 0;subR->_bf = 0;}else if (bf == -1){subRL->_bf = 0;parent->_bf = 0;subR->_bf = 1;}else{subRL->_bf = 0;parent->_bf = -1;subR->_bf = 0;}
}

验证AVL树是否平衡

虽然目前已经将AVL树的插入操作的代码已经写出来了,但是仅仅是写出来了一定能够保证代码就是正确的吗——肯定不是!

所以,接下来还要再实现一个方法,来验证一棵AVL树是不是平衡的。

AVL树是在二叉搜索树的基础上加入了平衡性的限制,因此要验证AVL树,可以分两步:

  1. 验证其为二叉搜索树
    如果中序遍历可得到一个有序的序列,就说明为二叉搜索树。
  2. 验证其为平衡树
    每个结点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)。
    结点的平衡因子是否计算正确。

【写法一代码:简单但是效率低】

// 求AVL树的高度
size_t _Height(Node* root)
{if (root == nullptr)return 0;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}size_t Height()
{return _Height(_root);
}bool _IsBalance(Node* root)
{// 空树也是AVL树if (root == nullptr) return true;// 计算root节点的平衡因子:即root左右子树的高度差int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);// 如果计算出的平衡因子与pRoot的平衡因子不相等,或者// root平衡因子的绝对值超过1,则一定不是AVL树int diff = rightHeight - leftHeight;if (abs(diff) >= 2){cout << root->_kv.first << "不平衡" << endl;return false;}if (diff != root->_bf){cout << root->_kv.first << "平衡因子异常" << endl;return false;}// root的左和右如果都是AVL树,则该树一定是AVL树return _IsBalance(root->_left) && _IsBalance(root ->_right);
}

【写法二代码:效率高但是相较写法一难理解】

// 判断AVL树是否平衡,高效
bool _IsBalance(Node* root, int& height)
{// 空树也是AVL树if (root == nullptr){height = 0;return true;}// 后序递归,leftHeight、rightHeight会分别获取root的左右子树的高度int leftHeight = 0, rightHeight = 0;if (!_IsBalance(root->_left, leftHeight) || !_IsBalance(root->_right, rightHeight)){return false;}// 如果高度差的绝对值 >= 2,AVL树不平衡int diff = rightHeight - leftHeight;if (abs(diff) >= 2){cout << root->_kv.first << "不平衡" << endl;return false;}// 如果高度差 != root->_bf,AVL树插入过程中的平衡因子更新有问题if (diff != root->_bf){cout << root->_kv.first << "平衡因子异常" << endl;return false;}// 将root自己的高度通过引用返回给上一层栈帧height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;// root的左子树平衡、右子树平衡、root自身也平衡,那这棵AVL树就平衡return true;
}

参考文章

数据结构 —— 图解AVL树(平衡二叉树)
高度平衡二叉搜索树(AVLTree)
【数据结构】AVL树的删除(解析有点东西哦)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/276917.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

基于openresty构建运维工具链实践

本文字数&#xff1a;4591字 预计阅读时间&#xff1a;25 01 导读 如今OpenResty已广泛被各个互联网公司在实际生产环境中应用&#xff0c;在保留Nginx高并发、高稳定等特性基础上&#xff0c;通过嵌入Lua来提升在负载均衡层的开发效率并保证其高性能。本文主要介绍接口鉴权、流…

Spring Cloud Alibab 入门搭建,包含Nacos中心,注册服务发现服务,Feign请求,GateWay网关,sentinel限流

源码在最后 一、安装Nacos注册中心 1.1查看Nacos官网&#xff0c;安装Nacos服务&#xff0c;下载源码或者安装包 1.2启动服务&#xff0c;默认端口为8848&#xff0c; 二、创建服务注册&发现 2.1使用脚手架&#xff0c;创建注册服务和发现服务项目&#xff0c;我用的版…

.NET开源快速、强大、免费的电子表格组件

今天大姚给大家分享一个.NET开源&#xff08;MIT License&#xff09;、快速、强大、免费的电子表格组件&#xff0c;支持数据格式、冻结、大纲、公式计算、图表、脚本执行等。兼容 Excel 2007 (.xlsx) 格式&#xff0c;支持WinForm、WPF和Android平台&#xff1a;ReoGrid。 项…

【机器学习300问】34、决策树对于数值型特征如果确定阈值?

还是用之前的猫狗二分类任务举例&#xff08;这个例子出现在【机器学习300问】第33问中&#xff09;&#xff0c;我们新增一个数值型特征&#xff08;体重&#xff09;&#xff0c;下表是数据集的详情。如果想了解更多决策树的知识可以看看我之前的两篇文章&#xff1a; 【机器…

Linux从0到1——Linux第一个小程序:进度条

Linux从0到1——Linux第一个小程序&#xff1a;进度条 1. 输出缓冲区2. 回车和换行的本质3. 实现进度条3.1 简单原理版本3.2 实际工程版本 1. 输出缓冲区 1. 小实验&#xff1a; 编写一个test.c文件&#xff0c;&#xff1a; #include <stdio.h> #include <unistd.h…

详解命令docker run -d --name container_name -e TZ=Asia/Shanghai your_image

docker run 是Docker的主要命令&#xff0c;用于从镜像启动一个新的容器。下面详细解释并举例说明 -d, --name, -e TZ 参数的用法&#xff1a; -d 或 --detach&#xff1a; 这个标志告诉Docker以守护进程&#xff08;后台&#xff09;模式运行容器。这意味着当你执行 docker ru…

学习笔记-华为IPD转型2020:1,IPD的重要意义

华为产品开发转型&#xff1a;IPD计划 大多数公司发现&#xff0c;当公司大幅增长时&#xff0c;在较小规模上有效的管理实践不再有效。产品开发过程也是如此。随着华为的发展&#xff0c;该公司遇到了产品故障率更高、开发周期更长和研发成本增加等问题。然后&#xff0c;它转…

Lord 3DMCV7-AHRS 时间同步硬件触发设置

目的:通过FPGA发送脉冲触发IMU采集数据。FPGA发送脉冲时,IMU才有数据产生。 FPGA与IMU的硬件接线就不讲了,这里主要说明的是IMU的设置以及ROS驱动的config文件更改。 1. WIN上位机设置 通过IMU在WINDOWS的上位机SensorConnect对IMU的GPIO、波特率等基本功能进行设值,具体…

Unity PS5开发 天坑篇 之 申请开发者与硬件部署01

腾了好几天终于把PS5开发机调试部署成功, 希望能帮到国内的开发者, 主机游戏PlayStation/Nintendo Switch都是比较闭塞的&#xff0c;开发者账号是必须的。 开发环境有两个部分&#xff0c;一是DEV Kit 开发机, TEST Kit测试机两部分组成&#xff0c;二是Unity的支持库(安装后…

vue使用elementPlus ui框架,如何给Dialog 对话框添加Loading 自定义类名显示隐藏

vue使用elementPlus ui框架时&#xff0c;如何给Dialog 对话框添加Loading 自定义类名&#xff0c;想要实现dialog对话框区域有loading效果 官方给出的这个API配置项customClass&#xff0c;使用不太明确。暂时无法实现绑定class。 最后的实现方式&#xff1a; <template&…

3、设计模式之工厂模式2(Factory)

一、什么是工厂模式 工厂模式属于创建型设计模式&#xff0c;它用于解耦对象的创建和使用。通常情况下&#xff0c;我们创建对象时需要使用new操作符&#xff0c;但是使用new操作符创建对象会使代码具有耦合性。工厂模式通过提供一个公共的接口&#xff0c;使得我们可以在不暴露…

【小白学机器学习8】统计里的自由度DF=degree of freedom, 以及关于df=n-k, df=n-k-1, df=n-1 等自由度公式

目录 1 自由度 /degree of freedom / df 1.1 物理学的自由度 1.2 数学里的自由度 1.2.1 数学里的自由度 1.2.2 用线性代数来理解自由度&#xff08;需要补充&#xff09; 1.2.3 统计里的自由度 1.3 统计学里自由度的定义 2 不同对象的自由度 2.1 纯公式的自由度&#…

idea:忽略不要搜索unpackage文件夹

开发vue时搜索关键字&#xff0c;会搜索到编译后的文件&#xff0c;如unpackage。&#xff08;注意这个是idea工具&#xff0c;和Git忽略是有区别的&#xff09; File->Settings->Editor->File Types

【C++ 设计模式】策略模式与简单工厂模式的结合

文章目录 前言一、为什么需要策略模式简单工厂模式二、策略模式简单工厂模式实现原理三、UML图四、示例代码总结 前言 在软件设计中&#xff0c;常常会遇到需要根据不同情况选择不同算法或行为的情况。策略模式和简单工厂模式是两种常见的设计模式&#xff0c;它们分别解决了对…

.Net Core 中间件验签

文章目录 为什么是用中间件而不是筛选器&#xff1f;代码实现技术要点context.Request.EnableBuffering()指针问题 小结 为什么是用中间件而不是筛选器&#xff1f; 为什么要用中间件验签&#xff0c;而不是筛选器去验签? 1、根据上图我们可以看到&#xff0c;中间件在筛选器之…

专业无网设备如何远程运维?向日葵远程控制能源场景案例解析

清洁能源领域&#xff0c;拥有庞大的上下游产业链&#xff0c;涉及的相关工业设备门类多、技术覆盖全、行业应用广。在这一领域内&#xff0c;相关专业设备的供应商的核心竞争力除了本身产品的技术能力之外&#xff0c;服务也是重要的一环。 某企业作为致力于节能环保方向的气…

spy分析文件另存为弹框【selenium】

有时需要下载多个文件&#xff0c;但是不想保存在同一个目录下&#xff0c;需要做两步 selenium设置浏览器默认下载路径&#xff0c;这个路径需要是个不存在的路径操作文件另存为弹框 文章目录 selenium设置浏览器默认下载路径操作文件另存为弹框 selenium设置浏览器默认下载路…

使用docker-compose管理freeswitch容器

概述 之前的文章我们介绍过如何将freeswitch做成docker镜像&#xff0c;也使用命令行模式正常启动了fs的docker容器。 但是当我们需要同时管理多个docker容器的时候&#xff0c;还是使用docker-compose更简单。 环境 CENTOS 7 docker engine&#xff1a;Version 25.0.3 D…

【快捷部署】002_Flink(1.17.2)

&#x1f4e3;【快捷部署系列】002期信息 编号选型版本操作系统部署形式部署模式002Flink1.17.2CentOS 7.Xtgz包单机 &#x1f449; 演示视频 Flink一键安装&#xff08;本地模式&#xff09; install-flink.sh 脚本内容 #!/bin/bash ####变量 ###执行脚本的当前目录 mydir$…

使用IDEA2023创建传统的JavaWeb项目并运行与调试

日期:2024-0312 作者:dusuanyun 文档环境说明: OS:Deepin 20.9(Linux) JDK: OpenJDK21 Tomcat:10.1.19 IDEA: 2023.3.4 (Ultimate Edition) 本文档默认已经安装JDK及环境变量的配置。 关键词…