; Auteur : Dr.Dri
; Date : 06/02/2007

EnableExplicit

;> ----------------------------------------- <
;- Structures d'Arbres Binaires de Recherche
;> ----------------------------------------- <

Structure BSN ; Binary Search Node
  item.l
  *subs.BSN[2]
EndStructure

Structure BST ; Binary Search Tree
  StructureUnion
    *root.BSN
    *node.BSN
  EndStructureUnion
EndStructure

;> ----------------------------------- <
;- Fonctions pour manipuler les noeuds
;> ----------------------------------- <

Procedure.l InsertBSN(*Tree.BST, Item.l)
  Protected Insert.l
 
  If Not *Tree\node
    *Tree\node = AllocateMemory( SizeOf(BSN) )
    *Tree\node\item = Item
    Insert = *Tree
  ElseIf Item > *Tree\node\item
    Insert = InsertBSN(@*Tree\node\subs[1], Item)
  ElseIf Item < *Tree\node\item
    Insert = InsertBSN(@*Tree\node\subs[0], Item)
  EndIf
 
  ProcedureReturn Insert
EndProcedure

Procedure.l RemoveBSN(*Tree.BST, *Item.Long)
  Protected Remove.l
 
  If *Tree\node\subs[0]
    RemoveBSN(@*Tree\node\subs[0], *Item)
  Else
    *Item\l = *Tree\node\item
   
    If *Tree\node\subs[1]
      RemoveBSN(@*Tree\node\subs[1], @*Tree\node\item)
    Else
      FreeMemory(*Tree\node)
      *Tree\node = #Null
    EndIf
   
  EndIf
 
  ProcedureReturn Remove
EndProcedure

Procedure.l DeleteBSN(*Tree.BST, Item.l)
  Protected Delete.l
 
  If Not *Tree\node
    Delete = #False
  ElseIf Item > *Tree\node\item
    Delete = DeleteBSN(@*Tree\node\subs[1], Item)
  ElseIf Item < *Tree\node\item
    Delete = DeleteBSN(@*Tree\node\subs[0], Item)
  Else
    If Not *Tree\node\subs[0] Or Not *Tree\node\subs[1]
      RemoveBSN(*Tree, @*Tree\node\item)
    Else
      RemoveBSN(@*Tree\node\subs[1], @*Tree\node\item)
    EndIf
  EndIf
 
  ProcedureReturn Delete
EndProcedure

Procedure.s StrBSN(*Tree.BST, Open.c, Close.c, Empty.c)
  Protected String.s
 
  String + Chr(Open)
 
  If *Tree\node
    String + Str(*Tree\node\item)
    If *Tree\node\subs[0] Or *Tree\node\subs[1]
      String  + StrBSN(@*Tree\node\subs[0], Open, Close, Empty)
      String  + StrBSN(@*Tree\node\subs[1], Open, Close, Empty)
    EndIf
  Else
    String + Chr(Empty)
  EndIf
 
  String + Chr(Close)
 
  ProcedureReturn String
EndProcedure

Procedure.s StrSortedBSN(*Tree.BST, Separator.c)
  Protected String.s
 
  If *Tree\node
    If *Tree\node\subs[0]
      String  + StrSortedBSN(@*Tree\node\subs[0], Separator)
    EndIf
   
    String + Str(*Tree\node\item) + Chr(Separator)
   
    If *Tree\node\subs[1]
      String  + StrSortedBSN(@*Tree\node\subs[1], Separator)
    EndIf
  EndIf
 
  ProcedureReturn String
EndProcedure

;> ----------------------------------- <
;- Fonctions pour manipuler les arbres
;> ----------------------------------- <

ProcedureDLL.l NewBST()
  ProcedureReturn AllocateMemory( SizeOf(BST) )
EndProcedure

ProcedureDLL.l InsertBST(*Tree.BST, Item.l)
  ProcedureReturn InsertBSN(@*Tree\root, Item)
EndProcedure

ProcedureDLL.l DeleteBST(*Tree.BST, Item.l)
  ProcedureReturn DeleteBSN(@*Tree\root, Item)
EndProcedure

ProcedureDLL.l ClearBST(*Tree.BST)
  Protected Clear.l = #True
 
  While *Tree\root
    Clear | DeleteBSN(@*Tree\root, *Tree\root\item)
  Wend
 
  ProcedureReturn Clear
EndProcedure

ProcedureDLL.l FreeBST(*Tree.BST)
  ClearBST(*Tree)
  ProcedureReturn FreeMemory(*Tree)
EndProcedure

ProcedureDLL.s StrBST(*Tree.BST, Open.c = '{', Close.c = '}', Empty.c = '*')
  ProcedureReturn StrBSN(@*Tree\root, Open, Close, Empty)
EndProcedure

ProcedureDLL.s StrSortedBST(*Tree.BST, Separator.c = ' ')
  ProcedureReturn StrSortedBSN(@*Tree\root, Separator)
EndProcedure

;> ------------ <
;- Petits tests
;> ------------ <

Define Tree = NewBST()

InsertBST(Tree, 6)
InsertBST(Tree, 2)
InsertBST(Tree, 1)
InsertBST(Tree, 4)
InsertBST(Tree, 3)
InsertBST(Tree, 5)
InsertBST(Tree, 8)
InsertBST(Tree, 7)
InsertBST(Tree, 9)
InsertBST(Tree, 11)
InsertBST(Tree, 10)

;à l'issue des insertions on a cet arbre :
;        6
;   2         8
; 1   4     7   9
;    3 5          11
;               10
Debug StrBST(Tree)
Debug StrSortedBST(Tree)

DeleteBST(Tree, 8)

;à l'issue de la supression on a cet arbre :
;        6
;   2         9
; 1   4     7   10
;    3 5          11
Debug StrBST(Tree)
Debug StrSortedBST(Tree)