Arbre binaire

Guimauve · Message par **Guimauve** » dim. 12/nov./2006 17:04

Bonjour à tous.

Voiçi un exemple qui montre comment on peut créer une variable, un tableau et possiblement une liste d'arbre binaire et peut-être même l'imbriquer dans une structure de donnée.

Ce code est inspiré de l'exemple d'arbre binaire de Comtois.

Si ce code peut être utile à quelqu'un...

A+
Guimauve

[EDIT] Affichage du nombre de noeud de chacun des arbres

Code : Tout sélectionner

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; 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)NbTiret
  
  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 · Message par **Guimauve** » lun. 13/nov./2006 2:48

Un autre exemple cette fois avec des valeurs numérique de type Byte (.b)
Et c'est confirmé, il est possible de créer des arbres de manière unitaire,
dans une liste chaînée, dans un tableau dynamique ou même l'imbriqué
dans une structure de donnée.

Désolé le code est en anglais.

A+
Guimauve

Code : Tout sélectionner

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; 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 <<<<<
; <<<<<<<<<<<<<<<<<<<<<<<