We discuss two common variants of trees and show some typical functions of each variant.
A binary tree is either of the following: a singleton value called empty (also null or leaf) or a pair, called a branch, consisting of two binary trees called the left and the right child. Most often, a branch is a triple rather than a pair which in addition to the children also stores a value of some generic set. This value is called the root or decoration of the tree.
A (decorated) binary tree is declared in Curry as:
where BinTree is a type constructor and is its parameter and stands for the type of the decorations. A popular variant of binary trees is called a binary search tree. The set of decorations is totally ordered and the decoration of a non-empty binary search tree is greater than all the decorations in the left child and smaller than all the decorations in the right child. This condition prevents repeated decorations in a binary search tree. The following function inserts a value in a binary search tree in such a way that the result is again a binary search tree [Browse Program][Download Program]:
An in-order traversal of any binary search tree produces the sorted list of the decorations of the tree.
An ordered tree is a pair in which the first component is an element of a set, called the set of decorations, and the second component is a sequence of ordered trees.
An ordered tree is declared in Curry as:
where is a parameter that stands for the type of the decorations and the identifier “Tree” is overloaded to denote both a type constructor (1st and 3rd occurrences) and a data constructor (2nd occurrence).
A trie is a tree that stores a mapping from keys, typically strings, to values and is characterized by sharing key prefixes. We present a simple variant where only keys are stored. This variant is useful to efficiently represent a dictionary and tell whether a string is in the dictionary.
We declare the type of a trie as follows:
The following function inserts a string in a trie sharing whatever prefix of the string might already be present in the trie. The distinguished symbol that terminates a string is a period. [Browse Program][Download Program]