BinaryTree

Guimauve · Post by **Guimauve** » Sun Nov 12, 2006 5:16 pm

Hello everyone

Yes, an another small exemple, this time it's a BinaryTree. This exemple demonstate how to create a BinaryTree as simple variable, Array, LinkedList (Not tested yet) or as a Structure nested field (Not tested yet).

If this exemple can be usefull for someone.

Sorry, the source code are in french but if someone is willing to translate go for it.

EDIT Minor change - Based Object Programming BOP

Regards
Guimauve

Code: Select all

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; Nom du projet : Exemple d'arbre binaire
; Fichier : Arbre Binaire V1.pb
; Version : 1.0.1
; Programmation : CODE EXPÉRIMENTAL
; Programmé par : Guimauve
; Code Original : Comtois
; Date : 12-11-2006
; Mise à jour : 12-11-2006
; Codé avec PureBasic V4.01
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; CODE GÉNÉRÉ AUTOMATIQUEMENT, NE PAS MODIFIER À
; MOINS D'AVOIR UNE RAISON TRÈS TRÈS VALABLE !!!
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; <<<<< Déclaration de la Structure <<<<<

Structure Noeud
  
  Mots.s
  Compteur.l
  Gauche.l
  Droite.l
  
EndStructure

; <<<<<<<<<<<<<<<<<<<<<<<<<
; <<<<< Les mutateurs <<<<<

Macro SetNoeudMots(Noeud, P_Mots)
  
  Noeud\Mots = P_Mots
  
EndMacro

Macro SetNoeudCompteur(Noeud, P_Compteur)
  
  Noeud\Compteur = P_Compteur
  
EndMacro

Macro SetNoeudGauche(Noeud, P_Gauche)
  
  Noeud\Gauche = P_Gauche
  
EndMacro

Macro SetNoeudDroite(Noeud, P_Droite)
  
  Noeud\Droite = P_Droite
  
EndMacro

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<
; <<<<< Les observateurs <<<<<

Macro GetNoeudMots(Noeud)
  
  Noeud\Mots
  
EndMacro

Macro GetNoeudCompteur(Noeud)
  
  Noeud\Compteur
  
EndMacro

Macro GetNoeudGauche(Noeud)
  
  Noeud\Gauche
  
EndMacro

Macro GetNoeudDroite(Noeud)
  
  Noeud\Droite
  
EndMacro

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; <<<<< Code généré en : 00.001 secondes <<<<<
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

Procedure PrivateAfficheNoeuds(*Noeud.Noeud)
  
  If *Noeud <> #Null
    
    PrivateAfficheNoeuds(GetNoeudGauche(*Noeud))
    
    Debug GetNoeudMots(*Noeud) + " =---> " + Str(GetNoeudCompteur(*Noeud)) + " fois"
    
    PrivateAfficheNoeuds(GetNoeudDroite(*Noeud))
    
  EndIf
  
EndProcedure

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; <<<<< Fin de la définition du noeud <<<<<
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; CODE GÉNÉRÉ AUTOMATIQUEMENT, NE PAS MODIFIER À
; MOINS D'AVOIR UNE RAISON TRÈS TRÈS VALABLE !!!
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; <<<<< Déclaration de la Structure <<<<<

Structure ArbreBinaire
  
  QteNoeud.l
  Noeud.Noeud
  
EndStructure

; <<<<<<<<<<<<<<<<<<<<<<<<<
; <<<<< Les mutateurs <<<<<

Macro SetArbreBinaireQteNoeud(Arbre, P_QteNoeud)
  
  Arbre\QteNoeud = P_QteNoeud
  
EndMacro

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<
; <<<<< Les observateurs <<<<<

Macro GetArbreBinaireQteNoeud(Arbre)
  
  Arbre\QteNoeud
  
EndMacro

Macro GetArbreBinaireNoeud(Arbre)
  
  Arbre\Noeud
  
EndMacro

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; <<<<< Code généré en : 00.001 secondes <<<<<
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

Procedure AfficheArbreBinaire(*Arbre.ArbreBinaire)
  
  PrivateAfficheNoeuds(GetArbreBinaireNoeud(*Arbre))
  
EndProcedure

Procedure.l PrivateAjouterNoeudArbre(*Arbre.ArbreBinaire, *Noeud.Noeud, Mot.s)
  
  If GetArbreBinaireQteNoeud(*Arbre) = 0 
    
    SetArbreBinaireQteNoeud(*Arbre, GetArbreBinaireQteNoeud(*Arbre) + 1)
    SetNoeudMots(*Noeud, Mot)
    SetNoeudCompteur(*Noeud, 1)
    SetNoeudGauche(*Noeud, #Null)
    SetNoeudDroite(*Noeud, #Null)
    
  Else 
    
    If *Noeud = #Null
      
      *Noeud = AllocateMemory(SizeOf(Noeud))
      
      If *Noeud
        
        SetArbreBinaireQteNoeud(*Arbre, GetArbreBinaireQteNoeud(*Arbre) + 1)
        SetNoeudMots(*Noeud, Mot)
        SetNoeudCompteur(*Noeud, 1)
        SetNoeudGauche(*Noeud, #Null)
        SetNoeudDroite(*Noeud, #Null)
        
      Else
        
        MessageRequester("Erreur","Impossible d'allouer de la mémoire !",0)
        End
        
      EndIf
      
    ElseIf UCase(Mot) = UCase(GetNoeudMots(*Noeud))
      
      SetNoeudCompteur(*Noeud, GetNoeudCompteur(*Noeud) + 1)
      
    ElseIf UCase(Mot) < UCase(GetNoeudMots(*Noeud))
      
      SetNoeudGauche(*Noeud, PrivateAjouterNoeudArbre(*Arbre, GetNoeudGauche(*Noeud), Mot))
      
    Else
      
      SetNoeudDroite(*Noeud, PrivateAjouterNoeudArbre(*Arbre, GetNoeudDroite(*Noeud), Mot))
      
    EndIf
    
  EndIf
  
  
  ProcedureReturn *Noeud
  
EndProcedure

Procedure AjouterNoeudArbre(*Arbre.ArbreBinaire, Mot.s)
  
  PrivateAjouterNoeudArbre(*Arbre, GetArbreBinaireNoeud(*Arbre), Mot)
  
EndProcedure

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; <<<<< Fin de la définition de l'arbre <<<<<
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

Dim MyHeros.s(14)

MyHeros(00) = "Zoro"
MyHeros(01) = "Fred"
MyHeros(02) = "Yoda"
MyHeros(03) = "Freak"
MyHeros(04) = "Morpheus"
MyHeros(05) = "Fred"
MyHeros(06) = "Freak"
MyHeros(07) = "Zoro"
MyHeros(08) = "Hercule"
MyHeros(09) = "Yoda"
MyHeros(10) = "Luke"
MyHeros(11) = "Anakin"
MyHeros(12) = "Mace Windu"
MyHeros(13) = "Yoda"
MyHeros(14) = "Obiwan"

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

NbTiret = 40

Dim MesArbres.ArbreBinaire(1)

Debug LSet("", NbTiret, "-")
Debug "1er arbre binaire"

For Index = 0 To 14
  AjouterNoeudArbre(MonArbre01.ArbreBinaire, MyHeros(Index))
Next 

Debug "Nombre de noeud : " + Str(GetArbreBinaireQteNoeud(MonArbre01))
Debug LSet("", NbTiret, "-")

AfficheArbreBinaire(MonArbre01)

Debug LSet("", NbTiret, "-")
Debug "2e arbre binaire"

For Index = 14 To 0 Step - 1
  AjouterNoeudArbre(MonArbre02.ArbreBinaire, MyHeros(Index))
Next 

Debug "Nombre de noeud : " + Str(GetArbreBinaireQteNoeud(MonArbre02))
Debug LSet("", NbTiret, "-")

AfficheArbreBinaire(MonArbre02)

Debug LSet("", NbTiret, "-")
Debug "3e arbre binaire"

For Index = 0 To 14 Step 2
  AjouterNoeudArbre(MesArbres(0), MyHeros(Index))
Next 

Debug "Nombre de noeud : " + Str(GetArbreBinaireQteNoeud(MesArbres(0)))
Debug LSet("", NbTiret, "-")

AfficheArbreBinaire(MesArbres(0))

Debug LSet("", NbTiret, "-")
Debug "4e arbre binaire"

For Index = 13 To 0 Step - 2
  AjouterNoeudArbre(MesArbres(1), MyHeros(Index))
Next 

Debug "Nombre de noeud : " + Str(GetArbreBinaireQteNoeud(MesArbres(1)))
Debug LSet("", NbTiret, "-")

AfficheArbreBinaire(MesArbres(1))

; <<<<<<<<<<<<<<<<<<<<<<<<<<
; <<<<< FIN DU FICHIER <<<<<
; <<<<<<<<<<<<<<<<<<<<<<<<<<

Guimauve · Post by **Guimauve** » Mon Nov 13, 2006 2:36 am

New testing exemple. This time with numerical value (.b)

Any suggestions ??

Regards
Guimauve

Code: Select all

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; Project name : BinaryTree Template
; File : BinaryTree
; File Version : 1.1.0
; Programmation : EXPERIMENTAL CODE
; Programmed by : Guimauve
; Date : 12-11-2006
; Last Update : 12-11-2006
; Coded for PureBasic V4.00
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; AUTOMATICALLY GENERATED CODE, DO NOT MODIFY
; UNLESS YOU REALLY, REALLY, REALLY MEAN IT !!
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; <<<<< Structure declaration <<<<<

Structure ByteNode
  
  Element.b
  left.l
  right.l
  
EndStructure

; <<<<<<<<<<<<<<<<<<<<<<<<<
; <<<<< The accessors <<<<<

Macro ByteNodeElement(ByteNodeA)
  
  ByteNodeA\Element
  
EndMacro

Macro ByteNodeLeft(ByteNodeA)
  
  ByteNodeA\left
  
EndMacro

Macro ByteNodeRight(ByteNodeA)
  
  ByteNodeA\right
  
EndMacro

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; <<<<< Code generated in : 00.016 seconds <<<<<
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

Procedure PrivateDebugByteNode(*ByteNodeA.ByteNode)
  
  If *ByteNodeA <> #Null
    
    PrivateDebugByteNode(ByteNodeLeft(*ByteNodeA))
    
    Debug ByteNodeElement(*ByteNodeA)
    
    PrivateDebugByteNode(ByteNodeRight(*ByteNodeA))
    
  EndIf
  
EndProcedure

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; AUTOMATICALLY GENERATED CODE, DO NOT MODIFY
; UNLESS YOU REALLY, REALLY, REALLY MEAN IT !!
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; <<<<< Structure declaration <<<<<

Structure ByteBinaryTree
  
  NodeCount.l
  RootNode.ByteNode
  
EndStructure

; <<<<<<<<<<<<<<<<<<<<<<<<<
; <<<<< The accessors <<<<<

Macro ByteBinaryTreeNodeCount(ByteBinaryTree)
  
  ByteBinaryTree\NodeCount
  
EndMacro

Macro ByteBinaryTreeRoot(ByteBinaryTree)
  
  ByteBinaryTree\RootNode
  
EndMacro

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; <<<<< Code generated in : 00.001 seconds <<<<<
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

Procedure DebugByteBinaryTree(*Tree.ByteBinaryTree)
  
  PrivateDebugByteNode(ByteBinaryTreeRoot(*Tree))
  
EndProcedure

Procedure.l PrivateAddNodeByteBinaryTree(*Tree.ByteBinaryTree, *ByteNodeA.ByteNode, Element.b)
  
  If ByteBinaryTreeNodeCount(*Tree) = 0 
    
    ByteBinaryTreeNodeCount(*Tree) + 1
    ByteNodeElement(*ByteNodeA) = Element
    ByteNodeLeft(*ByteNodeA) = #Null
    ByteNodeRight(*ByteNodeA) = #Null
    
  Else 
    
    If *ByteNodeA = #Null
      
      *ByteNodeA = AllocateMemory(SizeOf(ByteNode))
      
      If *ByteNodeA
        
        ByteBinaryTreeNodeCount(*Tree) + 1
        ByteNodeElement(*ByteNodeA) = Element
        ByteNodeLeft(*ByteNodeA) = #Null
        ByteNodeRight(*ByteNodeA) = #Null
        
      Else
        
        MessageRequester("Fatal Error","Impossible to allocate memory !",0)
        End
        
      EndIf
      
    ElseIf Element < ByteNodeElement(*ByteNodeA)
      
      ByteNodeLeft(*ByteNodeA) = PrivateAddNodeByteBinaryTree(*Tree, ByteNodeLeft(*ByteNodeA), Element)
      
    ElseIf Element > ByteNodeElement(*ByteNodeA)
      
      ByteNodeRight(*ByteNodeA) = PrivateAddNodeByteBinaryTree(*Tree, ByteNodeRight(*ByteNodeA), Element)
      
    EndIf
    
  EndIf
  
  ProcedureReturn *ByteNodeA
EndProcedure

Procedure AddNodeByteBinaryTree(*Tree.ByteBinaryTree, Element.b)
  
  PrivateAddNodeByteBinaryTree(*Tree, ByteBinaryTreeRoot(*Tree), Element)
  
EndProcedure

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; Testing code

Separator.s = LSet("", 40, "-")

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

For ByteNumber = 0 To 14
  AddNodeByteBinaryTree(MyTree01.ByteBinaryTree, Random(75))
Next

Debug Separator
Debug "1st Byte Binary Tree"
Debug "Node Count : " + Str(ByteBinaryTreeNodeCount(MyTree01))
Debug Separator

DebugByteBinaryTree(MyTree01)

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

For ByteNumber = 0 To 14
  AddNodeByteBinaryTree(MyTree02.ByteBinaryTree, Random(75))
Next

Debug Separator
Debug "2nd Byte Binary Tree"
Debug "Node Count : " + Str(ByteBinaryTreeNodeCount(MyTree02))
Debug Separator

DebugByteBinaryTree(MyTree02)

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

NewList ListOfByteBinaryTree.ByteBinaryTree()

For Index = 0 To 2
  AddElement(ListOfByteBinaryTree())
  For ByteNumber = 0 To 14
    AddNodeByteBinaryTree(ListOfByteBinaryTree(), Random(75))
  Next
Next

ForEach ListOfByteBinaryTree()
  Debug Separator
  Debug "List Index " + Str(ListIndex + 1) + " Byte Binary Tree"
  Debug "Node Count : " + Str(ByteBinaryTreeNodeCount(ListOfByteBinaryTree()))
  Debug Separator
  DebugByteBinaryTree(ListOfByteBinaryTree())
  ListIndex + 1
Next 

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

Dim ArrayOfByteBinaryTree.ByteBinaryTree(1)

For Index = 0 To 1
  For ByteNumber = 0 To 14
    AddNodeByteBinaryTree(ArrayOfByteBinaryTree(Index), Random(75))
  Next
Next

For Index = 0 To 1
  Debug Separator
  Debug "Array Index " + Str(Index + 1) + " Byte Binary Tree"
  Debug "Node Count : " + Str(ByteBinaryTreeNodeCount(ArrayOfByteBinaryTree(Index)))
  Debug Separator
  DebugByteBinaryTree(ArrayOfByteBinaryTree(Index))
Next 

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

Structure Dummy
  
  Nested.ByteBinaryTree
  
EndStructure

Alpha.Dummy 

For ByteNumber = 0 To 14
  AddNodeByteBinaryTree(Alpha\Nested, Random(75))
Next

Debug Separator
Debug "Dummy Structure Byte Binary Tree"
Debug "Node Count : " + Str(ByteBinaryTreeNodeCount(Alpha\Nested))
Debug Separator

DebugByteBinaryTree(Alpha\Nested)

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

; <<<<<<<<<<<<<<<<<<<<<<<
; <<<<< END OF FILE <<<<<
; <<<<<<<<<<<<<<<<<<<<<<<