Data.Math.Phys2017. 6. 23. 20:20


 

개요

 

트리 구조예.


트리순회 (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); // 자기 자신 함수 호출함. 즉 재귀호출.
     }
  }


 

 


 


///1326.


Posted by 리치굿맨

댓글을 달아 주세요