博客

二叉树结点定义：

struct Node

{

int v;

Node* left;

Node* right;

};

函数原型：

void print_node_at_level(Node* node, int level)；

说明：

将level层的结点中所保存的值打印在同一行。

思路：

可以利用递归方法，

打印

node所指结点为根节点的第level层的结点，可以打印node的左右子树的第level-1层的结点，一次递归。

还可以用层次遍历的方法打印某一层的结点，要借助两个队列实现，一个队列一次存放每层的结点，另一个队列一次存放对应结点所在的层数。

#include <iostream>
#include <queue>


using namespace std;

struct Node
{
	int v; 
	Node* left;
	Node* right;
};

void print_node_at_level(Node* node, int level)
{
	if( node == NULL || level <= -1 )
		return ;

	if( level == 0 )
		cout<<node->v<<'\t';
	else
	{
		print_node_at_level(node->left, level-1); /* 递归调用，直到level==0 */
		print_node_at_level(node->right, level-1);
	}
}

void print_node_at_level_ex(Node* node, int level)
{
	if( node == NULL || level <= -1 )
		return ;

	queue<Node*> queue_node;  /*用于存放结点指针的队列*/
	queue<int>  queue_level;  /*用于存放每个节点对应的层数*/
	int count_level = 0;

	queue_node.push(node);
	queue_level.push(0);
	while( queue_node.size() != 0 )
	{
		Node* temp = queue_node.front();
		count_level = queue_level.front();

		queue_node.pop();
		queue_level.pop();


		if( count_level == level ) /*到达指定的层数，打印结点数值*/
		{
			cout<<temp->v<<'\t';
		}
		else if( count_level < level )  /*没有到达指定层数，继续层次遍历该数*/
		{
			if( temp->left != NULL )
			{
				queue_node.push(temp->left);
				queue_level.push(count_level+1);
			}

			if( temp->right != NULL )
			{
				queue_node.push(temp->right);
				queue_level.push(count_level+1);
			}
		}	
	}

}

int main()
{
	Node nodes[] = { {0, NULL, NULL},
	                 {1, NULL, NULL},
	                 {2, NULL, NULL},
	                 {3, NULL, NULL},
	                 {4, NULL, NULL},
	                 {5, NULL, NULL},
	                 {6, NULL, NULL},
	                 {7, NULL, NULL}
	               };

	nodes[0].left  = &nodes[1];
    nodes[0].right = &nodes[2];
    nodes[1].left  = &nodes[3];
    nodes[1].right = &nodes[4];
    nodes[2].left  = &nodes[5];
    nodes[2].right = NULL;
    nodes[4].left  = &nodes[6];
    nodes[4].right = &nodes[7];

	print_node_at_level(nodes, 6);
	cout<<endl;
	print_node_at_level_ex(nodes, 6);
	cout<<endl;
	return 0;
}