网创优客建站品牌官网
为成都网站建设公司企业提供高品质网站建设
热线:028-86922220
成都专业网站建设公司

定制建站费用3500元

符合中小企业对网站设计、功能常规化式的企业展示型网站建设

成都品牌网站建设

品牌网站建设费用6000元

本套餐主要针对企业品牌型网站、中高端设计、前端互动体验...

成都商城网站建设

商城网站建设费用8000元

商城网站建设因基本功能的需求不同费用上面也有很大的差别...

成都微信网站建设

手机微信网站建站3000元

手机微信网站开发、微信官网、微信商城网站...

建站知识

当前位置:首页 > 建站知识

按层换行打印二叉树-创新互联

题目描述: 二叉树,按层打印,并且每层换行

成都创新互联公司专注于光泽企业网站建设,自适应网站建设,商城网站建设。光泽网站建设公司,为光泽等地区提供建站服务。全流程按需定制开发,专业设计,全程项目跟踪,成都创新互联公司专业和态度为您提供的服务

分析: 我们知道,二叉树的层序遍历需要借助队列来实现,每取出一个节点打印,并将该节点的左右孩子放入队列中,依此反复,直到队列为空时,也就完成了二叉树的按层打印。

基本过程如图所示:

按层换行打印二叉树

但是,关键是怎么换行?

分析:要换行则需要知道什么时候换行,由二叉树我们可以分析,我们需要知道每一层最右边的节点,每次打印完这个节点的值后,再打印一个换行即可。于是我们这样做:

定义两个变量,last 和 nlast

last : 表示正在打印的当前行的最右节点

nlast : 表示下一行的最右节点

步骤:

  1. 开始让 last 等于二叉树的根节点,并将其点放入队列中。

  2. 队头节点出队列,并打印,将该节点的左孩子入队,并让 nlast 等于该节点,将该节点的右孩子入队,并让 nlast 等于该节点。

  3. 如果打印的节点等于 last 当前指向的节点,则打印一次换行,同时让 last 等于 nlast。

  4. 重复步骤2,3,知道队列为空为止。

图示过程如下:

先将 1 入队

按层换行打印二叉树

再将 1 出队,并将 2 ,3 入队,并让 nlast 分别指向 2, 3

按层换行打印二叉树

此时发现,出队列的节点与 last 指向的节点相等,此时,打印换行符。同时让 last 等于 nlast

重复上述步骤,将 2 出队列,并将 4 入队列,让 nlast 指向 4

按层换行打印二叉树

再将 3 出队列,并将 5,6 入队列,让 nlast 分别指向 5,6 ,此时发现3 等于 last ,则再打印一次换行,并让 last 等于 nlast

按层换行打印二叉树

重复上述步骤,最终结果如下:

按层换行打印二叉树

这样,按层换行打印二叉树就完成啦!


代码如下:

#pragma once
#include
#include
#include
using namespace std;

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

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

template
class BinaryTree
{
public:
	BinaryTree()
		:_root(NULL)
	{}

	BinaryTree(const T* a, size_t size)
	{
		size_t index = 0;
		_root = _CreateTree(a, size, index);
	}

	~BinaryTree()
	{
		_DestroyTree(_root);
		_root = NULL;
	}

	void LevelOrder()  //层次遍历
	{
		_LevelOrder(_root);  //每层换行!
	}


protected:
	BinaryTreeNode* _CreateTree(const T*& a, size_t size, size_t& index) 
	                                                            //创建二叉树
	{
		assert(a);
		BinaryTreeNode* NewNode = NULL;
		if (index < size && '#' != a[index])
		{
			NewNode = new BinaryTreeNode(a[index]);
			NewNode->_left = _CreateTree(a, size, ++index);
			NewNode->_right = _CreateTree(a, size, ++index);
		}
		return NewNode;
	}

	void _DestroyTree(BinaryTreeNode*& root)  //销毁二叉树
	{
		if (NULL == root)
			return;

		//后序遍历删除结点
		_DestroyTree(root->_left);
		_DestroyTree(root->_right);
		delete root;
		root = NULL;
	}

	void _LevelOrder(BinaryTreeNode*& root)
	{
		if (NULL == root)
			return;

		std::queue*> q;
		q.push(root);

		BinaryTreeNode* last = root;
		BinaryTreeNode* nlast = NULL;
		while (!q.empty())
		{
			BinaryTreeNode* cur = q.front();
			cout << cur->_data << " ";
			q.pop();

			if (cur->_left)
			{
				q.push(cur->_left);
				nlast = cur->_left;
			}

			if (cur->_right)
			{
				q.push(cur->_right);
				nlast = cur->_right;
			}

			if (cur == last)
			{
				cout << endl;
				last = nlast;
			}
		}
		cout << endl;
	}

	
protected:
	BinaryTreeNode* _root;
};


void Test1()
{
	int array[] = { 1, 2, 4, '#', '#', '#', 3, 5, 7, '#', '#', 8, '#', '#', 6 };
	BinaryTree t1(array, sizeof(array)/sizeof(int));

	t1.LevelOrder();
}

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


本文标题:按层换行打印二叉树-创新互联
网站链接:http://bjjierui.cn/article/dhecje.html

其他资讯