按層換行打印二叉樹(shù)-創(chuàng)新互聯(lián)

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

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

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

基本過(guò)程如圖所示：

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

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

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

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

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

步驟：

1. 開(kāi)始讓 last 等于二叉樹(shù)的根節(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ì)列為空為止。

圖示過(guò)程如下：

先將 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é)果如下：

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

代碼如下：

#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)建二叉樹(shù)
	{
		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)  //銷毀二叉樹(shù)
	{
		if (NULL == root)
			return;

		//后序遍歷刪除結(jié)點(diǎn)
		_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元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

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

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

廣告

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