OCaml의 tree 2

오늘은 Tuple로 구현하는 방법을 살펴보자.

 

tree는 Leaf 노드와 튜플 형태의 노드 둘 중 하나이다.

튜플은 값과 왼쪽 트리, 오른쪽 트리로 이루어져있다.

 

tree에 대해 연산을 수행할 함수들

• Record로 구현했을 때와 달리 Node를 구성하는 각 데이터에 대해 지정된 이름이 없기 때문에 해당 이름을 기억하지 않아도 된다. 또한 pattern matching을 할 때도 단순히 사용할 pattern variable의 이름을 설정해주면 된다.
• Record로 구현했을 때와 다른 부분이 거의 없는데 pattern matching을 하기에는 Tuple이 더 좋은 것 같다.

 

•  mem
  • tree에 x값이 있는지 확인하는 함수
• preorder
  • tree의 전위 순회 값
• inorder
  • tree의 중위 순회 값
• postorder
  • tree의 후위 순회 값
• size
  • tree의 크기
  • 각각 데이터의 이름을 기억할 필요가 없기 때문에 값을 의미하는 첫 번째 pattern variable을 _로 설정하면 된다.
• leafNum
  • tree에서 Leaf 노드의 개수
  • 각각 데이터의 이름을 기억할 필요가 없기 때문에 값을 의미하는 첫 번째 pattern variable을 _로 설정하면 된다.

 

실제로 tree를 만들어서 위의 함수들을 적용해보자.

 

위와 같은 그림의 트리를 지금 구현한 것으로 표현해보면 아래와 같다.

그림 1을 표현한 노드 t

t에 대해서 전위 순회, 중위 순회, 후위 순회한 결과를 구하자.

pre는 t를 preorder한 값이고 ino는 t를 inorder한 값, post는 t를 postorder한 값이다.

 

그림 2

*각각 순회하는 함수는 Leaf일 경우 []를 반환하기 때문에 Leaf가 들어올 때를 고려하여 match를 해줘야 한다.

그림 2의 결과

그림 3

그림 3의 결과

그림 1을 보면 5는 있기 때문에 true이고 9는 없기 때문에 false이다.

 

이 글은 제가 Ocaml을 공부하며 작성한 글로 정확하지 않은 부분이 있을 수 있습니다.