題目描述： 二叉樹，按層打印，并且每層換行

成都創(chuàng)新互聯(lián)公司專注于光澤企業(yè)網(wǎng)站建設(shè),自適應(yīng)網(wǎng)站建設(shè),商城網(wǎng)站建設(shè)。光澤網(wǎng)站建設(shè)公司,為光澤等地區(qū)提供建站服務(wù)。全流程按需定制開發(fā)，專業(yè)設(shè)計(jì)，全程項(xiàng)目跟蹤，成都創(chuàng)新互聯(lián)公司專業(yè)和態(tài)度為您提供的服務(wù)

分析： 我們知道，二叉樹的層序遍歷需要借助隊(duì)列來實(shí)現(xiàn)，每取出一個(gè)節(jié)點(diǎn)打印，并將該節(jié)點(diǎn)的左右孩子放入隊(duì)列中，依此反復(fù)，直到隊(duì)列為空時(shí)，也就完成了二叉樹的按層打印。

基本過程如圖所示：

但是，關(guān)鍵是怎么換行？

分析：要換行則需要知道什么時(shí)候換行，由二叉樹我們可以分析，我們需要知道每一層最右邊的節(jié)點(diǎn)，每次打印完這個(gè)節(jié)點(diǎn)的值后，再打印一個(gè)換行即可。于是我們這樣做：

定義兩個(gè)變量，last 和 nlast

last : 表示正在打印的當(dāng)前行的最右節(jié)點(diǎn)

nlast : 表示下一行的最右節(jié)點(diǎn)

步驟：

1. 開始讓 last 等于二叉樹的根節(jié)點(diǎn)，并將其點(diǎn)放入隊(duì)列中。

2. 隊(duì)頭節(jié)點(diǎn)出隊(duì)列，并打印，將該節(jié)點(diǎn)的左孩子入隊(duì)，并讓 nlast 等于該節(jié)點(diǎn)，將該節(jié)點(diǎn)的右孩子入隊(duì)，并讓 nlast 等于該節(jié)點(diǎn)。

3. 如果打印的節(jié)點(diǎn)等于 last 當(dāng)前指向的節(jié)點(diǎn)，則打印一次換行，同時(shí)讓 last 等于 nlast。

4. 重復(fù)步驟2,3，知道隊(duì)列為空為止。

圖示過程如下：

先將 1 入隊(duì)

再將 1 出隊(duì)，并將 2 ，3 入隊(duì)，并讓 nlast 分別指向 2， 3

此時(shí)發(fā)現(xiàn)，出隊(duì)列的節(jié)點(diǎn)與 last 指向的節(jié)點(diǎn)相等，此時(shí)，打印換行符。同時(shí)讓 last 等于 nlast

重復(fù)上述步驟，將 2 出隊(duì)列，并將 4 入隊(duì)列，讓 nlast 指向 4

再將 3 出隊(duì)列，并將 5,6 入隊(duì)列，讓 nlast 分別指向 5,6 ，此時(shí)發(fā)現(xiàn)3 等于 last ，則再打印一次換行，并讓 last 等于 nlast

重復(fù)上述步驟，最終結(jié)果如下：

這樣，按層換行打印二叉樹就完成啦！

代碼如下：

#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) 
	                                                            //創(chuàng)建二叉樹
	{
		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;

		//后序遍歷刪除結(jié)點(diǎn)
		_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();
}

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

網(wǎng)站題目：按層換行打印二叉樹-創(chuàng)新互聯(lián)
URL分享：http://weahome.cn/article/dhecje.html