FICO
FICO Xpress Optimization Examples Repository
FICO Optimization Community FICO Xpress Optimization Home
Back to examples browserPrevious exampleNext example

Defining a package to handle binary trees

Description
  • definition of subroutines (function, procedure)
  • data structures 'list' and 'record'
  • type definitions
The package 'bintree' defines the new types 'tree' (to represent a binary tree data structure) and 'btree_node' (a tree node, building blocks of trees storing the actual data) for the Mosel language and also a set of subroutines for working with trees, such as inserting a value into a tree, locating a value, getting the tree size, printing out a tree, and converting a tree to a list.

The model file 'exbtree.mos' shows how to create a tree and work with it using the functionality of this package. To run this example, you first need to compile the package (resulting in the BIM file 'bintree.bim'). You may then execute the example in the same directory that contains this BIM file.

bintree.zip[download all files]

Source Files
By clicking on a file name, a preview is opened at the bottom of this page.
bintree.mos[download]
exbtree.mos[download]




bintree.mos

(!*******************************************************
   Mosel Example Problems
   ======================

   file bintree.mos
   ````````````````
   a package that provides the functionality for
   handling binary trees

   (c) 2021 Fair Isaac Corporation
       author: Y. Colombani, 2006
  *******************************************************!)
package bintree

declarations
 public btree_node=record
       value:real
       left,right:integer
      end-record
 public tree=dynamic array(range) of btree_node
end-declarations

forward procedure show(t:tree,n:integer)
forward procedure makelist(t:tree,n:integer,l:list of real)

!**************************************************************
!* Public declarations
!**************************************************************

!**************************
! Insert a value in a tree
!**************************
public procedure insert(t:tree,v:real)
 if t.size > 0 then
  j:=1
  repeat
   p_j:=j
   j:=if(t(j).value > v , t(j).left,t(j).right)
  until (j=0)
  if t(p_j).value <> v then
   with lastnode=t.size+1 do
    t(lastnode).value:=v
    if t(p_j).value > v then
     t(p_j).left:=lastnode
    else
     t(p_j).right:=lastnode
    end-if
   end-do
  end-if
 else
  t(1).value:=v
 end-if
end-procedure

!***************************************************
! Check whether a value is already stored in a tree
!***************************************************
public function find(t:tree,v:real):boolean
 if t.size > 0 then
  j:=1
  repeat
   if t(j).value > v then
    j:=t(j).left
   elif t(j).value < v then
    j:=t(j).right
   else
    break
   end-if
  until (j=0)
  returned:= j<>0
 else
  returned:=false
 end-if
end-function

!*****************
!* Display a tree
!*****************
public procedure show(t:tree)
 write("<")
  if t.size > 0 then
   show(t,1)
  end-if
 writeln(" >")
end-procedure

!*************************************************
!* Return the sorted list of all values of a tree
!*************************************************
public function tolist(t:tree):list of real
  if t.size > 0 then
   makelist(t,1,returned)
  end-if
end-function

!**************************************************************
!* Private declarations
!**************************************************************
!********************
!* Display a subtree
!********************
procedure show(t:tree,n:integer)
 if n > 0 then
  show(t,t(n).left)
  write(" ",t(n).value)
  show(t,t(n).right)
 end-if
end-procedure

!*****************************
!* Append a subtree to a list
!*****************************
procedure makelist(t:tree,n:integer,l:list of real)
 if n > 0 then
  makelist(t,t(n).left,l)
  l+=[t(n).value]
  makelist(t,t(n).right,l)
 end-if
end-procedure

end-package
Back to examples browserPrevious exampleNext example
© Copyright 2023 Fair Isaac Corporation.