devbox
我家小花儿
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

AVL（二叉平衡搜索树）详解_avl树添加节点何时查询平衡性

作者：我家小花儿 | 2024-04-30 05:02:26

赞

踩

avl树添加节点何时查询平衡性

目录

1.什么是二叉平衡搜索树？

2.AVL树的结点结构

3.AVL模板类

3.1. 插入操作

（1）插入情况

（2）旋转操作

1.左旋操作

2.右旋操作

3.双旋操作

3.2 检查平衡性

1.什么是二叉平衡搜索树？

首先，我们要了解什么是二叉搜索树，这里大家可以看我写的上一篇博客    二叉搜索树

并且本文也在二叉搜索树的基础上进行讲解。

我们可以知道，AVL树是二叉搜索树的一种，它与二叉搜索树的不同之处就在于平衡二字，这也是为了弥补二叉搜索树的缺陷而做出的改变。

我们知道，二叉搜索树在极端条件下会出现下面的情况：

 在这种情况下，二叉搜索树退化为链表，无论是查找，插入，删除等一系列操作，二叉搜索树都与链表没有任何区别，那我们建立二叉搜索树的优势就不复存在了。

为了弥补这个缺点，有了二叉平衡搜索树，二叉平衡搜索树有如下性质：

1.满足二叉搜索树的性质

2.任何一个节点的左右树高度差不超过一

3.左右子树都满足AVL树的性质

这就保证了二叉搜索树的性质同时不会出现极端情况退化为链表，满足这种条件的树我们称之为二叉平衡搜索树。

2.AVL树的结点结构

首先，我们知道AVL树是二叉搜索树的一种，唯一多了平衡的特性，因此结点结构也是与二叉搜索树类似的，只是多了一个 int 类型的数据 ，平衡因子 _bf  ，平衡因子的值是此结点的右子树高度减去左子树高度后得到的值，具体结构如下：

  1. template<class T>
  2. struct AVLTreeNode
  3. {
  4. 	AVLTreeNode(const T& data = T())
  5. 		: _pLeft(nullptr)
  6. 		, _pRight(nullptr)
  7. 		, _pParent(nullptr)
  8. 		, _data(data)
  9. 		, _bf(0)
  10. 	{}
  11.  
  12. 	AVLTreeNode<T>* _pLeft;
  13. 	AVLTreeNode<T>* _pRight;
  14. 	AVLTreeNode<T>* _pParent;
  15. 	T _data;
  16. 	int _bf;   // 节点的平衡因子
  17. };

使用template类模板我们可以使用多种数据类型的AVL结点类型，如果想要存储key-value结构的数据，我们可以将data的数据类型更改为pair ，这里为了方便大家理解，我采用key的结构，同时我们写了一个构造函数来进行结点的构造。

3.AVL模板类

完成了AVL树的结点结构，我们要进行AVL树的模板类的编写，首先，我们可以搭建框架：

  1. template<class T>
  2. class AVLTree
  3. {
  4. 	typedef AVLTreeNode<T> Node;
  5. public:
  6. 	AVLTree()
  7. 		: _pRoot(nullptr)
  8. 	{}
  9.  
  10. private:
  11. 	Node* _pRoot;
  12. };

这里我们知道AVL树的类模板中只有一个成员变量 _pRoot，用来存储AVL树的的根结点，并且我们简单写一个构造函数，有兴趣的朋友也可以去实现一下拷贝构造，析构......默认成员函数。

接下来我们编写AVL类中主要的成员方法：

3.1. 插入操作

与二叉搜索树不同的是，AVL的树操作更加复杂，首先，我们要找到结点的插入位置，这步操作我们可以与二叉搜索树的插入操作进行复用，其次，我们插入结点后，要让树满足 “平衡” ，这里我们就有可能要对树的结构进行一些改变，我们称之为 旋转操作。

（1）插入情况

首先，我们要知道，在插入之前树是一棵AVL树，总的来说，这棵树只有三种情况：

1.左右均衡

这种情况下，AVL树几完全平衡的，此时无论我们在哪边插入都不会影响AVL的平衡性质

2.左高右低

在AVL树中，左右高度差不超过1，因此即便左高右低，高度也只差了1，情况如下：

这种情况下，我们如果插入结点到右子树，会使AVL树更加平衡，但是如果插入节点到左子树上，就会影响AVL的平衡，并且插入到左子树也有两种可能：

1.插入到左结点的 左子树上

2.插入到左结点的右子树上

这两种操作需要的操作也是不相同的，我们后面再说。

3.左低右高

这种情况下，我们如果插入结点到左子树，会使AVL树更加平衡，但是如果插入节点到右子树上，就会影响AVL的平衡，并且插入到右子树也有两种可能：

1.插入到右结点的左子树上

2.插入到右结点的右子树上

并且我们要知道插入结点后的一些性质：

1.插入结点后，只对其祖先结点产生影响。

2.若某祖先结点的平衡因子变为0，影响不再向上传递。

3.若某祖先的平衡因子为+1/-1，影响继续向上传递。 

（2）旋转操作
1.左旋操作

 当右子树偏高且结点插入到右节点的右子树上时候，我们要采用左旋操作，详细过程如下：

首先，我们要注意，只有当AVL树本来就右边偏高并且插入结点在AVL树的右边子树上才能够使用左旋，把这个条件变化成数据体现，其实也就是当我们找到平衡因子异常的结点parent，如果它的平衡因子为2，且cur平衡因子为1。类似这样的结构，parent，cur和插入结点在一条直线上，如下：

满足了这个条件，我们就可以以cur为轴心进行左旋，并且我们可以注意到，左旋后的parent和cur平衡因子都变为0，则影响不再向上传递。

也就是说，满足左旋场景我们只需要左旋一次就能够完成调整，得到的树就满足AVL树的条件。

代码如下：

  1. // 左单旋
  2. 	void RotateL(Node* pParent)
  3. 	{
  4. 		Node* cur = pParent->_pRight;
  5. 		Node* curleft = cur->_pLeft;
  6.  
  7. 		//左旋第一步，cur的左树变为parent的右子树
  8. 		pParent->_pRight = curleft;
  9. 		if (curleft)
  10. 		{
  11. 			curleft->_pParent = pParent;
  12. 		}
  13.  
  14. 		//左旋第二步，parent变为cur的左子树
  15. 		cur->_pLeft = pParent;
  16.  
  17. 		//记录根节点的上一个节点
  18. 		Node* ppnode = pParent->_pParent;
  19.  
  20. 		pParent->_pParent = cur;
  21.  
  22. 		if (pParent == _pRoot)//如果parent已经是根节点了
  23. 		{
  24. 			_pRoot = cur;
  25. 			cur->_pParent = nullptr;
  26. 		}
  27. 		else    //如果parent不是根节点，需要把cur与前面节点进行连接
  28. 		{
  29. 			if (ppnode->_pLeft == pParent)//如果原来的parent是上一节点的左孩子
  30. 			{
  31. 				ppnode->_pLeft = cur;
  32. 				cur->_pParent = ppnode;  
  33. 			}
  34. 			else                         //如果原来的parent是上一节点的右孩子
  35. 			{
  36. 				ppnode->_pRight = cur;
  37. 				cur->_pParent = ppnode;
  38. 			}
  39. 		}
  40.  
  41. 		//完成平衡因子的修改
  42. 		cur->_bf = pParent->_bf = 0;
  43.  
  44.  
  45. 	}

2.右旋操作

当左子树偏高且结点插入到左节点的左子树上时候，我们要采用右边旋操作，详细过程如下：

要进行右旋 ，需要满足的条件为：

插入之前，左子树偏高，插入结点在左结点的左子树上，和左旋一样，parent，cur和插入结点在一条直线上，不过类似与下面的结构：

描述为数据表现就是，当我们找到平衡因子异常的结点parent：若parent的bf为2，cur的bf为1，我们就以cur为轴心进行右旋。

并且我们可以注意到，进行旋转后，parent和cur的平衡因子变为0，影响不再向上传递，

也就是说，满足右旋场景我们只需要右旋一次就能够完成调整，得到的树就满足AVL树的条件。

代码如下：

  1. // 右单旋
  2. 	void RotateR(Node* pParent)
  3. 	{
  4. 		Node* cur = pParent->_pLeft;
  5. 		Node* curright = cur->_pRight;
  6.  
  7. 		//右旋第一步，cur的右子树给parent的左子树
  8. 		pParent->_pLeft = curright;
  9. 		if (curright)
  10. 		{
  11. 			curright->_pParent = pParent;
  12. 		}
  13.  
  14. 		//右旋第二步，parent变为cur的右子树
  15. 		cur->_pRight = pParent;
  16. 		Node* ppnode = pParent->_pParent;
  17. 		pParent->_pParent = cur;
  18.  
  19. 		if (pParent == _pRoot)
  20. 		{
  21. 			_pRoot = cur;
  22. 			cur->_pParent = nullptr;
  23. 		}
  24. 		else
  25. 		{
  26. 			if (ppnode->_pLeft == pParent)
  27. 			{
  28. 				ppnode->_pLeft = cur;
  29. 				cur->_pParent = ppnode;
  30. 			}
  31. 			else
  32. 			{
  33. 				ppnode->_pRight = cur;
  34. 				cur->_pParent = ppnode;
  35. 			}
  36. 		}
  37. 		cur->_bf = pParent->_bf = 0;
  38.  
  39. 	}

3.双旋操作

1.右左双旋

在讲解插入情况时，我们知道右高左低有两种情况

其中，我们如果插入到右结点的右子树，就满足了左旋的条件，直接进行左旋就可以完成。

但是我们如果插入到右结点的左子树，这个时候 ，parent ，cur和插入结点并不在一条直线上，而是一条折线结构，数据表现为，当我们找到平衡因子异常的结点parent，其平衡因子为2,cur的平衡因子为-1，其右如下：

详细操作如下：

 首先，我们找到平衡因子异常的结点为parent，先对其right结点进行右旋，然后再对parent结点进行左旋，具体操作如下：

  1.     // 右左双旋
  2. 	void RotateRL(Node* pParent)
  3. 	{
  4. 		RotateR(pParent->_pRight);
  5. 		RotateL(pParent);
  6. 	}

2.左右双旋

与右左双旋相对的是，左右双旋是左高右低中的一种情况

当我们把新结点插入到左结点的左子树时，满足右旋操作的条件，进行右旋操作即可。

但是如果我们插入到 左结点的右子树时，形成另外一种折线结构，数据表现为，当我们找到平衡因子异常的结点parent，其平衡因子为-2,cur的平衡因子为1，如下：

此时，我们需要进行左右双旋,具体操作如下：

代码如下：

  1. // 左右双旋
  2. 	void RotateLR(Node* pParent)
  3. 	{
  4. 		RotateL(pParent->_pLeft);
  5. 		RotateR(pParent);
  6. 	}

插入操作全过程：

  1. // 在AVL树中插入值为data的节点
  2. 	bool Insert(const T& data)
  3. 	{
  4. 		//树为空
  5. 		if (!_pRoot)
  6. 		{
  7. 			Node* newnode = new Node(data);
  8. 			_pRoot = newnode;
  9. 			return true;
  10. 		}
  11.  
  12. 		Node* parent =nullptr;
  13. 		Node* cur = _pRoot;
  14. 		while (cur)
  15. 		{
  16. 			if (cur->_data > data)
  17. 			{
  18. 				parent = cur;
  19. 				cur = cur->_pLeft;
  20. 			}
  21. 			else if (cur->_data < data)
  22. 			{
  23. 				parent = cur;
  24. 				cur = cur->_pRight;
  25. 			}
  26. 			else
  27. 			{
  28. 				return false;
  29. 			}
  30. 		}
  31. 		Node* newnode = new Node(data);
  32. 		if (parent->_data < data)
  33. 		{
  34. 			parent->_pRight = newnode;
  35. 			newnode->_pParent = parent;
  36. 		}
  37. 		else
  38. 		{
  39. 			parent->_pLeft = newnode;
  40. 			newnode->_pParent = parent;
  41. 		}
  42. 		//向添加节点的祖先进行进行平衡因子的更新，查找是否有_bf>1的节点
  43. 		cur = newnode;
  44. 		parent = newnode->_pParent;
  45. 		while (parent)
  46. 		{
  47. 			if (cur == parent->_pLeft)
  48. 			{
  49. 				parent->_bf--;
  50. 			}
  51. 			else
  52. 			{
  53. 				parent->_bf++;
  54. 			}
  55.  
  56. 			//如果出现平衡因子为0，更新结束
  57. 			if (parent->_bf == 0)
  58. 			{
  59. 				break;
  60. 			}
  61. 			else if (parent->_bf ==1|| parent->_bf == -1)//如果平衡因子正常，继续向上进行更新
  62. 			{
  63. 				cur = parent;
  64. 				parent = parent->_pParent;
  65. 			}
  66. 			else if(parent->_bf == 2 || parent->_bf == -2)//平衡因子不正常，需要进行旋转
  67. 			{
  68.  
  69. 				if (parent->_bf == 2 && cur->_bf == 1)
  70. 				{
  71. 					RotateL(parent);
  72. 				}
  73. 				else if (parent->_bf == -2 && cur->_bf == -1)
  74. 				{
  75. 					RotateR(parent);
  76. 				}
  77. 				else if (parent->_bf == 2 && cur->_bf == -1)
  78. 				{
  79. 					RotateRL(parent);
  80. 				}
  81. 				else if (parent->_bf == -2 && cur->_bf == 1)
  82. 				{
  83. 					RotateLR(parent);  
  84. 				}
  85.  
  86. 				break;
  87. 			}
  88. 			else  //平衡因子大于2，出现问题
  89. 			{
  90. 				assert(false);
  91. 			}
  92. 		}
  93. 		return true;
  94. 	}

3.2 检查平衡性

检查AVL树是否平衡，我们需要计算左右子树的高度，使用递归操作可以简单实现，操作如下：

  1. public:
  2. bool IsBalance()
  3. {
  4. 	return IsBalance(_pRoot);
  5. }
  6.  
  7.  
  8. int Height()
  9. {
  10.     return Height(_pRoot);
  11. }
  12.  
  13.  
  14. //这样做的目的是为了让外部可以直接调用私有成员_pRoot
  15.  
  16.  
  17. private:
  18. int Height(Node* root)
  19. 	{
  20. 		if (root == nullptr)
  21. 			return 0;
  22.  
  23. 		int leftHeight = Height(root->_pLeft);
  24. 		int rightHeight = Height(root->_pRight);
  25.  
  26. 		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
  27. 	}
  28.  
  29. 	
  30. 	bool IsBalance(Node* root)
  31. 	{
  32. 		if (root == nullptr)
  33. 			return true;
  34.  
  35. 		int leftHight = Height(root->_pLeft);
  36. 		int rightHight = Height(root->_pRight);
  37.  
  38. 		if (rightHight - leftHight != root->_bf)
  39. 		{
  40. 			std::cout << "平衡因子异常:" << root->_data << "->" << root->_bf << std::endl;
  41. 			std::cout << leftHight << "  "<<rightHight << "  " << root->_bf;
  42. 			return false;
  43. 		}
  44.  
  45. 		return abs(rightHight - leftHight) < 2
  46. 			&& IsBalance(root->_pLeft)
  47. 			&& IsBalance(root->_pRight);
  48. 	}

最后，其实AVL树的删除，查找，删除等等操作我没有进行实现，因为其实只要掌握了插入，其他操作简简单单，如果我完成了AVL树的其他功能，我也会添加进来。

下面贴上完整代码供大家参考：

  1. #pragma once
  2. #include<cassert>
  3. #include<iostream>
  4.  
  5. template<class T>
  6. struct AVLTreeNode
  7. {
  8. 	AVLTreeNode(const T& data = T())
  9. 		: _pLeft(nullptr)
  10. 		, _pRight(nullptr)
  11. 		, _pParent(nullptr)
  12. 		, _data(data)
  13. 		, _bf(0)
  14. 	{}
  15.  
  16. 	AVLTreeNode<T>* _pLeft;
  17. 	AVLTreeNode<T>* _pRight;
  18. 	AVLTreeNode<T>* _pParent;
  19. 	T _data;
  20. 	int _bf;   // 节点的平衡因子
  21. };
  22.  
  23.  
  24. // AVL: 二叉搜索树 + 平衡因子的限制
  25. template<class T>
  26. class AVLTree
  27. {
  28. 	typedef AVLTreeNode<T> Node;
  29. public:
  30. 	AVLTree()
  31. 		: _pRoot(nullptr)
  32. 	{}
  33.  
  34. 	// 在AVL树中插入值为data的节点
  35. 	bool Insert(const T& data)
  36. 	{
  37. 		//树为空
  38. 		if (!_pRoot)
  39. 		{
  40. 			Node* newnode = new Node(data);
  41. 			_pRoot = newnode;
  42. 			return true;
  43. 		}
  44.  
  45. 		Node* parent =nullptr;
  46. 		Node* cur = _pRoot;
  47. 		while (cur)
  48. 		{
  49. 			if (cur->_data > data)
  50. 			{
  51. 				parent = cur;
  52. 				cur = cur->_pLeft;
  53. 			}
  54. 			else if (cur->_data < data)
  55. 			{
  56. 				parent = cur;
  57. 				cur = cur->_pRight;
  58. 			}
  59. 			else
  60. 			{
  61. 				return false;
  62. 			}
  63. 		}
  64. 		Node* newnode = new Node(data);
  65. 		if (parent->_data < data)
  66. 		{
  67. 			parent->_pRight = newnode;
  68. 			newnode->_pParent = parent;
  69. 		}
  70. 		else
  71. 		{
  72. 			parent->_pLeft = newnode;
  73. 			newnode->_pParent = parent;
  74. 		}
  75. 		//向添加节点的祖先进行进行平衡因子的更新，查找是否有_bf>1的节点
  76. 		cur = newnode;
  77. 		parent = newnode->_pParent;
  78. 		while (parent)
  79. 		{
  80. 			if (cur == parent->_pLeft)
  81. 			{
  82. 				parent->_bf--;
  83. 			}
  84. 			else
  85. 			{
  86. 				parent->_bf++;
  87. 			}
  88.  
  89. 			//如果出现平衡因子为0，更新结束
  90. 			if (parent->_bf == 0)
  91. 			{
  92. 				break;
  93. 			}
  94. 			else if (parent->_bf ==1|| parent->_bf == -1)//如果平衡因子正常，继续向上进行更新
  95. 			{
  96. 				cur = parent;
  97. 				parent = parent->_pParent;
  98. 			}
  99. 			else if(parent->_bf == 2 || parent->_bf == -2)//平衡因子不正常，需要进行旋转
  100. 			{
  101.  
  102. 				if (parent->_bf == 2 && cur->_bf == 1)
  103. 				{
  104. 					RotateL(parent);
  105. 				}
  106. 				else if (parent->_bf == -2 && cur->_bf == -1)
  107. 				{
  108. 					RotateR(parent);
  109. 				}
  110. 				else if (parent->_bf == 2 && cur->_bf == -1)
  111. 				{
  112. 					RotateRL(parent);
  113. 				}
  114. 				else if (parent->_bf == -2 && cur->_bf == 1)
  115. 				{
  116. 					RotateLR(parent);  
  117. 				}
  118.  
  119. 				break;
  120. 			}
  121. 			else  //平衡因子大于2，出现问题
  122. 			{
  123. 				assert(false);
  124. 			}
  125. 		}
  126. 		return true;
  127. 	}
  128.  
  129. 	// AVL树的验证
  130. 	bool IsBalance()
  131. 	{
  132. 		return IsBalance(_pRoot);
  133. 	}
  134.  
  135.  
  136. 	int Height()
  137. 	{
  138. 		return Height(_pRoot);
  139. 	}
  140.  
  141.  
  142. private:
  143.  
  144. 	// 根据AVL树的概念验证pRoot是否为有效的AVL树
  145. 	
  146. 	int Height(Node* root)
  147. 	{
  148. 		if (root == nullptr)
  149. 			return 0;
  150.  
  151. 		int leftHeight = Height(root->_pLeft);
  152. 		int rightHeight = Height(root->_pRight);
  153.  
  154. 		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
  155. 	}
  156.  
  157. 	
  158. 	bool IsBalance(Node* root)
  159. 	{
  160. 		if (root == nullptr)
  161. 			return true;
  162.  
  163. 		int leftHight = Height(root->_pLeft);
  164. 		int rightHight = Height(root->_pRight);
  165.  
  166. 		if (rightHight - leftHight != root->_bf)
  167. 		{
  168. 			std::cout << "平衡因子异常:" << root->_data << "->" << root->_bf << std::endl;
  169. 			std::cout << leftHight << "  "<<rightHight << "  " << root->_bf;
  170. 			return false;
  171. 		}
  172.  
  173. 		return abs(rightHight - leftHight) < 2
  174. 			&& IsBalance(root->_pLeft)
  175. 			&& IsBalance(root->_pRight);
  176. 	}
  177.  
  178. 	// 右单旋
  179. 	void RotateR(Node* pParent)
  180. 	{
  181. 		Node* cur = pParent->_pLeft;
  182. 		Node* curright = cur->_pRight;
  183.  
  184. 		//右旋第一步，cur的右子树给parent的左子树
  185. 		pParent->_pLeft = curright;
  186. 		if (curright)
  187. 		{
  188. 			curright->_pParent = pParent;
  189. 		}
  190.  
  191. 		//右旋第二步，parent变为cur的右子树
  192. 		cur->_pRight = pParent;
  193. 		Node* ppnode = pParent->_pParent;
  194. 		pParent->_pParent = cur;
  195.  
  196. 		if (pParent == _pRoot)
  197. 		{
  198. 			_pRoot = cur;
  199. 			cur->_pParent = nullptr;
  200. 		}
  201. 		else
  202. 		{
  203. 			if (ppnode->_pLeft == pParent)
  204. 			{
  205. 				ppnode->_pLeft = cur;
  206. 				cur->_pParent = ppnode;
  207. 			}
  208. 			else
  209. 			{
  210. 				ppnode->_pRight = cur;
  211. 				cur->_pParent = ppnode;
  212. 			}
  213. 		}
  214. 		cur->_bf = pParent->_bf = 0;
  215.  
  216. 	}
  217.  
  218.  
  219.  
  220. 	// 左单旋
  221. 	void RotateL(Node* pParent)
  222. 	{
  223. 		Node* cur = pParent->_pRight;
  224. 		Node* curleft = cur->_pLeft;
  225.  
  226. 		//左旋第一步，cur的左树变为parent的右子树
  227. 		pParent->_pRight = curleft;
  228. 		if (curleft)
  229. 		{
  230. 			curleft->_pParent = pParent;
  231. 		}
  232.  
  233. 		//左旋第二步，parent变为cur的左子树
  234. 		cur->_pLeft = pParent;
  235.  
  236. 		//记录根节点的上一个节点
  237. 		Node* ppnode = pParent->_pParent;
  238.  
  239. 		pParent->_pParent = cur;
  240.  
  241. 		if (pParent == _pRoot)//如果parent已经是根节点了
  242. 		{
  243. 			_pRoot = cur;
  244. 			cur->_pParent = nullptr;
  245. 		}
  246. 		else    //如果parent不是根节点，需要把cur与前面节点进行连接
  247. 		{
  248. 			if (ppnode->_pLeft == pParent)//如果原来的parent是上一节点的左孩子
  249. 			{
  250. 				ppnode->_pLeft = cur;
  251. 				cur->_pParent = ppnode;  
  252. 			}
  253. 			else                         //如果原来的parent是上一节点的右孩子
  254. 			{
  255. 				ppnode->_pRight = cur;
  256. 				cur->_pParent = ppnode;
  257. 			}
  258. 		}
  259.  
  260. 		//完成平衡因子的修改
  261. 		cur->_bf = pParent->_bf = 0;
  262.  
  263.  
  264. 	}
  265.  
  266. 	// 右左双旋
  267. 	void RotateRL(Node* pParent)
  268. 	{
  269. 		RotateR(pParent->_pRight);
  270. 		RotateL(pParent);
  271. 	}
  272.  
  273. 	// 左右双旋
  274. 	void RotateLR(Node* pParent)
  275. 	{
  276. 		RotateL(pParent->_pLeft);
  277. 		RotateR(pParent);
  278. 	}
  279.  
  280. private:
  281. 	Node* _pRoot;
  282. };
  283.  
  284.

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/511526
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号