함수를 써서 두 갈래 트리의 어떤 층의 모든 결점을 인쇄하다

2366 단어
두 갈래 트리 결점 정의:struct Node {int v;Node* left;Node* right;};
함수 원형:void print_node_at_level(Node* node, int level);
설명: level 층의 결점에 저장된 값을 같은 줄에 인쇄합니다.
 
생각:
귀속 방법을 이용하여 node가 가리키는 결점이 루트 노드인 제1level층의 결점을 인쇄할 수 있으며, node의 좌우 트리인 제1level-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;
}

 

좋은 웹페이지 즐겨찾기