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

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

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

基本過程如圖所示：

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

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

定義兩個變量，last 和 nlast

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

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

步驟：

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

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

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

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

圖示過程如下：

先將 1 入隊

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

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

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

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

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

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

代碼如下：

#pragma once
#include<iostream>
#include<cassert>
#include<queue>
using namespace std;

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

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

template<class T>
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<T>* _CreateTree(const T*& a, size_t size, size_t& index) 
	                                                            //創(chuàng)建二叉樹
	{
		assert(a);
		BinaryTreeNode<T>* NewNode = NULL;
		if (index < size && '#' != a[index])
		{
			NewNode = new BinaryTreeNode<T>(a[index]);
			NewNode->_left = _CreateTree(a, size, ++index);
			NewNode->_right = _CreateTree(a, size, ++index);
		}
		return NewNode;
	}

	void _DestroyTree(BinaryTreeNode<T>*& root)  //銷毀二叉樹
	{
		if (NULL == root)
			return;

		//后序遍歷刪除結(jié)點
		_DestroyTree(root->_left);
		_DestroyTree(root->_right);
		delete root;
		root = NULL;
	}

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

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

		BinaryTreeNode<T>* last = root;
		BinaryTreeNode<T>* nlast = NULL;
		while (!q.empty())
		{
			BinaryTreeNode<T>* 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<T>* _root;
};


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

	t1.LevelOrder();
}

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

分享名稱：按層換行打印二叉樹-創(chuàng)新互聯(lián)
瀏覽路徑：http://www.chinadenli.net/article24/dhecje.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站策劃、定制開發(fā)、網(wǎng)站建設(shè)、品牌網(wǎng)站制作、微信公眾號、靜態(tài)網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)