Defining a package to handle binary trees


Type:	Programming
Rating:	4 (medium-difficult)
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 '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.
File(s):	bintree.mos, exbtree.mos

bintree.mos

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

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

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

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

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

!**************************************************************
!* Public declarations
!**************************************************************
!**************
! Reset a tree
!**************
public procedure reset(t:tree)
 delcell(t.nodes)
 t.lastnode:=0
end-procedure

!************************
! Get the size of a tree
!************************
public function getsize(t:tree):integer
 returned:=t.lastnode
end-function

!**************************
! Insert a value in a tree
!**************************
public procedure insert(t:tree,v:real)
 if t.lastnode  > 0 then
  j:=1
  repeat
   p_j:=j
   j:=if(t.nodes(j).value > v , t.nodes(j).left,t.nodes(j).right)
  until (j=0)
  if t.nodes(p_j).value <> v then
   t.lastnode+=1
   t.nodes(t.lastnode).value:=v
   if t.nodes(p_j).value > v then
    t.nodes(p_j).left:=t.lastnode
   else
    t.nodes(p_j).right:=t.lastnode
   end-if
  end-if
 else
  t.lastnode+=1
  t.nodes(t.lastnode).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.lastnode > 0 then
  j:=1
  repeat
   if t.nodes(j).value > v then
    j:=t.nodes(j).left
   elif t.nodes(j).value < v then
    j:=t.nodes(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.lastnode > 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.lastnode > 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.nodes(n).left)
  write(" ",t.nodes(n).value)
  show(t,t.nodes(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.nodes(n).left,l)
  l+=[t.nodes(n).value]
  makelist(t,t.nodes(n).right,l)
 end-if
end-procedure

end-package

exbtree.mos

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

   file exbtree.mos
   ````````````````
   Example of use lists and of the 'bintree' package

   -- Note: The package 'bintree' (file bintree.mos)  
      needs to be compiled before executing this model --

   (c) 2008 Fair Isaac Corporation
       author: Y. Colombani, 2006
  *******************************************************!)
model exbtree
uses ':bintree.bim'

declarations
 arbre:tree
 allvals:list of real
end-declarations

repeat
 insert(arbre,round(random*100))
until arbre.size = 10

write("Values in the binary tree:"); show(arbre)

allvals:=tolist(arbre)
writeln("The smallest value:",allvals.first)
writeln("The biggest value:",allvals.last)
writeln("The 5 first entries:",splithead(allvals,5))
writeln("Remaining after split:",allvals)

end-model

Contents

Index

Glossary

Search Results

Defining a package to handle binary trees