트리순회. 재귀호출. Tree Traverse. Recursion Call.

 

	개요
	트리 구조예.     트리순회 (Tree Traverse) : 트리구조의 각 노드에 중복없이 모두 접근하는것. 재귀호출 (Recursion Call)  :  함수가 자기 자신을 호출하는것.   트리 순회 구현은 필연적으로 재귀호출 형식으로 구현된다.

 

 

	트리순회 함수. 재귀함수 가 왜 요구되는지 단계별 이해.
	단계1. 일반적인 트리순회 함수 전체 구현 전에 어떤 노드 1개를 함수 입력으로 전달하면 입력한 노드의 하위 노드에 접근하는 코드를 먼저 구현해보자.   void myFunc( nodetype  node_in)   {      node_in 에 연결된 모든 node 루프      {           node_1; // 여기서 함수 입력 node_in 에 연결된 node_1에는 모두 접근완료됨.      }   }     단계2. - 비 재귀적 구현시도. 상기 단계1에서의 하위node 에 또 노드들이 연결되어있을 수 있으므로 해당 노드에 접근하기 위한 코드 추가해보자. 아래 파랑색 부분이 추가되었다.     void myFunc( nodetype  node_in)   {      node_in 에 연결된 모든 node 루프      {           node_1; // 여기서 함수 입력 node_in 에 연결된 node_1 들에 모두 접근완료됨.           node_1 에 연결된 모든 node_2 루프.           {                node_2 ; // 여기서 node_1들에 연결된 node_2 에 모두 접근완료됨.           }      }   } 검토. 위와 같은 코드로 node_2까지는 접근가능하나, node_2 에 연결된 노드에 접근하려면 node_2 루프내에서 하위 노드 찾는 코드를 추가해야한다. 이런 식의 로직으로는 트리구조에서 하위에 몇 층으로 노드들이 부착되어있을지 모르기 때문에 범용 로직 구현 불가능. 단계3. 재귀 호출 구현. 상기 단계1의 코드상태에서 재귀호출방식으로 구현하면, 트리구조에서 하위노드 계층이 많든 적든 node_in의 하위에 연결된 모든 노드에 접근가능하며 코드도 간결하다.   void myFunc( nodetype  node_in)   {        ...          // node_in 이용하여 할 것들 수행.              node_in 에 연결된 모든 node 루프      {           node_1; // 여기서 함수 입력 node_in 에 연결된 node_1에는 모두 접근완료됨.            myFunc (node_1); // 자기 자신 함수 호출함. 즉 재귀호출.      }   }

 

 

 

---

첫 등록 : 2017.06.23

최종 수정 : 

단축 주소 : https://igotit.tistory.com/1326

---