树：二叉树的前序/中序/后序/层次递归-创新互联

在二叉树的应用中，很多使用二叉树的操作都是通过遍历来进行节点的修改。

所以对于遍历而言是学习二叉树的要点，今天就来总结一下。

假设二叉树的结构为：

template
struct BinaryTreeNode
{
	BinaryTreeNode(const T& x)
		:_data(x)
		,_left(NULL)
		,_right(NULL)
	{}

	T _data;
	BinaryTreeNode* _left;
	BinaryTreeNode* _right;
};

1. 前序遍历：

void PrevOrder()
{
	_PrevOrder(_root);
	cout<* root)
{
	if (root==NULL)
    	    return;

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

void PrevOrder_Non_R()
{
	stack*> s;
	if (_root)
	s.push(_root);
	while(!s.empty())
	{
		BinaryTreeNode* top = s.top();
		cout<_data<<" ";
		s.pop();

		if (top->_right)
			s.push(top->_right);
			
		if (top->_left)
			s.push(top->_left);
	}

	cout<
2.中序遍历：
	void InOrder()
	{
		_InOrder(_root);
		cout<* root)
	{
		if (root == NULL)
			return;

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

	void InOrder_Non_R()
	{
		stack*> s;
		BinaryTreeNode* cur = _root;

		while (cur || !s.empty())
		{
			// 1.压左节点
			while (cur)
			{
				s.push(cur);
				cur = cur->_left;
			}

			// 取栈顶节点数据访问
			// 前序遍历top节点的右树
			if (!s.empty())
			{
				BinaryTreeNode* top = s.top();
				s.pop();
				cout<_data<<" ";

				cur = top->_right;
			}
		}

		cout<
3.后序遍历：
       	void PostOrder()
	{
		_PostOrder(_root);
		cout<* root)
	{
		if (root == NULL)
			return;

		_PostOrder(root->_left);
		_PostOrder(root->_right);
		cout<_data<<" ";
	}
	
	void PostOrder_Non_R()
	{
		stack*> s;
		BinaryTreeNode* cur = _root;
		BinaryTreeNode* prevVisited = NULL;

		while (cur || !s.empty())
		{
			// 1.压左节点
			while (cur)
			{
				s.push(cur);
				cur = cur->_left;
			}

			BinaryTreeNode* top = s.top();
			if (top->_right == NULL 
				|| top->_right == prevVisited)
			{
				cout<_data<<" ";
				s.pop();
				prevVisited = top;
			}
			else
			{
				cur = top->_right;
			}
		}

		cout<
4.层次遍历
	void LevelOrder()
	{
		queue* > q;
		if (_root)
			q.push(_root);

		while(!q.empty())
		{
			BinaryTreeNode* front = q.front();
			cout<_data<<" ";
			q.pop();

			if (front->_left)
				q.push(front->_left);

			if (front->_right)
				q.push(front->_right);

		}

		cout<
以上
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
            

            本文标题：树：二叉树的前序/中序/后序/层次递归-创新互联            

            当前链接：http://cxhlcq.com/article/diepji.html