【C/C++練習問題】二叉木を上から下まで印刷

『剣指Offer』面接問題32
 
 
タイトル1
ツリーの各ノードを上から下に印刷し、同じレイヤのノードを左から右に順番に印刷します.
 
構想
キューの先入先出を利用して、ツリーの階層別ノード情報の印刷を完了します.キューに二叉木のノードポインタを格納し,まずルートノードをエンキューし,ルートノードをデキュー印刷するとともに左右のサブノードポインタをエンキューする.これにより,キューからノードを取り出し,ノードを印刷し,左右のサブノードをキューに入れ,最終的にすべてのノードを階層別に印刷することが完了する.
 
コード#コード#

/******************************************************************************
*     ：            
*     ：pTreeRoot         
*     ： 
*    ：true    , false       
*   ： 
******************************************************************************/
bool Print_level_order(BinaryTreeNode* pTreeRoot)
{
	if (NULL == pTreeRoot)
	{
		return false;
	}

	queue nodes;	//      nodes

	//1.        
	nodes.push(pTreeRoot);
	while(!nodes.empty())
	{
		//2.      ,       
		BinaryTreeNode* pNode = nodes.front();
		cout << pNode->m_nValue << ",";
		
		//3.      
		nodes.pop();

		//4.          
        if(pNode->m_pLeft != NULL)
        {
            nodes.push(pNode->m_pLeft);
        }
        if(pNode->m_pRight != NULL)
        {
            nodes.push(pNode->m_pRight);
        }
	}

	return true;
}

 
 
タイトル2
二叉木を上から下へ層別に印刷し、同じ層のノードを左から右への順に印刷し、各層を1行に印刷します. 
構想
前に、次のレイヤノードの個数と現在のレイヤ印刷対象ノードの個数をそれぞれ記録する2つの変数を設定します.
 
コード#コード#

/******************************************************************************
*     ：           
*     ：pTreeRoot         
*     ： 
*    ：true    , false       
*   ： 
******************************************************************************/
bool Print_level_order(BinaryTreeNode* pTreeRoot)
{
	if (NULL == pTreeRoot)
	{
		return false;
	}

	queue nodes;	//      nodes
	int next_level = 0;				//        
	int level_num = 1;				//          

	//1.        
	nodes.push(pTreeRoot);
	while(!nodes.empty())
	{
		//2.      ,       
		BinaryTreeNode* pNode = nodes.front();
		cout << pNode->m_nValue << " ";
		
		//3.      
		nodes.pop();
		--level_num;

		//4.          ,         next_level
        if(pNode->m_pLeft != NULL)
        {
        	++next_level;
            nodes.push(pNode->m_pLeft);
        }
        if(pNode->m_pRight != NULL)
        {
        	++next_level;
            nodes.push(pNode->m_pRight);
        }

        //5.    
        if (level_num == 0)
        {
        	cout << endl;
        	level_num = next_level;
        	next_level = 0;
        }
	}

	return true;
}

 
 
テーマ3
二叉木をフォント順に印刷する関数を実装してください.すなわち、第1行は左から右、第2層は右から左、第3行は左から右の順に印刷し、他の行はこのようにします.
 
ぶんせき
2つのスタックstack 1、stack 2を使用して完了し、ルートノードをstack 1にpushし、印刷をポップアップします.ルートノードの左サブノードと右サブノードをそれぞれstack 1にpushし、stack 1から要素印刷をポップアップする.同時に、次のレイヤの右サブノードと左サブノードをスタックstack 2にそれぞれpushを押し込む(第2のレイヤノードがstack 1からpopが完了すると、第3のレイヤのノードもstack 2に押し込まれて完了する).stack 1、stack 2スタックが空になるまで、印刷を完了します.
 
コード#コード#

/******************************************************************************
*     ：        
*     ：pTreeRoot         
*     ： 
*    ：true    , false       
*   ： 
******************************************************************************/
bool Print_level_order(BinaryTreeNode* pTreeRoot)
{
	if (NULL == pTreeRoot)
	{
		return false;
	}

	stack levels[2];	//      nodes
	int current = 0;		
	int next = 1;			

	//1.        
	levels[current].push(pTreeRoot);

	while (!levels[0].empty() || !levels[1].empty())
	{
		//2.          
		BinaryTreeNode* pNode = levels[current].top();
		levels[current].pop();

		cout << pNode->m_nValue << " ";

		if (current == 0)
		{
			if (pNode->m_pLeft != NULL)
				levels[next].push(pNode->m_pLeft);
			if (pNode->m_pRight != NULL)
				levels[next].push(pNode->m_pRight);
		}
		else
		{
			if (pNode->m_pRight != NULL)
				levels[next].push(pNode->m_pRight);
			if (pNode->m_pLeft != NULL)
				levels[next].push(pNode->m_pLeft);
		}

		if (levels[current].empty())
		{
			cout << endl;
			current = 1 - current;
			next = 1 - next;
		}
	}

	return true;
}

 
 
ソースリンク:https://gitee.com/hinzer/sword_to_offer/tree/master/questions