OCaml의 tree 1

OCaml에서 Tree를 구현하는 방법은 Node를 Record로 구현하는 방법, Node를 Tuple로 구현하는 방법 2개가 있다.

 

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

 

tree는 Leaf 노드와 왼쪽 트리, 오른쪽 트리를 갖는 node 둘 중 하나이다.

node는 값 value와 왼쪽 트리 left, 오른쪽 트리 right를 갖는다.

 

* 이때 node 앞에 and를 쓰지 않고 type을 쓰면 안된다.

왜냐면 node에 있는 left와 right에서 tree를 사용하기 때문이다.

 

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

• mem
  • tree에 x값이 있는지 확인하는 함수
• preorder
  • tree의 전위 순회 값
• inorder
  • tree의 중위 순회 값
• postorder
  • tree의 후위 순회 값
• size
  • tree의 크기
  • record에서 pattern variable은 record에서 사용된 이름을 그대로 사용하거나 = 을 이용하여 pattern variable 이름을 지정할 수 있다. size에서 value의 값을 사용하지 않기 때문에 record에서 사용된 이름을 그대로 사용하지 않고 _로 지정하여 사용해야 error가 발생하지 않는다.
• leafNum
  • tree에서 Leaf 노드의 개수
  • record에서 pattern variable은 record에서 사용된 이름을 그대로 사용하거나 = 을 이용하여 pattern variable 이름을 지정할 수 있다. size에서 value의 값을 사용하지 않기 때문에 record에서 사용된 이름을 그대로 사용하지 않고 _로 지정하여 사용해야 error가 발생하지 않는다.

 

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

그림 1

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

그림 1을 표현하는 노드 t

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

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

 

그림 2

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

그림 2의 결과

그림 3

그림 3의 결과

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

 

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