We define the abstract data type \(\texttt{Ternary_Tree}\) (3 children tree) as follows:

Type: \(\texttt{TT(element)}\)
Use: \(\texttt{Boolean}\)

Functions:
\(\begin{array}{p{1cm} l l l l} & \textbf{Init}: & \texttt{TT} & \rightarrow \texttt{TT} & \text{// creates an empty TT} \\ & \textbf{Construct}: & \texttt{element} \times \texttt{TT} \times \texttt{TT} \times \texttt{TT} & \rightarrow \texttt{TT} & \text{// construct a tree by giving the root value and its 3 children} \\ & \textbf{LeftChildren}: & \texttt{TT} & \rightarrow \texttt{TT}&  return TT left children  \\ & \textbf{MiddleChildren}: & \texttt{TT}  & \rightarrow \texttt{TT} & \text{// return TT middle children}  \\ & \textbf{RightChildren}: & \texttt{TT}  & \rightarrow \texttt{TT} & \text{// return TT right children}  \\ & \textbf{Root}: & \texttt{TT}  & \rightarrow \texttt{element} & \text{// return root value}  \\ & \textbf{isEmpty}: & \texttt{TT} & \rightarrow \texttt{Boolean} & \text{// test if TT is empty}\\ & \textbf{Rotation}: & \texttt{TT}   & \rightarrow \texttt{TT} & \text{// replace left subtree by middle subtree, middle subtree by right subtree, and right subtree by the left one and leave the root unchanged. If the tree is empty then the operation has no effect} \\   & \textbf{CutM}: & \texttt{TT}   & \rightarrow \texttt{TT} & \text{// replace the middle subtree by an empty tree} \\ \end{array}\)

Constructors: ...
Preconditions:  ...
Axioms: ...

Fill in missing paragraphs.

Difficulty level
This exercise is mostly suitable for students 
Let A, L, M, R be a TT and e an element
Constructors: Init, Construct
Preconditions: LeftChildren(A), MiddleChildren(A), RightChildren(A), Root(A), CutM(A) defined iff not isEmpty(A)
Axioms:
    * isEmpty(Init()) = True
    * Rotation(Init())=Init()
    * isEmpty(Construct(e,L,M,R)) = False
    * Root(Construct(e,L,M,R))=e
    * LeftChildren(Construct(e,L,M,R))=L
    * MiddleChildren(Construct(e,L,M,R))=M
    * RightChildren(Construct(e,L,M,R))=R
    * Rotation(Construct(e,L,M,R))=Construct(e,M,R,L)
    * CutM(Construct(e,L,M,R))=Construct(e,L,Init(),R)
Back to the list of exercises
Looking for a more challenging exercise, try this one !!
Forest of Binary Search Trees