트리 구조

root노드 : 다른 모든 노드들을 자손으로 갖는 노드

leaf노드 : 자식이 하나도 없는 노드

depth(깊이) : 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수

height(높이) : 트리에서 가장 깊숙히 있는 노드의 깊이

struct TreeNode{
	string label;
	TreeNode *parent;
	vector<TreeNode*> children;
}

트리의 노드는 주로 위와 같이 구조체로 정의된다.

트리의 순회

(1) 모든 노드의 label 출력하기

void printLabels(TreeNode* root){
	cout << root->label << endl;
	for(int i = 0; i< root->children.size(); i++)
		printLabels(root->children[i]); 
}

재귀를 사용해서 위와 같이 서브트리를 방문할 수 있다.

(2) 트리의 높이 출력하기

int height(TreeNode *root){
	int h = 0;
	for(int i = 0;i < root->children.size(); i++)
		h = max(h, 1 + height(root->children[i])); 
	return h;
}

children을 타고 내려갈수록 1을 더하고, 가장 아래의 리프 노드를만났을 때 재귀호출을 끝내면서 구해진 가장 최댓값을 통해 높이를 구한다.

문제 : 트리 순회 순서 변경