[C++知识库]C++二叉树的代码实现（含迭代器）

二叉树

简单介绍

二叉树（BinaryTree），就是一棵有左右两个节点的树，这里不再具体讲二叉树的原理是什么，而是着重于二叉树的C++代码实现。不同于一般的二叉树实现，这里更突出如何实现二叉树的迭代器，以及如何串行化初始化一棵二叉树。

注意：代码中使用了 C++17 的特性 if constexpr

BinaryTree 类内的成员函数速览

1. size_t height()- 获取树的高度
2. size_t size() - 获取树的节点数
3. iterator root_node() - 获取树的根节点（迭代器）
4. const_iterator root_node() const - 同上，常量迭代器版本
5. iterator insert_left(iterator node, const _Ty& val) - 在节点左侧插入一个节点，如果已经存在左节点则替换值
6. iterator insert_right(iterator node, const _Ty& val) - 在节点右侧插入一个节点，如果已经存在右节点则替换值
7. iterator erase(iterator node) - 删除一个节点以及该节点往下的子节点
8. preorder_iterator preorder(const iterator& itr = iterator(nullptr, nullptr)) - 获取先序遍历的迭代器
9. preorder_const_iterator preorder_const(const iterator& itr = iterator(nullptr, nullptr)) - 获取先序遍历的常量迭代器
10. inorder_iterator inorder(const iterator& itr = iterator(nullptr, nullptr)) - 获取中序遍历的迭代器
11. inorder_const_iterator inorder_const(const iterator& itr = iterator(nullptr, nullptr)) - 获取中序遍历的常量迭代器
12. postorder_iterator postorder(const iterator& itr = iterator(nullptr, nullptr)) - 获取后序遍历的迭代器
13. postorder_const_iterator postorder_const(const iterator& itr = iterator(nullptr, nullptr)) - 获取后序遍历的常量迭代器
14. preorder_reverse_iterator preorder_reverse(const iterator& itr = iterator(nullptr, nullptr)) - 获取先序遍历的反向迭代器
15. preorder_reverse_const_iterator preorder_reverse_const(const iterator& itr = iterator(nullptr, nullptr)) - 获取先序遍历的反向常量迭代器
16. inorder_reverse_iterator inorder_reverse(const iterator& itr = iterator(nullptr, nullptr)) - 获取中序遍历的反向迭代器
17. inorder_reverse_const_iterator inorder_reverse_const(const iterator& itr = iterator(nullptr, nullptr)) - 获取中序遍历的反向常量迭代器
18. postorder_reverse_iterator postorder_reverse(const iterator& itr = iterator(nullptr, nullptr)) - 获取后序遍历的反向迭代器
19. postorder_reverse_const_iterator postorder_reverse_const(const iterator& itr = iterator(nullptr, nullptr)) - 获取后序遍历的反向常量迭代器

节点的实现

想要实现一棵二叉树，首先得实现它的节点。该节点应该要具有以下特征：

1. 储存了节点的值
2. 可以访问左右节点

当然，一般而言，二叉树实现以上两点即可，当时为了便于后面迭代器的实现，这里还另外存储了父节点，使得子节点可以访问父节点。

template<class _Ty>
class BinaryTree
{
private:
	/*
	* @brief 二叉树节点
	*/
	struct BinaryTreeNode
	{
		_Ty val;
		BinaryTreeNode* parent = nullptr;
		BinaryTreeNode* left = nullptr;
		BinaryTreeNode* right = nullptr;

		BinaryTreeNode() { val = _Ty(); }
		BinaryTreeNode(_Ty val, BinaryTreeNode* parent = nullptr) :val(val), parent(parent) {}
		~BinaryTreeNode()
		{
			if (left) delete left;
			if (right) delete right;
		}

		//深拷贝
		BinaryTreeNode(const BinaryTreeNode& node)
		{
			this->val = node.val;
			if (node.left) this->left = new BinaryTreeNode(node.left);
			if (node.right) this->right = new BinaryTreeNode(node.right);
		}

		//节点数
		size_t size() const
		{
			const size_t left_sz = left == nullptr ? 0 : left->size();
			const size_t right_sz = right == nullptr ? 0 : right->size();
			return 1 + left_sz + right_sz;
		}

		//高度
		size_t height() const
		{
			const size_t left_height = left == nullptr ? 0 : left->height();
			const size_t right_height = right == nullptr ? 0 : right->height();
			return 1 + std::max(left_height, right_height);
		}
	};

	...
}

节点的获取、插入和删除

因为我们实现的二叉树是有迭代器的，因此节点的获取、插入和删除均是借由迭代来完成。这里有一点需要注意的是：需要判断迭代器是否是该容器的。

template<class _Ty>
class BinaryTree
{
public:
	/*
	* @brief 获取根节点
	* @return 迭代器
	*/
	iterator root_node()
	{
		return iterator(root, this);
	}

	/*
	* @brief 获取根节点
	* @return 迭代器
	*/
	const_iterator root_node() const
	{
		return const_iterator(root, this);
	}

	/*
	* @brief 在节点左侧插入一个节点，如果已经存在左节点则替换值
	* @param 迭代器，决定要进行左插入的节点
	* @param 新插入节点的值
	* @return 新插入节点的迭代器
	* @exception 提供其他树的节点会抛出 WrongIterator 异常
	*/
	iterator insert_left(iterator node, const _Ty& val)
	{
		if (node.container != this) throw "WrongIterator";
		if (node.now->left)
		{
			node.now->left->val = val;
		}
		else
		{
			node.now->left = new BinaryTreeNode(val);
			node.now->left->parent = node.now;
		}
		return node.left();
	}

	/*
	* @brief 在节点右侧插入一个节点，如果已经存在右节点则替换值
	* @param 迭代器，决定要进行右插入的节点
	* @param 新插入节点的值
	* @return 新插入节点的迭代器
	* @exception 提供其他树的节点会抛出 WrongIterator 异常
	*/
	iterator insert_right(iterator node, const _Ty& val)
	{
		if (node.container != this) throw "WrongIterator";
		if (node.now->right)
		{
			node.now->right->val = val;
		}
		else
		{
			node.now->right = new BinaryTreeNode(val);
			node.now->right->parent = node.now;
		}
		return node.right();
	}

	/*
	* @brief 删除一个节点以及该节点往下的子节点
	* @param 迭代器，被删除的节点
	* @return 被删除节点的父节点的迭代器
	* @exception 删除根节点会抛出 CanNotEraseRoot 异常，提供其他树的节点会抛出 WrongIterator 异常
	*/
	iterator erase(iterator node)
	{
		if (node.container != this) throw "WrongIterator";
		if (node.now == root) throw "CanNotEraseRoot";
		iterator parent = node.parent();
		if (parent.now->left == node.now) parent.now->left = nullptr;
		else if (parent.now->right == node.now) parent.now->right = nullptr;
		delete node.now;
		return parent;
	}
	
	...
}

迭代器的实现

对节点做迭代器的封装并不难，难的是如何让迭代器在先序遍历、中序遍历、后序遍历三种不同的遍历情况下取 上一个节点 和 下一个节点 （只用当前节点的状态进行推断）。这里我们只说怎么取得 下一个节点 ， 上一个节点 用类似方法也可以得出如何遍历取得。

1.先序遍历

对于先序遍历，遍历的顺序是：自己 -> 左 -> 右，如下图所示：

这里可以看出，这里遍历的起点是根节点，结束的节点是最右侧节点。假设我们的迭代器所在节点有左子节点的话，下一步遍历便是左子节点。如果没有左子节点，但是有右子节点的话，下一步遍历就是右子节点。但如果没有子节点，我们便要回退，找到一个有右节点的父节点，且该父节点的右节点不为自己的节点，这个父节点的右子节点便是下一个要遍历的节点（关于回退这一点，具体可见 第三步遍历到第四步遍历 和 第四步遍历到第五步遍历）。

// 先序遍历取上一个节点
{
	//如果存在父节点，优先往父节点走
	if (now->parent)
	{
		//如果是左侧节点且没有右侧节点，上一个节点就是父节点
		if (now == now->parent->left)
			now = now->parent;
		//如果是右侧节点且没有左侧节点，上一个节点是父节点
		else if (now == now->parent->right && now->parent->left == nullptr)
			now = now->parent;
		//如果是右侧节点且有左侧节点，上一个节点是左侧节点的最底部节点
		else
		{
			now = now->parent->left;
			while (now->left || now->right)
				now = now->right == nullptr ? now->left : now->right;
		}
	}
	//没有父节点，上一个即是最右侧节点
	else
	{
		while (now->right)
			now = now->right;
	}
}

// 先序遍历取下一个节点
{
	//如果自己存在左节点
	//往左节点走
	if (now->left)
		now = now->left;
	//否则如果存在右节点
	//往右节点走
	else if (now->right)
		now = now->right;
	//如果没有子节点 但是 有父节点
	else if(now->parent)
	{
		//往上探索，直到父节点存在右节点并且不是自己
		do
		{
			if (now->parent->right != nullptr && now->parent->right != now)
			{
				now = now->parent->right;
				break;
			}
			else
			{
				now = now->parent;
			}
		} while (now->parent);
	}
}

2.中序遍历

对于先序遍历，遍历的顺序是：左 -> 自己 -> 右，如下图所示：

可以看出，这里遍历的起点与先序遍历不同，是从最左侧节点开始的，并且以最右侧节点为结束节点。首先，因为遍历永远从左节点开始，因为下一个节点永远不可能是自己的左子节点以及自己的左子节点所在下面的部分。假设节点有右节点，那么下一个节点就是右子节点的最左侧节点（具体见第五步遍历到第六步遍历）。假设节点没有子节点，那么就看看自己是父节点的左子节点还是右子节点，如果自己是父节点的左子节点，那么下一个节点就是自己的父节点，如果自己是父节点的右子节点，那么把节点转移到父节点这个位置上，重新做上述流程（具体见 第二步遍历到第三步遍历 和 第六步遍历到第七步遍历）。

// 中序遍历取上一个节点
{
	//如果有左节点，上一个节点就是左节点的最右侧节点
	if (now->left)
	{
		now = now->left;
		while (now->right)
			now = now->right;
	}
	//如果没有左节点，但是有父节点
	else if (now->parent)
	{
		//自己是父节点的右节点，上一个节点就是父节点
		if (now == now->parent->right)
			now = now->parent;
		//自己是父节点的左节点
		else
		{
			//向上探索，直到找到自己属于右节点
			bool left_jump = true;
			do
			{
				if (now == now->parent->right)
				{
					left_jump = false;
					now = now->parent;
					break;
				}
				now = now->parent;
			} while (now->parent);
		
			//如果是从左边一直跳上来的，且该节点没有父节点，说明已经是头部，需要跳到最右侧节点
			if(left_jump && now->parent == nullptr)
				while (now->right)
					now = now->right;
		}
	}
	//既没有父节点，也没有左节点，上一个节点就是最右侧节点
	else
	{
		while (now->right)
			now = now->right;
	}
}

// 中序遍历取下一个节点
{
	//如果存在右节点，往右节点走，走到右节点的底部
	if (now->right)
	{
		now = now->right;
		while (now->left)
			now = now->left;
	}
	//如果没有右节点，但是有父节点，并且自己是父节点的左节点，则往父节点走
	else if (now->parent && now == now->parent->left)
		now = now->parent;
	//如果自己是父节点的右节点
	else if (now->parent && now == now->parent->right)
	{
		//往上探索，直到自己是父节点的左节点
		bool right_jump = true;
		do
		{
			if (now->parent->left == now)
			{
				now = now->parent;
				right_jump = false;
				break;
			}
			now = now->parent;
		} while (now->parent);

		//从右侧上去，且没有父节点，说明到头了，回到最左侧节点
		if(right_jump && now->parent == nullptr)
			while (now->left)
				now = now->left;
	}
	//没有右节点也没有父节点，走到最左侧节点
	else
	{
		while (now->left)
			now = now->left;
	}
}

3.后序遍历

对于后序遍历，遍历的顺序是：左 -> 右 -> 自己，如下图所示：

可以看出，这里的根节点反而是结束的节点了，最左侧的最下侧的节点才是开始的节点。这里更直接了，由于后序遍历的性质，下一个节点压根不可能是自己的子节点以及往下的部分，我们只需考虑自己在父节点中的位置即可。假设自己是父节点的左子节点，如果父节点没有右子节点，那么下一个节点就是父节点（具体见 第五步遍历到第六步遍历 及 第六步遍历到第七步遍历）；如果父节点有右子节点，那么下一个节点就是父节点的右节点的最左侧的最下侧（具体见 第四步遍历到第五步遍历）。假设自己是父节点的右节点，那么下一个节点就是父节点（具体见 第一步遍历到第二步遍历 及 第三步遍历到第四步遍历）。

// 后序遍历取上一个节点
{
	//如果有右节点，上一个节点就是右节点
	if (now->right)
			now = now->right;
		//如果没有右节点，但是有左节点，上一个节点就是左节点
		else if (now->left)
			now = now->left;
		//如果没有左右节点，但是有父节点，一直往父节点上跳，直到找到左节点
		else if (now->parent)
		{
			do
			{
				if (now->parent->left != nullptr && now->parent->right == now)
				{
					now = now->parent->left;
					break;
				}
				now = now->parent;
			} while (now->parent);
		}
}

// 后序遍历取下一个节点
{
	//如果存在父节点，父节点没有右节点且自己是父节点的左节点，跳到父节点
	if (now->parent && now->parent->right == nullptr && now->parent->left == now)
		now = now->parent;
	//如果存在父节点，且自己是父节点的右节点，跳到父节点
	else if (now->parent && now->parent->right == now)
		now = now->parent;
	//如果存在父节点，父节点有右节点且自己是父节点的左节点，跳到父节点的右节点的最底部
	else if (now->parent && now->parent->right != nullptr && now->parent->left == now)
	{
		now = now->parent->right;
		while (now->left || now->right)
			now = now->left == nullptr ? now->right : now->left;
	}
	//没有父节点，说明已经到终点了，跳回最左侧的最底部
	else
	{
		while (now->left || now->right)
			now = now->left == nullptr ? now->right : now->left;
	}
}

迭代器的获取

在完成了的迭代器的前向和后向移动后，便可以提供多种多样的迭代器了。

template<class _Ty>
class BinaryTree
{
public:
	//通用迭代器
	using iterator = _IteratorBase<_Ty>;
	using const_iterator = _IteratorBase<const _Ty>;

	//正向迭代器
	using preorder_iterator = _Iterator<_Ty, -1>;
	using preorder_const_iterator = _Iterator<const _Ty, -1>;
	using inorder_iterator = _Iterator<_Ty, 0>;
	using inorder_const_iterator = _Iterator<const _Ty, 0>;
	using postorder_iterator = _Iterator<_Ty, 1>;
	using postorder_const_iterator = _Iterator<const _Ty, 1>;

	//反向迭代器
	using preorder_reverse_iterator = _Reverse_Iterator<preorder_iterator>;
	using preorder_reverse_const_iterator = _Reverse_Iterator<preorder_const_iterator>;
	using inorder_reverse_iterator = _Reverse_Iterator<inorder_iterator>;
	using inorder_reverse_const_iterator = _Reverse_Iterator<inorder_const_iterator>;
	using postorder_reverse_iterator = _Reverse_Iterator<postorder_iterator>;
	using postorder_reverse_const_iterator = _Reverse_Iterator<postorder_const_iterator>;

	/*
	* @brief 获取先序遍历的迭代器
	* @param 初始节点 - 默认是默认起始节点
	* @return 先序遍历的迭代器
	* @exception 提供其他树的节点会抛出 WrongIterator 异常
	*/
	preorder_iterator preorder(const iterator& itr = iterator(nullptr, nullptr))
	{
		if (itr.now == nullptr) return preorder_iterator(root, this);
		if (itr.container != this) throw "WrongIterator";
		return preorder_iterator(itr.now, this, false);
	}

	/*
	* @brief 获取先序遍历的迭代器
	* @param 初始节点 - 默认是默认起始节点
	* @return 先序遍历的迭代器
	* @exception 提供其他树的节点会抛出 WrongIterator 异常
	*/
	preorder_const_iterator preorder_const(const iterator& itr = iterator(nullptr, nullptr)) const
	{
		if (itr.now == nullptr) return preorder_const_iterator(root, this);
		if (itr.container != this) throw "WrongIterator";
		return preorder_const_iterator(itr.now, this, false);
	}

	/*
	* @brief 获取中序遍历的迭代器
	* @param 初始节点 - 默认是默认起始节点
	* @return 中序遍历的迭代器
	* @exception 提供其他树的节点会抛出 WrongIterator 异常
	*/
	inorder_iterator inorder(const iterator& itr = iterator(nullptr, nullptr))
	{
		if (itr.now == nullptr) return inorder_iterator(root, this);
		if (itr.container != this) throw "WrongIterator";
		return inorder_iterator(itr.now, this, false);
	}

	/*
	* @brief 获取中序遍历的迭代器
	* @param 初始节点 - 默认是默认起始节点
	* @return 中序遍历的迭代器
	* @exception 提供其他树的节点会抛出 WrongIterator 异常
	*/
	inorder_const_iterator inorder_const(const iterator& itr = iterator(nullptr, nullptr)) const
	{
		if (itr.now == nullptr) return inorder_const_iterator(root, this);
		if (itr.container != this) throw "WrongIterator";
		return inorder_const_iterator(itr.now, this, false);
	}

	/*
	* @brief 获取后序遍历的迭代器
	* @param 初始节点 - 默认是默认起始节点
	* @return 后序遍历的迭代器
	* @exception 提供其他树的节点会抛出 WrongIterator 异常
	*/
	postorder_iterator postorder(const iterator& itr = iterator(nullptr, nullptr))
	{
		if (itr.now == nullptr) return postorder_iterator(root, this);
		if (itr.container != this) throw "WrongIterator";
		return postorder_iterator(itr.now, this, false);
	}

	/*
	* @brief 获取后序遍历的迭代器
	* @param 初始节点 - 默认是默认起始节点
	* @return 后序遍历的迭代器
	* @exception 提供其他树的节点会抛出 WrongIterator 异常
	*/
	postorder_const_iterator postorder_const(const iterator& itr = iterator(nullptr, nullptr)) const
	{
		if (itr.now == nullptr) return postorder_const_iterator(root, this);
		if (itr.container != this) throw "WrongIterator";
		return postorder_const_iterator(itr.now, this, false);
	}

	/*
	* @brief 获取先序遍历的反向迭代器
	* @param 初始节点 - 默认是默认起始节点
	* @return 先序遍历的反向迭代器
	* @exception 提供其他树的节点会抛出 WrongIterator 异常
	*/
	preorder_reverse_iterator preorder_reverse(const iterator& itr = iterator(nullptr, nullptr))
	{
		if (itr.now == nullptr) return preorder_reverse_iterator(root, this);
		if (itr.container != this) throw "WrongIterator";
		return preorder_reverse_iterator(itr.now, this, false);
	}

	/*
	* @brief 获取先序遍历的反向迭代器
	* @param 初始节点 - 默认是默认起始节点
	* @return 先序遍历的反向迭代器
	* @exception 提供其他树的节点会抛出 WrongIterator 异常
	*/
	preorder_reverse_const_iterator preorder_reverse_const(const iterator& itr = iterator(nullptr, nullptr)) const
	{
		if (itr.now == nullptr) return preorder_reverse_const_iterator(root, this);
		if (itr.container != this) throw "WrongIterator";
		return preorder_reverse_const_iterator(itr.now, this, false);
	}

	/*
	* @brief 获取中序遍历的反向迭代器
	* @param 初始节点 - 默认是默认起始节点
	* @return 中序遍历的反向迭代器
	* @exception 提供其他树的节点会抛出 WrongIterator 异常
	*/
	inorder_reverse_iterator inorder_reverse(const iterator& itr = iterator(nullptr, nullptr))
	{
		if (itr.now == nullptr) return inorder_reverse_iterator(root, this);
		if (itr.container != this) throw "WrongIterator";
		return inorder_reverse_iterator(itr.now, this, false);
	}

	/*
	* @brief 获取中序遍历的反向迭代器
	* @param 初始节点 - 默认是默认起始节点
	* @return 中序遍历的反向迭代器
	* @exception 提供其他树的节点会抛出 WrongIterator 异常
	*/
	inorder_reverse_const_iterator inorder_reverse_const(const iterator& itr = iterator(nullptr, nullptr)) const
	{
		if (itr.now == nullptr) return inorder_reverse_const_iterator(root, this);
		if (itr.container != this) throw "WrongIterator";
		return inorder_reverse_const_iterator(itr.now, this, false);
	}

	/*
	* @brief 获取后序遍历的反向迭代器
	* @param 初始节点 - 默认是默认起始节点
	* @return 后序遍历的反向迭代器
	* @exception 提供其他树的节点会抛出 WrongIterator 异常
	*/
	postorder_reverse_iterator postorder_reverse(const iterator& itr = iterator(nullptr, nullptr))
	{
		if (itr.now == nullptr) return postorder_reverse_iterator(root, this);
		if (itr.container != this) throw "WrongIterator";
		return postorder_reverse_iterator(itr.now, this, false);
	}

	/*
	* @brief 获取后序遍历的反向迭代器
	* @param 初始节点 - 默认是默认起始节点
	* @return 后序遍历的反向迭代器
	* @exception 提供其他树的节点会抛出 WrongIterator 异常
	*/
	postorder_reverse_const_iterator postorder_reverse_const(const iterator& itr = iterator(nullptr, nullptr)) const
	{
		if (itr.now == nullptr) return postorder_reverse_const_iterator(root, this);
		if (itr.container != this) throw "WrongIterator";
		return postorder_reverse_const_iterator(itr.now, this, false);
	}

	...
}

串行初始化的实现

在各种涉及到树的题目中，我们经常能见到树的串行初始化数据，那么我们怎么自己实现串行数据初始化一棵二叉树呢？

串行初始化一个树的过程可以描述为：

1. 对于串行数据，依次获取下一个节点的初始化值，如果值为nullptr，说明下一个节点为空，否则初始化下一个节点；
2. 对于一颗二叉树，初始化的顺序为层序，即先将某一层初始化完毕，再初始化下一层；
3. 同一层内，初始化的顺序为从左到右。

为了在 C++ 中实现数据和nullptr可以同时输入到串行化序列中。我们首先要实现一个包装类如下：

template<class _Ty>
class BinaryTree
{
private:
	/*
	* @brief 用于树的串行初始化
	*/
	struct serial_initializer
	{
		const _Ty* val = nullptr;

		serial_initializer(const void*) {}

		serial_initializer(const _Ty& val)
		{
			this->val = &val;
		}

		//是否为空数据
		bool isNull() const
		{
			return val == nullptr;
		}

		//获取数据的值
		const _Ty& getVal() const
		{
			return *val;
		}
	};
	
	...
}

实现这一包装类后，我们可以配合 initializer_list 完成串行序列初始化。

template<class _Ty>
class BinaryTree
{
public:
	/*
	* @brief 串行初始化树
	* @param 串行参数列表
	* @exception 如果给的串行数据不合法，会抛出 WrongInitializer 异常
	*/
	BinaryTree(std::initializer_list<serial_initializer> ini_list)
	{
		if (ini_list.size() == 0 || ini_list.begin()->isNull()) throw "WrongInitializer";
	
		//初始化根节点
		root = new BinaryTreeNode(ini_list.begin()->getVal());
	
		//用于装节点
		BinaryTreeNode** all_nodes = new BinaryTreeNode * [ini_list.size()]{ nullptr };
		BinaryTreeNode** nodes = all_nodes;
		BinaryTreeNode** next_nodes = all_nodes + (ini_list.size() >> 1);
		size_t nodes_size = 0, next_nodes_size = 0;
		//记录当前是写入左节点还是右节点
		bool write_left = true;
	
		//装入根节点
		nodes[0] = root;
		nodes_size = 1;
	
		//记录当前的写入位置
		size_t idx = 0;
	
		for (auto itr = ini_list.begin() + 1; itr != ini_list.end(); ++itr)
		{
			if (!itr->isNull())
			{
				if (write_left)
				{
					nodes[idx]->left = new BinaryTreeNode(itr->getVal());
					nodes[idx]->left->parent = nodes[idx];
					next_nodes[next_nodes_size++] = nodes[idx]->left;
				}
				else
				{
					nodes[idx]->right = new BinaryTreeNode(itr->getVal());
					nodes[idx]->right->parent = nodes[idx];
					next_nodes[next_nodes_size++] = nodes[idx]->right;
				}
			}
			write_left = !write_left;
			if (write_left && ++idx >= nodes_size)
			{
				if (next_nodes_size == 0) break;
				std::swap(nodes, next_nodes);
				std::swap(nodes_size, next_nodes_size);
				idx = 0;
				next_nodes_size = 0;
			}
		}
	
		//释放堆内存
		delete[] all_nodes;
	}

	...
}

完整代码

// BinaryTree.h

#ifndef __YYYCZ_BINARY_TREE__
#define __YYYCZ_BINARY_TREE__

#include<initializer_list>
#include<xtr1common>
#include<utility>
#include<iterator>

namespace YYYCZ
{
	/*
	* @brief 二叉树
	* @author YYYCZ
	* @date 2021-11-06
	*/
	template<class _Ty>
	class BinaryTree
	{
		using _Self = BinaryTree<_Ty>;

		/*
		* @brief 用于树的串行初始化
		*/
		struct serial_initializer
		{
			const _Ty* val = nullptr;

			serial_initializer(const void*) {}

			serial_initializer(const _Ty& val)
			{
				this->val = &val;
			}

			//是否为空数据
			bool isNull() const
			{
				return val == nullptr;
			}

			//获取数据的值
			const _Ty& getVal() const
			{
				return *val;
			}
		};

		/*
		* @brief 二叉树节点
		*/
		struct BinaryTreeNode
		{
			_Ty val;
			BinaryTreeNode* parent = nullptr;
			BinaryTreeNode* left = nullptr;
			BinaryTreeNode* right = nullptr;

			BinaryTreeNode() { val = _Ty(); }
			BinaryTreeNode(_Ty val, BinaryTreeNode* parent = nullptr) :val(val), parent(parent) {}
			~BinaryTreeNode()
			{
				if (left) delete left;
				if (right) delete right;
			}

			//深拷贝
			BinaryTreeNode(const BinaryTreeNode& node)
			{
				this->val = node.val;
				if (node.left) this->left = new BinaryTreeNode(node.left);
				if (node.right) this->right = new BinaryTreeNode(node.right);
			}

			//节点数
			size_t size() const
			{
				const size_t left_sz = left == nullptr ? 0 : left->size();
				const size_t right_sz = right == nullptr ? 0 : right->size();
				return 1 + left_sz + right_sz;
			}

			//高度
			size_t height() const
			{
				const size_t left_height = left == nullptr ? 0 : left->height();
				const size_t right_height = right == nullptr ? 0 : right->height();
				return 1 + std::max(left_height, right_height);
			}
		};

	protected:
		//根节点
		BinaryTreeNode* root = nullptr;

	protected:
		/*
		* @brief 通用迭代器
		*/
		template<class _Val>
		class _IteratorBase
		{
			using _Self = _IteratorBase<_Val>;
			using _NoConstSelf = _IteratorBase<std::remove_const_t<_Val>>;
			using _ConstSelf = _IteratorBase<const std::remove_const_t<_Val>>;
			using _OtherSelf = std::conditional_t<std::is_same_v<_Self, _NoConstSelf>, _ConstSelf, _NoConstSelf>;
			friend BinaryTree<std::remove_const_t<_Val>>;

		protected:
			//当前节点
			BinaryTreeNode* now = nullptr;
			//容器
			const BinaryTree* container = nullptr;

		public:
			_IteratorBase(const BinaryTreeNode* root, const BinaryTree* container)noexcept :container(container)
			{
				now = const_cast<BinaryTreeNode*>(root);
			}

			/*
			* @brief 迭代器类型转换
			* @return 迭代器
			*/
			operator _OtherSelf() const noexcept
			{
				return _OtherSelf(now);
			}

			/*
			* @brief 迭代器类指针使用
			* @return 二叉树节点值的指针
			*/
			_Val* operator->() const
			{
				return const_cast<_Val*>(&(now->val));
			}

			/*
			* @brief 取出迭代器指向的节点的值
			* @return 二叉树节点值的引用
			*/
			_Val& operator*() const
			{
				return const_cast<_Val&>(now->val);
			}

			/*
			* @brief 是否有父节点
			* @return 布尔值
			*/
			bool hasParent() const
			{
				return now->parent != nullptr;
			}

			/*
			* @brief 是否有左节点
			* @return 布尔值
			*/
			bool hasLeft() const
			{
				return now->left != nullptr;
			}

			/*
			* @brief 是否有右节点
			* @return 布尔值
			*/
			bool hasRight() const
			{
				return now->right != nullptr;
			}

			/*
			* @breif 迭代器左移
			* @return 迭代器引用
			* @exception 如果不存在左节点将抛出 NoLeft 异常
			*/
			_Self& leftMove()
			{
				if (now->left == nullptr) throw "NoLeft";
				now = now->left;
				return *this;
			}

			/*
			* @breif 迭代器右移
			* @return 迭代器引用
			* @exception 如果不存在右节点将抛出 NoRight 异常
			*/
			_Self& rightMove()
			{
				if (now->right == nullptr) throw "NoRight";
				now = now->right;
				return *this;
			}

			/*
			* @breif 迭代器上移
			* @return 迭代器引用
			* @exception 如果不存在父节点将抛出 NoParent 异常
			*/
			_Self& parentMove()
			{
				if (now->parent == nullptr) throw "NoParent";
				now = now->parent;
				return *this;
			}

			/*
			* @breif 获取左节点的迭代器
			* @return 迭代器
			* @exception 如果不存在左节点将抛出 NoLeft 异常
			*/
			_Self left() const
			{
				auto tmp = *this;
				return tmp.leftMove();
			}

			/*
			* @breif 获取右节点的迭代器
			* @return 迭代器
			* @exception 如果不存在右节点将抛出 NoRight 异常
			*/
			_Self right() const
			{
				auto tmp = *this;
				return tmp.rightMove();
			}

			/*
			* @breif 获取父节点的迭代器
			* @return 迭代器
			* @exception 如果不存在父节点将抛出 NoParent 异常
			*/
			_Self parent() const
			{
				auto tmp = *this;
				return tmp.parentMove();
			}

			/*
			* @brief 判断两个迭代器是否相等
			* @param 另一迭代器
			* @return 布尔值
			*/
			bool operator==(const _Self& itr) const
			{
				return this->now == itr.now;
			}

			/*
			* @brief 判断两个迭代器是否不相等
			* @param 另一迭代器
			* @return 布尔值
			*/
			bool operator!=(const _Self& itr) const
			{
				return this->now != itr.now;
			}
		};

		/*
		* @brief 二叉树的迭代器
		*/
		template<class _Val, int _Order>
		class _Iterator
		{
			using _Self = _Iterator<_Val, _Order>;

		public:
			using _Base = _IteratorBase<_Val>;
			using ValueType = _Val;

		private:
			//当前节点
			BinaryTreeNode* now = nullptr;
			//容器
			const BinaryTree* container = nullptr;

		protected:
			/*
			* @brief 使当前节点移动到上一个节点
			*/
			void last()
			{
				//先序遍历
				if constexpr (_Order == -1)
				{
					//如果存在父节点，优先往父节点走
					if (now->parent)
					{
						//如果是左侧节点且没有右侧节点，上一个节点就是父节点
						if (now == now->parent->left)
							now = now->parent;
						//如果是右侧节点且没有左侧节点，上一个节点是父节点
						else if (now == now->parent->right && now->parent->left == nullptr)
							now = now->parent;
						//如果是右侧节点且有左侧节点，上一个节点是左侧节点的最底部节点
						else
						{
							now = now->parent->left;
							while (now->left || now->right)
								now = now->right == nullptr ? now->left : now->right;
						}
					}
					//没有父节点，上一个即是最右侧节点
					else
					{
						while (now->right)
							now = now->right;
					}
				}
				//中序遍历
				if constexpr (_Order == 0)
				{
					//如果有左节点，上一个节点就是左节点的最右侧节点
					if (now->left)
					{
						now = now->left;
						while (now->right)
							now = now->right;
					}
					//如果没有左节点，但是有父节点
					else if (now->parent)
					{
						//自己是父节点的右节点，上一个节点就是父节点
						if (now == now->parent->right)
							now = now->parent;
						//自己是父节点的左节点
						else
						{
							//向上探索，直到找到自己属于右节点
							bool left_jump = true;
							do
							{
								if (now == now->parent->right)
								{
									left_jump = false;
									now = now->parent;
									break;
								}
								now = now->parent;
							} while (now->parent);

							//如果是从左边一直跳上来的，且该节点没有父节点，说明已经是头部，需要跳到最右侧节点
							if (left_jump && now->parent == nullptr)
								while (now->right)
									now = now->right;
						}
					}
					//既没有父节点，也没有左节点，上一个节点就是最右侧节点
					else
					{
						while (now->right)
							now = now->right;
					}
				}
				//后序遍历
				if constexpr (_Order == 1)
				{
					//如果有右节点，上一个节点就是右节点
					if (now->right)
						now = now->right;
					//如果没有右节点，但是有左节点，上一个节点就是左节点
					else if (now->left)
						now = now->left;
					//如果没有左右节点，但是有父节点，一直往父节点上跳，直到找到左节点
					else if (now->parent)
					{
						do
						{
							if (now->parent->left != nullptr && now->parent->right == now)
							{
								now = now->parent->left;
								break;
							}
							now = now->parent;
						} while (now->parent);
					}
				}
			}

			/*
			* @brief 使当前节点移动到下一个节点
			*/
			void next()
			{
				//先序遍历
				if constexpr (_Order == -1)
				{
					//如果自己存在左节点
					//往左节点走
					if (now->left)
						now = now->left;
					//否则如果存在右节点
					//往右节点走
					else if (now->right)
						now = now->right;
					//如果没有子节点 但是 有父节点
					else if (now->parent)
					{
						//往上探索，直到父节点存在右节点并且不是自己
						do
						{
							if (now->parent->right != nullptr && now->parent->right != now)
							{
								now = now->parent->right;
								break;
							}
							else
							{
								now = now->parent;
							}
						} while (now->parent);
					}
				}
				//中序遍历
				if constexpr (_Order == 0)
				{
					//如果存在右节点，往右节点走，走到右节点的底部
					if (now->right)
					{
						now = now->right;
						while (now->left)
							now = now->left;
					}
					//如果没有右节点，但是有父节点，并且自己是父节点的左节点，则往父节点走
					else if (now->parent && now == now->parent->left)
						now = now->parent;
					//如果自己是父节点的右节点
					else if (now->parent && now == now->parent->right)
					{
						//往上探索，直到自己是父节点的左节点
						bool right_jump = true;
						do
						{
							if (now->parent->left == now)
							{
								now = now->parent;
								right_jump = false;
								break;
							}
							now = now->parent;
						} while (now->parent);

						//从右侧上去，且没有父节点，说明到头了，回到最左侧节点
						if (right_jump && now->parent == nullptr)
							while (now->left)
								now = now->left;
					}
					//没有右节点也没有父节点，走到最左侧节点
					else
					{
						while (now->left)
							now = now->left;
					}
				}
				//后序遍历
				if constexpr (_Order == 1)
				{
					//如果存在父节点，父节点没有右节点且自己是父节点的左节点，跳到父节点
					if (now->parent && now->parent->right == nullptr && now->parent->left == now)
						now = now->parent;
					//如果存在父节点，且自己是父节点的右节点，跳到父节点
					else if (now->parent && now->parent->right == now)
						now = now->parent;
					//如果存在父节点，父节点有右节点且自己是父节点的左节点，跳到父节点的右节点的最底部
					else if (now->parent && now->parent->right != nullptr && now->parent->left == now)
					{
						now = now->parent->right;
						while (now->left || now->right)
							now = now->left == nullptr ? now->right : now->left;
					}
					//没有父节点，说明已经到终点了，跳回最左侧的最底部
					else
					{
						while (now->left || now->right)
							now = now->left == nullptr ? now->right : now->left;
					}
				}
			}

		public:
			_Iterator(const BinaryTreeNode* root, const BinaryTree* container, bool adjust_place = true)noexcept :container(container)
			{
				now = const_cast<BinaryTreeNode*>(root);
				if (!adjust_place) return;
				//先序遍历
				if constexpr (_Order == -1)
				{
					//无需修改定位
				}
				//中序遍历
				if constexpr (_Order == 0)
				{
					//需要定位至最左侧
					while (now->left)
						now = now->left;
				}
				//后序遍历
				if constexpr (_Order == 1)
				{
					//需要定位至最左侧的最底部
					while (now->left || now->right)
						now = now->left == nullptr ? now->right : now->left;
				}
			}

			/*
			* @breif 转换为通用迭代器
			* @return 通用迭代器
			*/
			operator _Base() const noexcept
			{
				return _Base(now, container);
			}

			/*
			* @breif 转换为通用迭代器
			* @return 通用迭代器
			*/
			_Base generalization() const noexcept
			{
				return _Base(now, container);
			}

			/*
			* @brief 迭代器类指针使用
			* @return 二叉树节点值的指针
			*/
			ValueType* operator->() const
			{
				return const_cast<ValueType*>(&(now->val));
			}

			/*
			* @brief 取出迭代器指向的节点的值
			* @return 二叉树节点值的引用
			*/
			ValueType& operator*() const
			{
				return const_cast<ValueType&>(now->val);
			}

			/*
			* @brief 先取下一个节点，然后返回
			* @return 迭代器自身的引用
			*/
			_Self& operator++()
			{
				this->next();
				return *this;
			}

			/*
			* @brief 先返回，再取下一个节点
			* @return 迭代器
			*/
			_Self operator++(int)
			{
				_Self tmp = *this;
				this->next();
				return tmp;
			}

			/*
			* @brief 先取上一个节点，然后返回
			* @return 迭代器自身的引用
			*/
			_Self& operator--()
			{
				this->last();
				return *this;
			}

			/*
			* @brief 先返回，再取上一个节点
			* @return 迭代器
			*/
			_Self operator--(int)
			{
				_Self tmp = *this;
				this->last();
				return tmp;
			}

			/*
			* @brief 判断两个迭代器是否相等
			* @param 另一迭代器
			* @return 布尔值
			*/
			bool operator==(const _Self& itr) const
			{
				return this->now == itr.now;
			}

			/*
			* @brief 判断两个迭代器是否不相等
			* @param 另一迭代器
			* @return 布尔值
			*/
			bool operator!=(const _Self& itr) const
			{
				return this->now != itr.now;
			}
		};

		//反向迭代器
		template<class _Itr>
		class _Reverse_Iterator
		{
			using _Self = _Reverse_Iterator<_Itr>;
		public:
			using _Base = typename _Itr::_Base;
			using ValueType = typename _Itr::ValueType;

		private:
			_Itr iter;

		public:
			_Reverse_Iterator(const BinaryTreeNode* root, const BinaryTree* container, bool adjust_place = true) noexcept :iter(root, container)
			{
				if (!adjust_place) return;
				--(this->iter);
			}

			/*
			* @breif 转换为通用迭代器
			* @return 通用迭代器
			*/
			operator _Base() const noexcept
			{
				return _Base(iter);
			}

			/*
			* @breif 转换为通用迭代器
			* @return 通用迭代器
			*/
			_Base generalization() const noexcept
			{
				return _Base(iter);
			}

			/*
			* @brief 迭代器类指针使用
			* @return 二叉树节点值的指针
			*/
			ValueType* operator->() const
			{
				return iter.operator->();
			}

			/*
			* @brief 取出迭代器指向的节点的值
			* @return 二叉树节点值的引用
			*/
			ValueType& operator*() const
			{
				return iter.operator*();
			}

			/*
			* @brief 先取下一个节点，然后返回
			* @return 迭代器自身的引用
			*/
			_Self& operator++()
			{
				--iter;
				return *this;
			}

			/*
			* @brief 先返回，再取下一个节点
			* @return 迭代器
			*/
			_Self operator++(int)
			{
				_Self tmp = *this;
				--iter;
				return tmp;
			}

			/*
			* @brief 先取上一个节点，然后返回
			* @return 迭代器自身的引用
			*/
			_Self& operator--()
			{
				++iter;
				return *this;
			}

			/*
			* @brief 先返回，再取上一个节点
			* @return 迭代器
			*/
			_Self operator--(int)
			{
				_Self tmp = *this;
				++iter;
				return tmp;
			}

			/*
			* @brief 判断两个迭代器是否相等
			* @param 另一迭代器
			* @return 布尔值
			*/
			bool operator==(const _Self& itr) const
			{
				return this->iter == itr.iter;
			}

			/*
			* @brief 判断两个迭代器是否不相等
			* @param 另一迭代器
			* @return 布尔值
			*/
			bool operator!=(const _Self& itr) const
			{
				return this->iter != itr.iter;
			}
		};

	public:
		//通用迭代器
		using iterator = _IteratorBase<_Ty>;
		using const_iterator = _IteratorBase<const _Ty>;

		//正向迭代器
		using preorder_iterator = _Iterator<_Ty, -1>;
		using preorder_const_iterator = _Iterator<const _Ty, -1>;
		using inorder_iterator = _Iterator<_Ty, 0>;
		using inorder_const_iterator = _Iterator<const _Ty, 0>;
		using postorder_iterator = _Iterator<_Ty, 1>;
		using postorder_const_iterator = _Iterator<const _Ty, 1>;

		//反向迭代器
		using preorder_reverse_iterator = _Reverse_Iterator<preorder_iterator>;
		using preorder_reverse_const_iterator = _Reverse_Iterator<preorder_const_iterator>;
		using inorder_reverse_iterator = _Reverse_Iterator<inorder_iterator>;
		using inorder_reverse_const_iterator = _Reverse_Iterator<inorder_const_iterator>;
		using postorder_reverse_iterator = _Reverse_Iterator<postorder_iterator>;
		using postorder_reverse_const_iterator = _Reverse_Iterator<postorder_const_iterator>;

	public:
		BinaryTree()
		{
			root = new BinaryTreeNode;
		}

		BinaryTree(const _Ty& val)
		{
			root = new BinaryTreeNode(val);
		}

		~BinaryTree()
		{
			if (root) delete root;
		}

		/*
		* @brief 树的深拷贝
		* @param 被拷贝的树
		*/
		BinaryTree(const _Self& tree)
		{
			this->root = new BinaryTreeNode(tree.root);
		}

		/*
		* @brief 串行初始化树
		* @param 串行参数列表
		* @exception 如果给的串行数据不合法，会抛出 WrongInitializer 异常
		*/
		BinaryTree(std::initializer_list<serial_initializer> ini_list)
		{
			if (ini_list.size() == 0 || ini_list.begin()->isNull()) throw "WrongInitializer";

			//初始化根节点
			root = new BinaryTreeNode(ini_list.begin()->getVal());

			//用于装节点
			BinaryTreeNode** all_nodes = new BinaryTreeNode * [ini_list.size()]{ nullptr };
			BinaryTreeNode** nodes = all_nodes;
			BinaryTreeNode** next_nodes = all_nodes + (ini_list.size() >> 1);
			size_t nodes_size = 0, next_nodes_size = 0;
			//记录当前是写入左节点还是右节点
			bool write_left = true;

			//装入根节点
			nodes[0] = root;
			nodes_size = 1;

			//记录当前的写入位置
			size_t idx = 0;

			for (auto itr = ini_list.begin() + 1; itr != ini_list.end(); ++itr)
			{
				if (!itr->isNull())
				{
					if (write_left)
					{
						nodes[idx]->left = new BinaryTreeNode(itr->getVal());
						nodes[idx]->left->parent = nodes[idx];
						next_nodes[next_nodes_size++] = nodes[idx]->left;
					}
					else
					{
						nodes[idx]->right = new BinaryTreeNode(itr->getVal());
						nodes[idx]->right->parent = nodes[idx];
						next_nodes[next_nodes_size++] = nodes[idx]->right;
					}
				}
				write_left = !write_left;
				if (write_left && ++idx >= nodes_size)
				{
					if (next_nodes_size == 0) break;
					std::swap(nodes, next_nodes);
					std::swap(nodes_size, next_nodes_size);
					idx = 0;
					next_nodes_size = 0;
				}
			}

			//释放堆内存
			delete[] all_nodes;
		}

		/*
		* @brief 获取树的高度（深度）
		* @return 树的高度
		*/
		size_t height() const
		{
			return root->height();
		}

		/*
		* @brief 获取树的节点数
		* @return 树的节点数
		*/
		size_t size() const
		{
			return root->size();
		}

		/*
		* @brief 获取根节点
		* @return 迭代器
		*/
		iterator root_node()
		{
			return iterator(root, this);
		}

		/*
		* @brief 获取根节点
		* @return 迭代器
		*/
		const_iterator root_node() const
		{
			return const_iterator(root, this);
		}

		/*
		* @brief 在节点左侧插入一个节点，如果已经存在左节点则替换值
		* @param 迭代器，决定要进行左插入的节点
		* @param 新插入节点的值
		* @return 新插入节点的迭代器
		* @exception 提供其他树的节点会抛出 WrongIterator 异常
		*/
		iterator insert_left(iterator node, const _Ty& val)
		{
			if (node.container != this) throw "WrongIterator";
			if (node.now->left)
			{
				node.now->left->val = val;
			}
			else
			{
				node.now->left = new BinaryTreeNode(val);
				node.now->left->parent = node.now;
			}
			return node.left();
		}

		/*
		* @brief 在节点右侧插入一个节点，如果已经存在右节点则替换值
		* @param 迭代器，决定要进行右插入的节点
		* @param 新插入节点的值
		* @return 新插入节点的迭代器
		* @exception 提供其他树的节点会抛出 WrongIterator 异常
		*/
		iterator insert_right(iterator node, const _Ty& val)
		{
			if (node.container != this) throw "WrongIterator";
			if (node.now->right)
			{
				node.now->right->val = val;
			}
			else
			{
				node.now->right = new BinaryTreeNode(val);
				node.now->right->parent = node.now;
			}
			return node.right();
		}

		/*
		* @brief 删除一个节点以及该节点往下的子节点
		* @param 迭代器，被删除的节点
		* @return 被删除节点的父节点的迭代器
		* @exception 删除根节点会抛出 CanNotEraseRoot 异常，提供其他树的节点会抛出 WrongIterator 异常
		*/
		iterator erase(iterator node)
		{
			if (node.container != this) throw "WrongIterator";
			if (node.now == root) throw "CanNotEraseRoot";
			iterator parent = node.parent();
			if (parent.now->left == node.now) parent.now->left = nullptr;
			else if (parent.now->right == node.now) parent.now->right = nullptr;
			delete node.now;
			return parent;
		}

		/*
		* @brief 获取先序遍历的迭代器
		* @param 初始节点 - 默认是默认起始节点
		* @return 先序遍历的迭代器
		* @exception 提供其他树的节点会抛出 WrongIterator 异常
		*/
		preorder_iterator preorder(const iterator& itr = iterator(nullptr, nullptr))
		{
			if (itr.now == nullptr) return preorder_iterator(root, this);
			if (itr.container != this) throw "WrongIterator";
			return preorder_iterator(itr.now, this, false);
		}

		/*
		* @brief 获取先序遍历的迭代器
		* @param 初始节点 - 默认是默认起始节点
		* @return 先序遍历的迭代器
		* @exception 提供其他树的节点会抛出 WrongIterator 异常
		*/
		preorder_const_iterator preorder_const(const iterator& itr = iterator(nullptr, nullptr)) const
		{
			if (itr.now == nullptr) return preorder_const_iterator(root, this);
			if (itr.container != this) throw "WrongIterator";
			return preorder_const_iterator(itr.now, this, false);
		}

		/*
		* @brief 获取中序遍历的迭代器
		* @param 初始节点 - 默认是默认起始节点
		* @return 中序遍历的迭代器
		* @exception 提供其他树的节点会抛出 WrongIterator 异常
		*/
		inorder_iterator inorder(const iterator& itr = iterator(nullptr, nullptr))
		{
			if (itr.now == nullptr) return inorder_iterator(root, this);
			if (itr.container != this) throw "WrongIterator";
			return inorder_iterator(itr.now, this, false);
		}

		/*
		* @brief 获取中序遍历的迭代器
		* @param 初始节点 - 默认是默认起始节点
		* @return 中序遍历的迭代器
		* @exception 提供其他树的节点会抛出 WrongIterator 异常
		*/
		inorder_const_iterator inorder_const(const iterator& itr = iterator(nullptr, nullptr)) const
		{
			if (itr.now == nullptr) return inorder_const_iterator(root, this);
			if (itr.container != this) throw "WrongIterator";
			return inorder_const_iterator(itr.now, this, false);
		}

		/*
		* @brief 获取后序遍历的迭代器
		* @param 初始节点 - 默认是默认起始节点
		* @return 后序遍历的迭代器
		* @exception 提供其他树的节点会抛出 WrongIterator 异常
		*/
		postorder_iterator postorder(const iterator& itr = iterator(nullptr, nullptr))
		{
			if (itr.now == nullptr) return postorder_iterator(root, this);
			if (itr.container != this) throw "WrongIterator";
			return postorder_iterator(itr.now, this, false);
		}

		/*
		* @brief 获取后序遍历的迭代器
		* @param 初始节点 - 默认是默认起始节点
		* @return 后序遍历的迭代器
		* @exception 提供其他树的节点会抛出 WrongIterator 异常
		*/
		postorder_const_iterator postorder_const(const iterator& itr = iterator(nullptr, nullptr)) const
		{
			if (itr.now == nullptr) return postorder_const_iterator(root, this);
			if (itr.container != this) throw "WrongIterator";
			return postorder_const_iterator(itr.now, this, false);
		}

		/*
		* @brief 获取先序遍历的反向迭代器
		* @param 初始节点 - 默认是默认起始节点
		* @return 先序遍历的反向迭代器
		* @exception 提供其他树的节点会抛出 WrongIterator 异常
		*/
		preorder_reverse_iterator preorder_reverse(const iterator& itr = iterator(nullptr, nullptr))
		{
			if (itr.now == nullptr) return preorder_reverse_iterator(root, this);
			if (itr.container != this) throw "WrongIterator";
			return preorder_reverse_iterator(itr.now, this, false);
		}

		/*
		* @brief 获取先序遍历的反向迭代器
		* @param 初始节点 - 默认是默认起始节点
		* @return 先序遍历的反向迭代器
		* @exception 提供其他树的节点会抛出 WrongIterator 异常
		*/
		preorder_reverse_const_iterator preorder_reverse_const(const iterator& itr = iterator(nullptr, nullptr)) const
		{
			if (itr.now == nullptr) return preorder_reverse_const_iterator(root, this);
			if (itr.container != this) throw "WrongIterator";
			return preorder_reverse_const_iterator(itr.now, this, false);
		}

		/*
		* @brief 获取中序遍历的反向迭代器
		* @param 初始节点 - 默认是默认起始节点
		* @return 中序遍历的反向迭代器
		* @exception 提供其他树的节点会抛出 WrongIterator 异常
		*/
		inorder_reverse_iterator inorder_reverse(const iterator& itr = iterator(nullptr, nullptr))
		{
			if (itr.now == nullptr) return inorder_reverse_iterator(root, this);
			if (itr.container != this) throw "WrongIterator";
			return inorder_reverse_iterator(itr.now, this, false);
		}

		/*
		* @brief 获取中序遍历的反向迭代器
		* @param 初始节点 - 默认是默认起始节点
		* @return 中序遍历的反向迭代器
		* @exception 提供其他树的节点会抛出 WrongIterator 异常
		*/
		inorder_reverse_const_iterator inorder_reverse_const(const iterator& itr = iterator(nullptr, nullptr)) const
		{
			if (itr.now == nullptr) return inorder_reverse_const_iterator(root, this);
			if (itr.container != this) throw "WrongIterator";
			return inorder_reverse_const_iterator(itr.now, this, false);
		}

		/*
		* @brief 获取后序遍历的反向迭代器
		* @param 初始节点 - 默认是默认起始节点
		* @return 后序遍历的反向迭代器
		* @exception 提供其他树的节点会抛出 WrongIterator 异常
		*/
		postorder_reverse_iterator postorder_reverse(const iterator& itr = iterator(nullptr, nullptr))
		{
			if (itr.now == nullptr) return postorder_reverse_iterator(root, this);
			if (itr.container != this) throw "WrongIterator";
			return postorder_reverse_iterator(itr.now, this, false);
		}

		/*
		* @brief 获取后序遍历的反向迭代器
		* @param 初始节点 - 默认是默认起始节点
		* @return 后序遍历的反向迭代器
		* @exception 提供其他树的节点会抛出 WrongIterator 异常
		*/
		postorder_reverse_const_iterator postorder_reverse_const(const iterator& itr = iterator(nullptr, nullptr)) const
		{
			if (itr.now == nullptr) return postorder_reverse_const_iterator(root, this);
			if (itr.container != this) throw "WrongIterator";
			return postorder_reverse_const_iterator(itr.now, this, false);
		}
	};
}

#endif

测试代码

#include<iostream>
#include "BinaryTree.h"
using namespace std;
using namespace YYYCZ;

int main()
{
	BinaryTree<int> tree{ 1,2,6,3,5,8,7,nullptr,4,nullptr,nullptr,9 };
	BinaryTree<int> tree2{ 1 };

	{
		cout << "先序遍历：" << endl;
		auto itr = tree.preorder();
		do
		{
			cout << *itr << " ";
		} while (++itr != tree.preorder());
		cout << endl;
	}

	{
		cout << "中序遍历：" << endl;
		auto itr = tree.inorder();
		do
		{
			cout << *itr << " ";
		} while (++itr != tree.inorder());
		cout << endl;
	}

	{
		cout << "反向中序遍历：" << endl;
		auto itr = tree.inorder_reverse();
		do
		{
			cout << *itr << " ";
		} while (++itr != tree.inorder_reverse());
		cout << endl;
	}

	{
		cout << "以根节点的左节点为起点的后序遍历：" << endl;
		auto itr = tree.postorder(tree.root_node().left());
		do
		{
			cout << *itr << " ";;
		} while (++itr != tree.postorder());
		cout << endl;
	}

	{
		// 尝试删除不属于自己的迭代器
		try
		{
			tree2.erase(tree.root_node());
		}
		catch (const char* msg)
		{
			cerr << "Error Message: " << msg << endl;
		}
	}

	return 0;
}