Dynamic Tree

[Spirit]

In dem Buch 'Spieleprogrammierung Gems 4' gibt es einen Artikel '1.7 Ein generischer Baumcontainer in C++' von Bill Budge. Darin wird kurz das Konzept für die Implementierung eines Baumes beschrieben. Beim Design wurde besonders darauf geachtet, dass ein Preorder-Durchlauf des Baumes so schnell wie möglich geht. Ich habe es so gut es mir möglich war in PureBasic umgesetzt. Außerdem habe ich die Sache objektorientiert gemacht, um dynamisch Bäume erstellen und löschen zu können.

Für alle, die nicht wissen, was ein Preorder-Durchlauf ist:

Ein Preorder-Durchlauf besucht zuerst jeden Knoten und dann deren Kindknoten. (ist auch im Beispiel-Programm unten erkennbar)

Code: Alles auswählen

;/ DynamicTree 3.2 by BlueSpirit

;{- Konstanten

Enumeration
  #TREE_AsChild
  #TREE_AsSibling
EndEnumeration

;}-
;{- Strukturen

Structure Node
  *_parent.Node
  *_prev_sibling.Node
  *_next.Node
  *_last_descendant.Node
  
  *_next_item.Node
  *_prev_item.Node
  
  Childs.l
  Level.l
EndStructure

;}-
;{- Objekt

Interface Tree
  ;Baum modifizieren
  AddNode(Flags)
  DeleteNode()
  ClearTree()
  Node()
  CopyNode(SourceNode, TargetNode)
  SwapNodes(Node1, Node2)
  ;Navigation
  NextNode()
  PreviousNode()
  ChangeNode(Node)
  SelectNode(Index)
  NodeIndex()
  Root()
  LastNode()
  Parent()
  FirstChild()
  LastChild()
  NextSibling()
  PrevSibling()
  ;Andere
  CountNodes()
  NodeLevel()
  NodeChilds()
  IsLeaf()
EndInterface

Structure TreeFunctions
  Adr.l[SizeOf(Tree)/4]
EndStructure

Structure TreeObject
  *VTable.TreeFunctions
  
  *_current_item.Node
  *_first_item.Node
  
  *_current_node.Node
  *_root.Node
  
  BSize.l
  Nodes.l
  
  Next_Available.b
  LDes_Available.b
EndStructure

;}-
;{- Variablen

Global *Tree_VTable.TreeFunctions

;}-
;{- Declares

Declare.l NewTree(BlockSize)
Declare   DestroyTree(*Object.TreeObject)

Declare.l M_Tree_AddNode(*Object.TreeObject, Flags)
Declare   M_Tree_DeleteNode(*Object.TreeObject)
Declare   M_Tree_Clear(*Object.TreeObject)
Declare.l M_Tree_Node(*Object.TreeObject)
Declare.l M_Tree_NextNode(*Object.TreeObject)
Declare.l M_Tree_PreviousNode(*Object.TreeObject)
Declare   M_Tree_ChangeNode(*Object.TreeObject, Node)
Declare.l M_Tree_Root(*Object.TreeObject)
Declare.l M_Tree_LastNode(*Object.TreeObject)
Declare.l M_Tree_Parent(*Object.TreeObject)
Declare.l M_Tree_FirstChild(*Object.TreeObject)
Declare.l M_Tree_LastChild(*Object.TreeObject)
Declare.l M_Tree_NextSibling(*Object.TreeObject)
Declare.l M_Tree_PrevSibling(*Object.TreeObject)
Declare.l M_Tree_CountNodes(*Object.TreeObject)
Declare.l M_Tree_NodeLevel(*Object.TreeObject)
Declare.l M_Tree_NodeChilds(*Object.TreeObject)
Declare   M_Tree_CopyNode(*Object.TreeObject, SourceNode, TargetNode)
Declare   M_Tree_SwapNodes(*Object.TreeObject, Node1, Node2)
Declare.l M_Tree_SelectNode(*Object.TreeObject, Index)
Declare.l M_Tree_NodeIndex(*Object.TreeObject)
Declare.b M_Tree_IsLeaf(*Object.TreeObject)

Declare   Tree_CreateVTable()
Declare.l Tree_JumpToNextItem(*Object.TreeObject)
Declare   Tree_Unlink_Item(*Object.TreeObject)
Declare.l Tree_Set_Next(*Object.TreeObject, *_parent.Node)
Declare   Tree_Set_LDes(*Object.TreeObject)

;}-
;{- Konstruktor/Destruktor

Procedure.l NewTree(BlockSize)
  If *Tree_VTable=0 : Tree_CreateVTable() : EndIf
  
  *Object.TreeObject=AllocateMemory(SizeOf(TreeObject))
  *Object\VTable    =*Tree_VTable
  *Object\BSize     =BlockSize
  
  ProcedureReturn *Object
EndProcedure

Procedure DestroyTree(*Object.TreeObject)
  M_Tree_Clear(*Object)
  FreeMemory(*Object)
EndProcedure

;}-
;{- Methoden

Procedure.l M_Tree_AddNode(*Object.TreeObject, Flags)
  DefType.Node *_new_node, *_next_item, *_parent, *_prev_sibling
  
  Select Flags
    Case #TREE_AsChild   : *_parent=*Object\_current_node
    Case #TREE_AsSibling : *_parent=*Object\_current_node\_parent
    Default              : *_parent=Flags-SizeOf(Node)
  EndSelect
  
  *_new_node=AllocateMemory(SizeOf(Node)+*Object\BSize) : If *_new_node
    
    If *Object\Nodes 
      If *Object\_current_item=0 : *Object\_current_item=*Object\_first_item : EndIf
      
      *_new_node\_prev_item   =*Object\_current_item
      *_next_item             =*Object\_current_item\_next_item
      If *_next_item
        *_next_item\_prev_item=*_new_node
        *_new_node\_next_item =*_next_item
      EndIf
      *Object\_current_item\_next_item=*_new_node
    Else
      *Object\_first_item=*_new_node
    EndIf
    
    *_new_node\_parent=*_parent : If *_parent
      *_parent\Childs+1
      *_new_node\Level=*_parent\Level+1
    Else
      *Object\_root   =*_new_node
    EndIf
    
    *Object\_current_item=*Object\_first_item
    Repeat
      If *Object\_current_item\_parent=*_parent And *Object\_current_item<>*_new_node
        *_prev_sibling=*Object\_current_item 
        Break
      EndIf
    Until Tree_JumpToNextItem(*Object)=0
    
    If *_prev_sibling
      *_new_node\_prev_sibling    =*_prev_sibling\_prev_sibling
      *_prev_sibling\_prev_sibling=*_new_node
    Else
      *_new_node\_prev_sibling    =*_new_node 
    EndIf
    
    *Object\_current_item=*_new_node
    *Object\_current_node=*_new_node
    *Object\Next_Available =#False
    *Object\LDes_Available =#False
    *Object\Nodes+1
    
  EndIf
  
  ProcedureReturn *_new_node
EndProcedure

Procedure M_Tree_DeleteNode(*Object.TreeObject)
  DefType.Node *_parent, *_current_node, *_current_item
  
  If *Object\Next_Available=#False : Tree_Set_Next(*Object, 0) : EndIf
  If *Object\LDes_Available=#False : Tree_Set_LDes(*Object)    : EndIf
  
  *_parent=*Object\_current_node\_parent
  If *_parent
    
    If *Object\_current_node\Childs
      *_current_node=*Object\_current_node\_next
      
      While *_current_node And Last.b=#False
        If *_current_node=*Object\_current_node\_last_descendant : Last=#True : EndIf
        
        *_current_item   =*_current_node 
        Tree_Unlink_Item(*_current_item)
        *_current_node   =*_current_node\_next
        FreeMemory(*_current_item)
        
        *Object\Nodes-1
      Wend
      
      Tree_Set_Next(*Object, 0)
    EndIf
    
    If *_parent\Childs>1
      *_current_node=*Object\_current_node\_next
      If *_current_node=0 Or *_current_node\_parent<>*_parent
        *_parent\_next\_prev_sibling=*Object\_current_node\_prev_sibling
      Else
        *_current_node\_prev_sibling=*Object\_current_node\_prev_sibling
      EndIf 
    EndIf
    
    *_current_node=*Object\_current_node\_parent
    If *_current_node
      If *_current_node\_next=*Object\_current_node
        *_current_node\_next=0
      Else
        *Object\_current_node\_prev_sibling\_last_descendant\_next=0
      EndIf
    EndIf
    
    *_current_item=*Object\_current_node
    Tree_Unlink_Item(*_current_item)
    FreeMemory(*_current_item)
    *Object\_current_node=*_parent
    
    *_parent\Childs-1
    *Object\Nodes-1
    *Object\Next_Available=#False
    *Object\LDes_Available=#False
    
  Else
    M_Tree_Clear(*Object)
  EndIf 
EndProcedure

Procedure M_Tree_Clear(*Object.TreeObject)
  DefType.Node *_next_item
  
  *Object\_current_item=*Object\_first_item
  
  While *Object\_current_item
    *_next_item          =*Object\_current_item\_next_item
    FreeMemory(*Object\_current_item)
    *Object\_current_item=*_next_item
  Wend
  
  *Object\Nodes        =0
  *Object\_root        =0
  *Object\_current_node=0
EndProcedure

Procedure.l M_Tree_Node(*Object.TreeObject)
  ProcedureReturn *Object\_current_node+SizeOf(Node)
EndProcedure

Procedure.l M_Tree_NextNode(*Object.TreeObject)
  DefType.Node *_next
  
  If *Object\Next_Available=#False : Tree_Set_Next(*Object, 0) : EndIf
  
  *_next=*Object\_current_node\_next
  If *_next : *Object\_current_node=*_next : EndIf
  
  ProcedureReturn *_next
EndProcedure

Procedure.l M_Tree_PreviousNode(*Object.TreeObject)
  DefType.Node *_prev
  
  If *Object\Next_Available=#False : Tree_Set_Next(*Object, 0) : EndIf
  If *Object\LDes_Available=#False : Tree_Set_LDes(*Object)    : EndIf
  
  If *Object\_current_node\_parent
    If *Object\_current_node\_parent\_next=*Object\_current_node
      *_prev=*Object\_current_node\_parent
    Else
      *_prev=*Object\_current_node\_prev_sibling\_last_descendant
    EndIf
  EndIf
  
  If *_prev : *Object\_current_node=*_prev : EndIf
  
  ProcedureReturn *_prev
EndProcedure

Procedure M_Tree_ChangeNode(*Object.TreeObject, Node)
  *Object\_current_node=Node-SizeOf(Node)
EndProcedure

Procedure.l M_Tree_Root(*Object.TreeObject)
  *Object\_current_node=*Object\_root
  ProcedureReturn *Object\_root
EndProcedure

Procedure.l M_Tree_LastNode(*Object.TreeObject)
  If *Object\Next_Available=#False : Tree_Set_Next(*Object, 0) : EndIf
  If *Object\LDes_Available=#False : Tree_Set_LDes(*Object)    : EndIf
  
  *Object\_current_node=*Object\_root\_last_descendant
  
  ProcedureReturn *Object\_current_node
EndProcedure

Procedure.l M_Tree_Parent(*Object.TreeObject)
  DefType.Node *_parent
  
  *_parent=*Object\_current_node\_parent
  If *_parent : *Object\_current_node=*_parent : EndIf
  
  ProcedureReturn *_parent
EndProcedure

Procedure.l M_Tree_FirstChild(*Object.TreeObject)
  DefType.Node *_node
  
  If *Object\Next_Available=#False : Tree_Set_Next(*Object, 0) : EndIf
  
  If *Object\_current_node\_next And *Object\_current_node\_next\_parent=*Object\_current_node
    *_node               =*Object\_current_node\_next
    *Object\_current_node=*_node
  EndIf
  
  ProcedureReturn *_node
EndProcedure

Procedure.l M_Tree_LastChild(*Object.TreeObject)
  DefType.Node *_node, *_child
  
  *_child=M_Tree_FirstChild(*Object)
  If *_child
    *_node               =*_child\_prev_sibling
    *Object\_current_node=*_node
  EndIf
  
  ProcedureReturn *_node
EndProcedure

Procedure.l M_Tree_NextSibling(*Object.TreeObject)
  DefType.Node *_node
  
  If *Object\Next_Available=#False : Tree_Set_Next(*Object, 0) : EndIf
  If *Object\LDes_Available=#False : Tree_Set_LDes(*Object)    : EndIf
  
  *_node=*Object\_current_node\_last_descendant\_next
  If *_node And *_node\_parent=*Object\_current_node\_parent
    *Object\_current_node=*_node
  Else
    *_node=0
  EndIf
  
  ProcedureReturn *_node
EndProcedure

Procedure.l M_Tree_PrevSibling(*Object.TreeObject)
  DefType.Node *_node
  
  If *Object\Next_Available=#False : Tree_Set_Next(*Object, 0) : EndIf
  
  If *Object\_current_node\_parent And *Object\_current_node\_parent\_next<>*Object\_current_node
    *_node               =*Object\_current_node\_prev_sibling
    *Object\_current_node=*_node
  EndIf
  
  ProcedureReturn *_node
EndProcedure

Procedure.l M_Tree_CountNodes(*Object.TreeObject)
  ProcedureReturn *Object\Nodes
EndProcedure

Procedure.l M_Tree_NodeLevel(*Object.TreeObject)
  ProcedureReturn *Object\_current_node\Level
EndProcedure

Procedure.l M_Tree_NodeChilds(*Object.TreeObject)
  ProcedureReturn *Object\_current_node\Childs
EndProcedure

Procedure.l M_Tree_CopyNode(*Object.TreeObject, SourceNode, TargetNode)
  CopyMemory(SourceNode, TargetNode, *Object\BSize)
EndProcedure

Procedure M_Tree_SwapNodes(*Object.TreeObject, Node1, Node2)
  Temp=AllocateMemory(*Object\BSize)
  
  CopyMemory(Node1, Temp , *Object\BSize)
  CopyMemory(Node2, Node1, *Object\BSize)
  CopyMemory(Temp , Node2, *Object\BSize)
  
  FreeMemory(Temp)
EndProcedure

Procedure.l M_Tree_SelectNode(*Object.TreeObject, Index)
  If *Object\Next_Available=#False : Tree_Set_Next(*Object, 0) : EndIf
  
  *Object\_current_node=*Object\_root
  
  If Index>0 
    For p=1 To Index : *Object\_current_node=*Object\_current_node\_next : Next 
  EndIf
  
  ProcedureReturn *Object\_current_node
EndProcedure

Procedure.l M_Tree_NodeIndex(*Object.TreeObject)
  DefType.Node *_node
  
  If *Object\Next_Available=#False : Tree_Set_Next(*Object, 0) : EndIf
  
  *_node=*Object\_root
  While *_node And *_node<>*Object\_current_node
    *_node=*_node\_next
    Index+1
  Wend
  
  ProcedureReturn Index
EndProcedure

Procedure.b M_Tree_IsLeaf(*Object.TreeObject)
  If *Object\_current_node\Childs=0
    ProcedureReturn #True
  EndIf
EndProcedure

;}-
;{- Prozeduren

Procedure Tree_CreateVTable()
  *Tree_VTable       =AllocateMemory(SizeOf(Tree))
  *Tree_VTable\Adr[p]=@M_Tree_AddNode()      : p+1
  *Tree_VTable\Adr[p]=@M_Tree_DeleteNode()   : p+1
  *Tree_VTable\Adr[p]=@M_Tree_Clear()        : p+1
  *Tree_VTable\Adr[p]=@M_Tree_Node()         : p+1
  *Tree_VTable\Adr[p]=@M_Tree_CopyNode()     : p+1
  *Tree_VTable\Adr[p]=@M_Tree_SwapNodes()    : p+1
  *Tree_VTable\Adr[p]=@M_Tree_NextNode()     : p+1
  *Tree_VTable\Adr[p]=@M_Tree_PreviousNode() : p+1
  *Tree_VTable\Adr[p]=@M_Tree_ChangeNode()   : p+1
  *Tree_VTable\Adr[p]=@M_Tree_SelectNode()   : p+1
  *Tree_VTable\Adr[p]=@M_Tree_NodeIndex()    : p+1
  *Tree_VTable\Adr[p]=@M_Tree_Root()         : p+1
  *Tree_VTable\Adr[p]=@M_Tree_LastNode()     : p+1
  *Tree_VTable\Adr[p]=@M_Tree_Parent()       : p+1
  *Tree_VTable\Adr[p]=@M_Tree_FirstChild()   : p+1
  *Tree_VTable\Adr[p]=@M_Tree_LastChild()    : p+1
  *Tree_VTable\Adr[p]=@M_Tree_NextSibling()  : p+1
  *Tree_VTable\Adr[p]=@M_Tree_PrevSibling()  : p+1
  *Tree_VTable\Adr[p]=@M_Tree_CountNodes()   : p+1
  *Tree_VTable\Adr[p]=@M_Tree_NodeLevel()    : p+1
  *Tree_VTable\Adr[p]=@M_Tree_NodeChilds()   : p+1
  *Tree_VTable\Adr[p]=@M_Tree_IsLeaf()       : p+1
EndProcedure

Procedure.l Tree_JumpToNextItem(*Object.TreeObject)
  DefType.Node *_next_item
  
  *_next_item=*Object\_current_item\_next_item
  If *_next_item
    *Object\_current_item=*_next_item
    ProcedureReturn *_next_item
  Else
    ProcedureReturn 0
  EndIf
EndProcedure

Procedure.l Tree_Unlink_Item(*Item.Node)
  DefType.Node *_current_item
  
  *_current_item=*Item\_next_item
  If *_current_item : *_current_item\_prev_item=*Item\_prev_item : EndIf
  *_current_item=*Item\_prev_item
  If *_current_item : *_current_item\_next_item=*Item\_next_item : EndIf
EndProcedure

Procedure.l Tree_Set_Next(*Object.TreeObject, *_parent.Node)
  DefType.Node *_previous, *_current_node
  
  *_previous=*_parent
  
  *Object\_current_item=*Object\_first_item
  Repeat
    *_current_node=*Object\_current_item
    
    If *_current_node\_parent=*_parent
      If *_previous : *_previous\_next=*_current_node : EndIf
      
      *_previous=Tree_Set_Next(*Object, *_current_node)
      
      *Object\_current_item=*_current_node
    EndIf
  Until Tree_JumpToNextItem(*Object)=0
  
  *Object\Next_Available=#True
  
  ProcedureReturn *_previous
EndProcedure

Procedure Tree_Set_LDes(*Object.TreeObject)
  DefType.Node *_parent, *_current_node
  
  *_current_node=*Object\_root
  
  While *_current_node
    *_parent=*_current_node
    
    While *_parent
      *_parent\_last_descendant=*_current_node
      *_parent                 =*_parent\_parent
    Wend
    
    *_current_node=*_current_node\_next
  Wend
  
  *Object\LDes_Available=#True
EndProcedure

;}-

Da ich bis jetzt noch keine Zeit hatte eine Dokumentation zu schreiben, müsst ihr euch erstmal mit einem kurzem Beispiel zufriedengeben .

Code: Alles auswählen

*Node.LONG

Tree.Tree=NewTree(SizeOf(LONG))

Tree\AddNode(0)               : *Node=Tree\Node() : *Node\l='A'
Tree\AddNode(#TREE_AsChild)   : *Node=Tree\Node() : *Node\l='B'
Tree\AddNode(#TREE_AsChild)   : *Node=Tree\Node() : *Node\l='C'
Tree\Root()
Tree\AddNode(#TREE_AsChild)   : *Node=Tree\Node() : *Node\l='D'
Tree\AddNode(#TREE_AsChild)   : *Node=Tree\Node() : *Node\l='E'
Tree\AddNode(#TREE_AsSibling) : *Node=Tree\Node() : *Node\l='F' 
Tree\AddNode(#TREE_AsSibling) : *Node=Tree\Node() : *Node\l='G'

Tree\Root()
Repeat
  *Node=Tree\Node()
  Debug Space(Tree\NodeLevel()*5)+"Node "+Chr(*Node\l)
Until Tree\NextNode()=0

DestroyTree(Tree)

End

[MVXA]

Finde ich gut .

[Spirit]

Code: Alles auswählen

; Dokumentation
;
; 1.  NewTree(BlockSize)
;   
;   Beschreibung:
;     Erstellt einen neuen Baum. 'BlockSize' gibt die Größe des reservierten Speichers pro Knoten an.
;   
;   Beispiel:
;     
;     *Node.LONG
;     
;     MyTree.Tree=NewTree(SizeOf(LONG))
; 
; 2.  DestroyTree(Tree)
; 
;   Beschreibung:
;     Löscht den Baum und alle seine Knoten und gibt den Speicher frei.
;     Das Baumobjekt ist danach nicht mehr verwendbar. Der Versuch eine Methode dieses Baums aufzurufen
;     wird zu einem Absturz des Programms führen.
; 
;   Beispiel:
;     
;     MyTree.Tree=NewTree(SizeOf(LONG))
;     DestroyTree(MyTree)
; 
; 3.  AddNode(Flags)
; 
;   Beschreibung:
;     Fügt einen neuen Knoten zum Baum hinzu.
;     
;     'Flags' kann folgende Werte annehmen:
;       #TREE_AsChild                  - erstellt den Knoten als Child-Knoten des aktuellen Knotens
;       #TREE_AsSibling                - erstellt den Knoten als Geschwisterknoten des aktuellen Knotens (sollte nicht
;                                        benutzt werden, wenn der aktuelle Knoten der Wurzelknoten ist)
;       Zeiger zu einem anderen Knoten - erstellt den Knoten als Child-Knoten des angegeben Knotens
;       (im gleichen Baum)               (der Zeiger muss auf die Benutzerdaten des Knotens zeigen)
;     
;     Hinweis: Wenn der Baum leer ist, muss AddNode() mit dem #TREE_AsChild Flag aufgerufen 
;     werden, um den Wurzelknoten (Root node) zu erstellen.
; 
;   Rückgabewert:
;     Wenn der neue Knoten hinzugefügt werden konnte, gibt diese Methode einen Wert ungleich Null zurück.
;     Der Wert, den diese Methode zurückgibt, ist ein Zeiger auf den neuen Knoten (siehe Anhang).
; 
; 4.  DeleteNode()
; 
;   Beschreibung:
;     Löscht den aktuellen Knoten.
; 
; 5.  ClearTree()
;   
;   Beschreibung:
;     Löscht alle Knoten des Baums und gibt ihren Speicher frei. Nach dem Aufruf dieser Methode ist der
;     Baum noch benutzbar, aber leer (wie nach dem Erstellen eines Baums).
; 
; 6.  Node()
;   
;   Beschreibung:
;     Diese Methode wird verwendet, um Daten im Baum zu speichern und zu lesen.
; 
;   Rückgabewert:
;     Gibt den Zeiger auf die benutzerdefinierten Daten des aktuellen Knotens zurück.
; 
;   Beispiel:
;       
;       Structure test
;         a.l
;         b.l
;       EndStructure
;       
;       *MyData.test
;       
;       MyTree.Tree=NewTree(SizeOf(test))
;       MyTree\AddNode(#TREE_AsChild)
;       MyTree\AddNode(#TREE_AsChild)
;       
;       *MyData  =MyTree\Node()
;       *MyData\a=1
;       *MyData\b=2
; 
; 7.  CopyNode(SourceNode, TargetNode)
; 
;   Beschreibung:
;     Kopiert die benutzerdefinierten Daten des 'SourceNode' zum 'TargetNode'.
;     'SourceNode' und 'TargetNode' sind Zeiger auf die Knoten und sollten mit der
;     Node() Methode ermittelt werden.
;     
;     Hinweis: Die Knoten müssen sich nicht im selben Baum befinden, es ist also möglich
;     die Daten von einem Baum zum anderen zu kopieren (dazu müssen jedoch beide Bäume die
;     gleiche 'BlockSize' haben)
; 
; 8.  SwapNodes(Node1, Node2)
; 
;   Beschreibung:
;     Vertauscht die angegebenen Knoten 'Node1' und 'Node2'. 'Node1' und 'Node2' sind Zeiger
;     auf die Knoten und sollten mit der Node() Methode ermittelt werden.
;     
;     Hinweis: Die Knoten müssen sich nicht im selben Baum befinden, es ist also möglich
;     die Knoten zwischen zwei Bäumen auszutauschen (dazu müssen jedoch beide Bäume die
;     gleiche 'BlockSize' haben)
; 
; 9.  NextNode()
;   
;   Beschreibung:
;     Wechselt zum nächsten Knoten (Preorder), wenn dieser existiert. Ansonsten wird der aktuelle
;     Knoten beibehalten.
; 
;   Rückgabewert:
;     Diese Methode gibt einen Wert ungleich Null zurück, wenn es einen nachfolgenden Knoten gibt.
;     Der Wert, den diese Methode zurückgibt, ist ein Zeiger auf den nächsten Knoten (siehe Anhang).
; 
; 10. PreviousNode()
; 
;   Beschreibung:
;     Wechselt zum vorherigen Knoten (Preorder), wenn dieser existiert. Ansonsten wird der aktuelle
;     Knoten beibehalten.
; 
;   Rückgabewert:
;     Diese Methode gibt einen Wert ungleich Null zurück, wenn es einen vorhergehenden Knoten gibt.
;     Der Wert, den diese Methode zurückgibt, ist ein Zeiger auf den vorherigen Knotem (siehe Anhang).
; 
; 11. ChangeNode(Node)
; 
;   Beschreibung:
;     Ändert den aktuellen Knoten auf den angegebenen neuen Knoten 'Node'. 'Node' ist ein Zeiger auf den
;     neuen Knoten und sollte mit der Node() Methode ermittelt werden.
; 
; 12. SelectNode(Index)
; 
;   Beschreibung:
;     Ändert den aktuellen Knoten auf den Knoten mit dem angegebenen 'Index'. Die Wurzel hat den Index 0.
;     Es sollte kein Index angegeben werden, der außerhalb des Baumes liegt.
; 
;   Rückgabewert:
;     Diese Methode gibt den Zeiger auf den neuen aktuellen Knoten zurück (siehe Anhang).
; 
; 13. NodeIndex()
; 
;   Beschreibung:
;     Diese Methode wird benutzt, um den Index des aktuellen Knotens zu ermitteln (nützlich in Verbindung mit SelectNode()).
; 
;   Rückgabewert:
;     Diese Methode gibt den Index des aktuellen Knotens zurück.
; 
; 14. Root()
; 
;   Beschreibung:
;     Ändert den aktuellen Knoten auf den Wurzelknoten (Root) des Baums.
; 
;   Rückgabewert:
;     Gibt Null zurück, wenn der Knoten nicht existiert, ansonsten wird der Zeiger auf den Knoten zurückgegeben (siehe Anhang).
; 
; 15. LastNode()
; 
;   Beschreibung:
;     Ändert den aktuellen Knoten auf den letzten Knoten im Baum.
; 
;   Rückgabewert:
;     Gibt Null zurück, wenn der Knoten nicht existiert, ansonsten wird der Zeiger auf den Knoten zurückgegeben (siehe Anhang).
; 
; 16. Parent()
; 
;   Beschreibung:
;     Ändert den aktuellen Knoten auf den Elternknoten (Parent) des aktuellen Knotens, wenn dieser existiert, ansonsten wird der
;     aktuelle Knoten nicht geändert.
; 
;   Rückgabewert:
;     Gibt Null zurück, wenn der Knoten nicht existiert, ansonsten wird der Zeiger auf den Knoten zurückgegeben (siehe Anhang).
; 
; 17. FirstChild()
; 
;   Beschreibung:
;     Ändert den aktuellen Knoten auf den ersten Kindknoten (Child) des aktuellen Knotens, wenn dieser existiert, ansonsten wird der
;     aktuelle Knoten nicht geändert.
; 
;   Rückgabewert:
;     Gibt Null zurück, wenn der Knoten nicht existiert, ansonsten wird der Zeiger auf den Knoten zurückgegeben (siehe Anhang).
; 
; 18. LastChild()
; 
;   Beschreibung:
;     Ändert den aktuellen Knoten auf den letzten Kindknoten (Child) des aktuellen Knotens, wenn dieser existiert, ansonsten wird der
;     aktuelle Knoten nicht geändert.
; 
;   Rückgabewert:
;     Gibt Null zurück, wenn der Knoten nicht existiert, ansonsten wird der Zeiger auf den Knoten zurückgegeben (siehe Anhang).
; 
; 19. NextSibling()
; 
;   Beschreibung:
;     Ändert den aktuellen Knoten auf den nächsten Geschwisterknoten des aktuellen Knotens, wenn dieser existiert, ansonsten wird der
;     aktuelle Knoten nicht geändert.
; 
;   Rückgabewert:
;     Gibt Null zurück, wenn der Knoten nicht existiert, ansonsten wird der Zeiger auf den Knoten zurückgegeben (siehe Anhang).
; 
; 20. PrevSibling()
; 
;   Beschreibung:
;     Ändert den aktuellen Knoten auf den vorherigen Geschwisterknoten des aktuellen Knotens, wenn dieser existiert, ansonsten wird der
;     aktuelle Knoten nicht geändert.
; 
;   Rückgabewert:
;     Gibt Null zurück, wenn der Knoten nicht existiert, ansonsten wird der Zeiger auf den Knoten zurückgegeben (siehe Anhang).
; 
; 21. CountNodes()
; 
;   Beschreibung:
;     Diese Methode wird verwendet, um die Anzahl der Knoten des Baums zu ermitteln. Sie ist nützlich, um herauszufinden, ob der Baum
;     leer ist.
; 
;   Rückgabewert:
;     Gibt die Anzahl der Knoten im Baum zurück.
; 
; 22. NodeLevel()
; 
;   Beschreibung:
;     Diese Methode wird verwendet, um die Tiefe des aktuellen Knotens im Baum zu ermitteln. Die Wurzel hat die Tiefe 0, deren Kindknoten
;     die Tiefe 1, usw.
; 
;   Rückgabewert:
;     Gibt die Tiefe des Knotens im Baum zurück.
; 
; 23. NodeChilds()
; 
;   Beschreibung:
;     Diese Methode wird verwendet, um die Anzahl der Kindknoten des aktuellen Knotens zu ermitteln. Diese Methode zählt nur die Kindknoten,
;     die eine Ebene tiefer liegen, nicht aber deren Kindknoten.
; 
;   Rückgabewert:
;     Gibt die Anzahl der Kindknoten zurück.
; 
; 24. IsLeaf()
; 
;   Beschreibung:
;     Diese Methode wird verwendet, um herauszufinden, ob der aktuelle Knoten ein Blatt ist, also keine Kindknoten hat.
; 
;   Rückgabewert:
;     Gibt 1 zurück, wenn der aktuelle Knoten ein Blatt ist, ansonsten 0.
; 
; Anhang:
; 
;   Nachfolgend wird die Struktur eines Knotens dargestellt:
;   
;   Structure Node
;     *_parent.Node
;     *_prev_sibling.Node
;     *_next.Node
;     *_last_descendant.Node
;     
;     *_next_item.Node
;     *_prev_item.Node
;     
;     Childs.l
;     Level.l
;     
;     ;Benutzerdefinierte Daten
;   EndStructure
; 
;   Die Zeiger eines Knotens sollten nicht verändert werden, da dies die Struktur des Baums zerstört und ihn damit
;   unbrauchbar macht.