[C++]红黑树

一、概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或
Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路
径会比其他路径长出俩倍，因而是接近平衡的。

性质：

  • 每个结点不是红色就是黑色
  • 根节点是黑色的
  • 如果一个节点是红色的，则它的两个孩子结点是黑色的
  • 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点
  • 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

二、红黑树的结点定义

enum Colour
{
	RED,
	BLACK
};

template<class T>
struct RBTreeNode
{
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;

	T _data;
	Colour _col;

	RBTreeNode(T data = T())
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_data(data)
		,_col(RED)
};

二、红黑树的插入

1、插入结点

		Node* root = GetRoot();
		if (root == nullptr)
		{
			root = new Node(data);
			root->_parent = _head;
			_head->_parent = root;

			return true;
		}

		Node* cur = root;
		Node* parent = root;
		//找到data节点插入的位置
		while (cur)
		{
			if (data < cur->_data)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (data > cur->_data)
			{
				parent = cur;
				cur = cur->_right;
			}
		}
		//插入data节点
		cur = new Node(data);
		if (data < parent->_data)
		{
			cur->_parent = parent;
			parent->_left = cur;
		}
		else
		{
			cur->_parent = parent;
			parent->_right = cur;
		}

若插入结点的父亲为黑色，则结束。

若插入结点的父亲为红色，则出现了连续的红色结点，违反规则，需要处理。 

2、调整

如插入结点后，该树违反了红黑树的规则，则对其进行调整。

（1）cur红，parent红，gparent黑，uncle存在且红

可以看出，该结点插入后，违反了规则： 如果一个节点是红色的，则它的两个孩子结点是黑色的。

此时，需要对其进行变色：将parent、uncle改为黑，gparent改为红，然后将gparent赋值给cur，若此时cur的父结点为红，则继续向上调整。

（2）cur红，parent红，gparent黑，uncle不存在

 此时cur一定是新插入的结点。否则不符合红黑树的规则：不能出现连在一起的红色结点。调整后：

 

（3）cur红，parent红，gparent黑，uncle存在且为黑

（1）基础情况 

此时cur一定不是新增结点，cur一定是由黑色变为红色的，否则就违反了红黑树的规则：每条路径黑色结点相同。

cur变红前的一种可能情况：

注：c：包含一个黑色结点的红黑树 （4种）

d/e：null或一个红色结点（4种）

调整后（旋转＋变色）：

我们将parent变为黑色，而非将cur变为黑色（即parent为红，cur和gparent为黑），是因为如果parent为红，那么当parent不是根结点的时候，仍需向上处理，即parent为红非终结态。

（2）单旋后转变为基础情况

对于这种情况，我们需要做以下处理：

若parent为gparent的左孩子，cur为parent的右孩子，则针对parent做左单旋转；
若parent为gparent的右孩子，cur为parent的左孩子，则针对parent做右单旋转。

旋转完成后，即转变为基础情况：

3、插入完整代码

	bool Insert(const T& data)
	{
		Node* root = GetRoot();
		if (root == nullptr)
		{
			root = new Node(data);
			root->_parent = _head;
			_head->_left = root;
			_head->_right = root;
			_head->_parent = root;
			root->_col = BLACK;
			return true;
		}

		Node* cur = root;
		Node* parent = root;
		//找到data节点插入的位置
		while (cur)
		{
			if (data < cur->_data)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (data > cur->_data)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
			}
		}
		//插入data节点
		cur = new Node(data);
		if (data < parent->_data)
		{
			cur->_parent = parent;
			parent->_left = cur;
		}
		else
		{
			cur->_parent = parent;
			parent->_right = cur;
		}

		//更新_head结点链接关系
		T min = _head->_left->_data;
		T max = _head->_right->_data;
		if (data < min)
		{
			_head->_left = cur;
		}
		if (data > max)
		{
			_head->_right = cur;
		}

		//调整
		while (parent && parent->_col == RED)
		{
			Node* gparent = parent->_parent;
			

			if (parent == gparent->_left)
			{
				Node* uncle = gparent->_right;

				//cur红，parent红，gparent黑，uncle存在且红
				if (uncle && uncle->_col == RED)
				{
					//调整颜色
					parent->_col = uncle->_col = BLACK;
					gparent->_col = RED;

					//继续向上处理
					cur = gparent;
					parent = cur->_parent;
				}
				else if(uncle == nullptr)
				{
					//cur红，parent红，gparent黑，uncle不存在
					if (cur == parent->_left)
					{
						//右旋
						RotateR(gparent);
						//变色
						parent->_col = BLACK;
						gparent->_col = RED;
					}
					else
					{
						RotateL(parent);
						RotateR(gparent);

						//变色
						cur->_col = BLACK;
						parent->_col = gparent->_col = RED;
					}

				

				}
				else if (uncle && uncle->_col == BLACK)
				{
					//cur红，parent红，gparent黑，uncle存在且为黑
					if (cur == parent->_left)
					{
						RotateR(gparent);
						//变色
						parent->_col = BLACK;
						gparent->_col = RED;
					}
					else
					{
						//对parent左单旋后转变为上面的情况
						RotateL(parent);

						RotateR(gparent);

						//变色
						cur->_col = BLACK;
						gparent->_col = RED;
					}
				}
			}
			else if(parent = gparent->_right)
			{
				Node* uncle = gparent->_left;

				//cur红，parent红，gparent黑，uncle存在且红
				if (uncle && uncle->_col == RED)
				{
					//调整颜色
					parent->_col = uncle->_col = BLACK;
					gparent->_col = RED;

					//继续向上处理
					cur = gparent;
					parent = cur->_parent;
				}
				else if (uncle == nullptr)
				{
					//cur红，parent红，gparent黑，uncle不存在
					if (cur == parent->_right)
					{
						//左旋
						RotateL(gparent);
						//变色
						parent->_col = BLACK;
						gparent->_col = RED;
					}
					else
					{
						RotateR(parent);
						RotateL(gparent);

						//变色
						cur->_col = BLACK;
						parent->_col = gparent->_col = RED;

					}



				}
				else if (uncle && uncle->_col == BLACK)
				{
					//cur红，parent红，gparent黑，uncle存在且为黑
					if (cur == parent->_right)
					{
						RotateL(gparent);
						//变色
						parent->_col = BLACK;
						gparent->_col = RED;
					}
					else
					{
						//对parent右单旋后转变为上面的情况
						RotateR(parent);

						RotateL(gparent);

						//变色
						cur->_col = BLACK;
						gparent->_col = RED;
					}
				}
			}

		}


		
		_head->_parent->_col = BLACK;
		return true;
	}

三、验证是否为红黑树

验证是否为红黑树，则需要根据红黑树的规则来确定：

没有两个连续的红色结点；

每条路径包含相同的黑色结点。

	bool IsValidRBTRee()
	{
		Node* root = GetRoot();
		if (root->_col == RED)
		{
			return false;
		}

		if (root == nullptr)
		{
			return true;
		}

		int blackc = GetBlackCount(GetRoot());
		int blacknum = 0;

		_IsValidRBTRee(GetRoot(), blackc, blacknum);
	}

	bool _IsValidRBTRee(Node* root, size_t blackCount, size_t pathBlack)
	{
		if (root == nullptr)
		{
			pathBlack++;
			if (pathBlack != blackCount)
			{
				cout << "各路径黑色结点数量不同" << endl;
				return false;
			}

			return true;
		}

		if (root->_col == RED && root->_parent->_col == RED)
		{
			return false;
		}

		if (root->_col == BLACK)
		{
			pathBlack++;
		}

		return _IsValidRBTRee(root->_left, blackCount, pathBlack)
		&& _IsValidRBTRee(root->_right, blackCount, pathBlack);

	}

四、完整代码

enum Colour
{
	RED,
	BLACK
};

template<class T>
struct RBTreeNode
{
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;

	T _data;
	Colour _col;

	RBTreeNode(T data = T())
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_data(data)
		,_col(RED)
	{}
};


// 请模拟实现红黑树的插入--注意：为了后序封装map和set，本文在实现时给红黑树多增加了一个头结点
template<class T>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	RBTree()
	{
		_head = new Node;
		_head->_left = _head;
		_head->_right = _head;
		_head->_parent = _head;
	}


	// 在红黑树中插入值为data的节点，插入成功返回true，否则返回false
	// 注意：为了简单起见，本次实现红黑树不存储重复性元素
	bool Insert(const T& data)
	{
		Node* root = GetRoot();
		if (root == nullptr)
		{
			root = new Node(data);
			root->_parent = _head;
			_head->_left = root;
			_head->_right = root;
			_head->_parent = root;
			root->_col = BLACK;
			return true;
		}

		Node* cur = root;
		Node* parent = root;
		//找到data节点插入的位置
		while (cur)
		{
			if (data < cur->_data)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (data > cur->_data)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
			}
		}
		//插入data节点
		cur = new Node(data);
		if (data < parent->_data)
		{
			cur->_parent = parent;
			parent->_left = cur;
		}
		else
		{
			cur->_parent = parent;
			parent->_right = cur;
		}

		//更新_head结点链接关系
		T min = _head->_left->_data;
		T max = _head->_right->_data;
		if (data < min)
		{
			_head->_left = cur;
		}
		if (data > max)
		{
			_head->_right = cur;
		}

		//调整
		while (parent && parent->_col == RED)
		{
			Node* gparent = parent->_parent;
			

			if (parent == gparent->_left)
			{
				Node* uncle = gparent->_right;

				//cur红，parent红，gparent黑，uncle存在且红
				if (uncle && uncle->_col == RED)
				{
					//调整颜色
					parent->_col = uncle->_col = BLACK;
					gparent->_col = RED;

					//继续向上处理
					cur = gparent;
					parent = cur->_parent;
				}
				else if(uncle == nullptr)
				{
					//cur红，parent红，gparent黑，uncle不存在
					if (cur == parent->_left)
					{
						//右旋
						RotateR(gparent);
						//变色
						parent->_col = BLACK;
						gparent->_col = RED;
					}
					else
					{
						RotateL(parent);
						RotateR(gparent);

						//变色
						cur->_col = BLACK;
						parent->_col = gparent->_col = RED;
					}

				

				}
				else if (uncle && uncle->_col == BLACK)
				{
					//cur红，parent红，gparent黑，uncle存在且为黑
					if (cur == parent->_left)
					{
						RotateR(gparent);
						//变色
						parent->_col = BLACK;
						gparent->_col = RED;
					}
					else
					{
						//对parent左单旋后转变为上面的情况
						RotateL(parent);

						RotateR(gparent);

						//变色
						cur->_col = BLACK;
						gparent->_col = RED;
					}
				}
			}
			else if(parent = gparent->_right)
			{
				Node* uncle = gparent->_left;

				//cur红，parent红，gparent黑，uncle存在且红
				if (uncle && uncle->_col == RED)
				{
					//调整颜色
					parent->_col = uncle->_col = BLACK;
					gparent->_col = RED;

					//继续向上处理
					cur = gparent;
					parent = cur->_parent;
				}
				else if (uncle == nullptr)
				{
					//cur红，parent红，gparent黑，uncle不存在
					if (cur == parent->_right)
					{
						//左旋
						RotateL(gparent);
						//变色
						parent->_col = BLACK;
						gparent->_col = RED;
					}
					else
					{
						RotateR(parent);
						RotateL(gparent);

						//变色
						cur->_col = BLACK;
						parent->_col = gparent->_col = RED;

					}



				}
				else if (uncle && uncle->_col == BLACK)
				{
					//cur红，parent红，gparent黑，uncle存在且为黑
					if (cur == parent->_right)
					{
						RotateL(gparent);
						//变色
						parent->_col = BLACK;
						gparent->_col = RED;
					}
					else
					{
						//对parent右单旋后转变为上面的情况
						RotateR(parent);

						RotateL(gparent);

						//变色
						cur->_col = BLACK;
						gparent->_col = RED;
					}
				}
			}

		}


		
		_head->_parent->_col = BLACK;
		return true;
	}

	// 检测红黑树中是否存在值为data的节点，存在返回该节点的地址，否则返回nullptr
	Node* Find(const T& data)
	{
		Node* cur = GetRoot();
		Node* parent = cur;

		while (cur)
		{
			if (data > cur->_data)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (data < cur->_data)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}

		return nullptr;
	}

	// 获取红黑树最左侧节点
	Node* LeftMost()
	{
		return _head->_left;
	}

	// 获取红黑树最右侧节点
	Node* RightMost()
	{
		return _head->_right;
	}

	// 检测红黑树是否为有效的红黑树，注意：其内部主要依靠_IsValidRBTRee函数检测
	bool IsValidRBTRee()
	{
		Node* root = GetRoot();
		if (root->_col == RED)
		{
			return false;
		}

		if (root == nullptr)
		{
			return true;
		}

		int blackc = GetBlackCount(GetRoot());
		int blacknum = 0;

		_IsValidRBTRee(GetRoot(), blackc, blacknum);
	}

	void InOrder()
	{
		_InOrder(GetRoot());
	}
private:
	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		_InOrder(root->_left);
		cout << root->_data << " ";
		_InOrder(root->_right);
	}

	size_t GetBlackCount(Node* root)
	{
		size_t ret = 0;
		Node* cur = root;
		while (cur)
		{
			if (cur->_col == BLACK)
			{
				ret++;
			}
			cur = cur->_left;
		}
		ret++;

		return ret;
	}

	bool _IsValidRBTRee(Node* root, size_t blackCount, size_t pathBlack)
	{
		if (root == nullptr)
		{
			pathBlack++;
			if (pathBlack != blackCount)
			{
				cout << "各路径黑色结点数量不同" << endl;
				return false;
			}

			return true;
		}

		if (root->_col == RED && root->_parent->_col == RED)
		{
			return false;
		}

		if (root->_col == BLACK)
		{
			pathBlack++;
		}

		return _IsValidRBTRee(root->_left, blackCount, pathBlack)
		&& _IsValidRBTRee(root->_right, blackCount, pathBlack);

	}


	// 右单旋
	void RotateR(Node* parent)
	{
		Node* pprent = parent->_parent;
		Node* pl = parent->_left;
		Node* PRL = pl->_right;
		Node* PR = parent;

		//更新与上一节点的链接关系
		if (parent == GetRoot())
		{
			_head->_parent = pl;
			pl->_parent = nullptr;
		}
		else
		{
			if (pprent->_left == parent)
			{
				pprent->_left = pl;
			}
			else
			{
				pprent->_right = pl;
			}

			pl->_parent = pprent;
		}


		pl->_right = PR;
		PR->_parent = pl;
		PR->_left = PRL;
		if (PRL)
			PRL->_parent = PR;

	}

	// 左单旋
	void RotateL(Node* parent)
	{
		Node* pprent = parent->_parent;
		Node* pr = parent->_right;
		Node* PLR = pr->_left;
		Node* PL = parent;

		//更新与上一节点的链接关系
		if (parent == GetRoot())
		{
			_head->_parent = pr;
			pr->_parent = nullptr;
		}
		else
		{
			if (pprent->_left == parent)
			{
				pprent->_left = pr;
			}
			else
			{
				pprent->_right = pr;
			}

			pr->_parent = pprent;

		}


		pr->_left = PL;
		PL->_parent = pr;
		PL->_right = PLR;
		if (PLR)
			PLR->_parent = PL;

	}
	// 为了操作树简单起见：获取根节点
	Node* GetRoot()
	{
		if (_head->_parent == _head)
		{
			return nullptr;
		}
		else
		{
			return _head->_parent;
		}
	}
private:
	Node* _head;
};

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【vscode篇】1-VScode设置语言为中文，2-解决中文注释乱码问题。

【vscode篇】1-VScode设置语言为中文，2-解决中文注释乱码问题。

设置语言为中文 在前端开发中&#xff0c;Visual Studio Code(简称vscode)是一个非常好用的工具&#xff0c;但第一次打开vscode会发现界面为英文&#xff0c;这对很多开发者来说会很不友好&#xff08;比如我&#xff09;&#xff0c;把界面设置成中文只需要安装一个插件即可&…
阅读更多...
【stm32/CubeMX、HAL库】嵌入式实验六：定时器(1)|定时器中断

【stm32/CubeMX、HAL库】嵌入式实验六：定时器(1)|定时器中断

参考&#xff1a; 【【正点原子】手把手教你学STM32CubeIDE开发】 https://www.bilibili.com/video/BV1Wp42127Cx/?p13&share_sourcecopy_web&vd_source9332b8fc5ea8d349a54c3989f6189fd3 《嵌入式系统基础与实践》刘黎明等编著&#xff0c;第九章定时器。 实验内容…
阅读更多...
7777777777777

7777777777777

欢迎关注博主 Mindtechnist 或加入【智能科技社区】一起学习和分享Linux、C、C、Python、Matlab&#xff0c;机器人运动控制、多机器人协作&#xff0c;智能优化算法&#xff0c;贝叶斯滤波与Kalman估计、多传感器信息融合&#xff0c;机器学习&#xff0c;人工智能&#xff0c…
阅读更多...
python-合并排列数组 I

python-合并排列数组 I

问题描述&#xff1a;合并两个按升序排列的整数数组a和b&#xff0c;形成一个新数组&#xff0c;新数组也要按升序排列。 问题示例&#xff1a;输入A[1],B[1],输出[1,1],返回合并后的数组。输入A[1,2,3,4],B[2,4,5,6],输出[1,2,2,3,4,4,5,6],返回合并所有元素后的数组。 完整代…
阅读更多...
一个交易者的自白：念念不忘的交易，10个日内9个亏

一个交易者的自白：念念不忘的交易，10个日内9个亏

一、新手: 面对爆仓,我像个白痴 我是在2012年开始接触的&#xff0c;这些年里我尝到了残酷失败的滋味&#xff0c;更品尝过胜利带来的喜悦。刚刚接触时很自信&#xff0c;总想着自己有一天一定会变成千万富翁的&#xff0c;用杠杆获取暴利。 在我首次爆仓的时候&#xff0c;我的…
阅读更多...
前端Vue自定义轮播图组件的设计与实现

前端Vue自定义轮播图组件的设计与实现

摘要 随着技术的发展&#xff0c;前端开发的复杂性日益增加。传统的整块应用开发方式在面对频繁的功能更新和修改时&#xff0c;往往导致整体逻辑的变动&#xff0c;从而增加了开发和维护的难度。为了应对这一挑战&#xff0c;组件化开发应运而生。本文将以Vue中的自定义轮播图…
阅读更多...
01 Nginx安装部署（系列篇）

01 Nginx安装部署（系列篇）

一、安装部署 1、Nginx的发行版本 常用版本分为四大阵营&#xff1a; Nginx 开源版 | https://nginx.org/&#xff1a;赤裸裸的Web服务器、反向代理、负载均衡&#xff08;功能少&#xff0c;开发难度大&#xff09; Nginx Plus 商业版 | https://www.nginx.com/&#xff1a;…
阅读更多...
用易查分制作研学活动报名，支持在线签名，一键导出报名统计表格！

用易查分制作研学活动报名，支持在线签名，一键导出报名统计表格！

学校组织研学活动时&#xff0c;需要家长扫码在线填写报名信息&#xff0c;确认安全承诺和手写签名&#xff0c;提交报名后希望分配报名号&#xff0c;应该如何实现&#xff1f; 易查分的新建填表功能就可以实现上述需求&#xff0c;下面就来教大家如何制作吧。 &#x1f4cc;使…
阅读更多...
Django框架前后端通信打通实战(PyCharm高级版)

Django框架前后端通信打通实战(PyCharm高级版)

1.创建django项目并做好相关配置 首先在pycharm高级版中创建django项目 (1)选择左上角的四条小横线,然后找到文件下面的新建项目并点击,如下图: (2)点击完上图的新建项目之后,来到下面的页面. 然后点击左上角的Django,然后设置文件的位置,之后将模版文件夹的template这个单词…
阅读更多...
网络智能化的发展对仿真环境的需求

网络智能化的发展对仿真环境的需求

1. 网络智能化背景介绍 1.1 什么是网络智能化 网络智能化是指利用人工智能&#xff08;AI&#xff09;、机器学习&#xff08;ML&#xff09;、优化算法等技术来实现网络的信息化、自动化和智能化。相对5G、6G、算力网络等领域&#xff0c;网络智能化是针对网络全场景、全要素…
阅读更多...
通过花生壳对git服务器做内网穿透

通过花生壳对git服务器做内网穿透

很长一段时间内公司的git服务器只能够在公司内网访问&#xff0c;最近出差的同事比较多&#xff0c;通过外网访问git服务器的需求也迫在眉睫&#xff0c;于是选择了贝锐“花生壳”做内网穿透处理。 首先去贝锐官网购买花生壳映射&#xff0c;我选择的是个人标准版本&#xff0c…
阅读更多...
AI绘画Stable Diffusion XL 可商用模型！写实艺术时尚摄影级真实感大模型推荐（附模型下载）

AI绘画Stable Diffusion XL 可商用模型！写实艺术时尚摄影级真实感大模型推荐（附模型下载）

大家好&#xff0c;我是设计师阿威 大家在使用AI绘画的时候&#xff0c;是不是遇到这种问题&#xff1a;收藏的模型确实很多&#xff0c;可商用的没几个&#xff0c;而今天阿威将给大家带来的这款写实艺术时尚摄影级真实感大模型-墨幽人造人XL&#xff0c; 对于个人来讲完全是…
阅读更多...
命运方舟 失落的方舟台服下载教程+账号注册教程(图文全攻略)

命运方舟 失落的方舟台服下载教程+账号注册教程(图文全攻略)

命运方舟 失落的方舟台服下载教程账号注册教程(图文全攻略) 失落的方舟&#xff0c;作为今年一款备受瞩目的MMORPG类型游戏&#xff0c;在官宣的时候就收获了一波不小的热度。这款游戏由游戏开发商Smile gate开发&#xff0c;游戏本体搭建于知名的虚幻引擎之上&#xff0c;为玩…
阅读更多...
【网络原理】HTTPS详解

【网络原理】HTTPS详解

一.HTTPS的相关基本概念 HTTPS:由于HTTP协议内容都是按照文本的方式明文传输的. 这就导致在传输过程中出现一些被篡改的情况. 可能会出现运营商劫持,黑客入侵等不利影响, 因此就引入了HTTPS,其本质上就是在HTTP协议的基础上,引入了一个加密层SSM.什么是运营商劫持? 例如我们要…
阅读更多...
最新！！2024上半年软考【高级】系统分析师 综合知识真题解析

最新！！2024上半年软考【高级】系统分析师 综合知识真题解析

2024上半年软考考试已经结束了&#xff0c;为大家整理了网友回忆版的系统分析师选择题真题及答案&#xff0c;总共30道题。 上半年考试的宝子们可以对答案预估分数&#xff01;准备下半年考的宝子可以提前把握考试知识点和出题方向&#xff0c;说不定会遇到相同考点的题目&…
阅读更多...
2024.5.20 学习记录

2024.5.20 学习记录

1、react 原理&#xff08;jsx的本质、事件机制原理、setState和batch Update、组件渲染更新和diff算法、fiber&#xff09; 2、代码随想录贪心刷题
阅读更多...
使用递归形式以及迭代形式实现树的前中后序遍历

使用递归形式以及迭代形式实现树的前中后序遍历

相信大家对于二叉树的遍历并不陌生&#xff0c;对于二叉树的递归遍历我们也可以信手拈来。但是如果让我们将二叉树修改成为非递归的形式呢&#xff1f;是不是有点疑惑了&#xff1f;那么本次博客我们就来梳理一下二叉树的非递归遍历。 由于递归遍历二叉树的代码以及逻辑都很简单…
阅读更多...
Android Context 详解

Android Context 详解

一、什么是Context&#xff1f; Context是一个抽象基类。在翻译为上下文&#xff0c;是提供一些程序的运行环境基础信息。 Context下有两个子类&#xff0c;ContextWrapper是上下文功能的封装类&#xff08;起到方法传递的作用&#xff0c;主要实现还是ContextImpl&#xff0…
阅读更多...
操作系统实验三 可变分区内存分配首次适应算法模拟

操作系统实验三 可变分区内存分配首次适应算法模拟

实验三 可变分区内存分配首次适应算法模拟 实验内容 模拟内存分配&#xff0c;了解并掌握动态分区分配中所用的数据结构、分区分配算法&#xff0c;深刻理解首次适应内存分配算法。 模拟实现可变分区内存分配首次适应算法&#xff1b;空闲分区表要求有空闲块的起始地址、大小…
阅读更多...
6.2 Go 切片（Slice）

6.2 Go 切片（Slice）

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:「stormsha的主页」…
阅读更多...
最新文章

Copyright @ 2022~2023