알고스팟(algospot) 21 장 트리의 구현과 순회

21.1 도입

 계층구조를 가지는 것 같다? --> 트리

 

-트리의 구성요소  : 노드 node, 간선 edge

 

-트리는 재귀적 속성을 가지기 때문에 트리를 구현한 함수들은 대부분 재귀로 구현 가능!

 

-구조체로 구현하는것이 일반적!

 

struct TreeNode  { 
	string label; // 저장할자료(물론꼭문자열일 필요는 없다.) 
    TreeNod* parent; //부모노드를가리키는포인터
    vector<TreeNod*> children; //자손노드들을가리키는포인터의 배열 
};

 

 

21.2 트리의 순회

 

-순회할때는 트리의 재귀적 속성을 사용하는 것이 좋음

 

 

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

-- 모든 노드 출력코드

 

-트리의 높이도 위의 코드를 약간 변형

 

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

 

 

--문제들

21.3 트리 순회의 순서 변경

21.5 요새