PureBasic Forums - English

Posted: **Fri Aug 18, 2006 10:08 am**

Code updated For 5.20+

This is something I created helping some one out with creating such a system.
It's loaded with comments to help understanding how everything works.

the idea of this tree system is that you have a node and it can have a parent and n amount of children (n being the #MaxChildren constant) so nodes are connected by parent and children pointers so you could follow the tree down each descent or up by parent but linkage is the key.

you could have muiltable trees, asymetical trees, or even muiltable linked trees (network tree?).

this is a pretty flexable type of code,
your welcome to break it and help improve.

Code: Select all

#MaxChildren = 4

Structure Person ;this can hold other things that you fin more sutiable
  Name.s{30} ;this is just a work around for the pointer string issue
  ;instead of copying the pointer to the string I copy the data
  ;this is because if the example changes the string while the pointer is still attached
  ;so the entire tree inheirites 2 strings... Bad
  ;so keep that in mind
EndStructure

Structure Node
  NodeData.Person ;this holds your NodeData for the node
  *Parent.Node ;this holds the parents node
  *Child.Node[#MaxChildren] ;this holds the child nodes
  ;arn't Pointers Wonderful?
EndStructure

Global NewList Tree.Node()

Procedure SpawnRootNode(*NodeData.Person)
  ;Spawns a root Node otherwise known as a Orphined node
  ;With Optional NodeData
  AddElement(Tree())
  CopyMemory(*NodeData, @Tree()\NodeData, SizeOf(Person)) ;This Node May Contain NodeData Like Any Other Node
  Tree()\Parent = #Null ;Roots Always Are Null
  ;Leave All Children NULL
  ProcedureReturn @Tree() ;Return Node ID
EndProcedure

Procedure SpawnChild(*ParentNode.Node, *ChildNodeData.Person)
  For Index = 0 To #MaxChildren - 1
    If *ParentNode\Child[Index] = #Null
      Child = Index
      Found = #True
      Break
    EndIf
  Next
  
  If Found = #False
    ;Could not Find a Open Child
    ProcedureReturn #False
  EndIf
  
  AddElement(Tree()) ;create child
  *ParentNode\Child[Child] = @Tree() ;set child
  CopyMemory(*ChildNodeData, Tree()\NodeData, SizeOf(Person)) ;set NodeData
  Tree()\Parent = *ParentNode ;set parent
  ProcedureReturn @Tree() ;Return Child ID
EndProcedure

Procedure SetNodeData(*Node.Node, *NodeData.Person)
  CopyMemory(*NodeData, *Node\NodeData, SizeOf(Person)) ;put data into the node
EndProcedure

Procedure GetNodeData(*Node.Node)
  ProcedureReturn *Node\NodeData ;get the pointer to the node data
EndProcedure

Procedure SetNodeParent(*Node.Node, *ParentNode.Node)
  *Node\Parent = *ParentNode ;give this child a parent :)
EndProcedure

Procedure GetNodeParent(*Node.Node)
  ProcedureReturn *Node\Parent ;retrive the parent node
EndProcedure

Procedure SetNodeChild(*Node.Node, *ChildNode.Node, *Child)
  *Node\Child[Child] = *ChildNode ;adopt this child node
EndProcedure

Procedure GetNodeChild(*Node.Node, Child.l)
  ProcedureReturn *Node\Child[Child] ;get the child
EndProcedure

Procedure WalkChildrenNodes(*Base.Node)
  ;walks throught all children of the tree
  ;I guess if you want to render the tree you could use a static variable to monitor the depth 'level' of the tree
  ;enumerate the children draw evenly spaced circles at the 'level' then draw lines between the child and parent 
  For Index = 0 To #MaxChildren - 1
    If *Base\Child[Index] <> #Null
      ;do somthing here
      Debug *Base\NodeData\Name + " Is a Parent Of " + *Base\Child[Index]\NodeData\Name
      ;entering a new level
      WalkChildrenNodes(*Base\Child[Index]) 
    EndIf
  Next
  ;leaving a level
EndProcedure


;Now what you do is to spawn a root
;then spawn it's children

;example with a 3 generation with 2 children each tree
PersonNodeDataOne.Person
PersonNodeDataTwo.Person

PersonNodeDataOne\Name = "AB Root" 

;Root
AB = SpawnRootNode(PersonNodeDataOne)

;Split One
PersonNodeDataOne\Name = "A" 
PersonNodeDataTwo\Name = "B"
SpawnChild(AB, PersonNodeDataOne)
SpawnChild(AB, PersonNodeDataTwo)


;Split Two
PersonNodeDataOne\Name = "C"
PersonNodeDataTwo\Name = "D"
SpawnChild(GetNodeChild(AB, 0), PersonNodeDataOne)
SpawnChild(GetNodeChild(AB, 0), PersonNodeDataTwo)

PersonNodeDataOne\Name = "E"
PersonNodeDataTwo\Name = "F"
SpawnChild(GetNodeChild(AB, 1), PersonNodeDataOne)
SpawnChild(GetNodeChild(AB, 1), PersonNodeDataTwo)

;Split Three
PersonNodeDataOne\Name = "G"
PersonNodeDataTwo\Name = "H"
SpawnChild(GetNodeChild(GetNodeChild(AB, 0), 0), PersonNodeDataOne)
SpawnChild(GetNodeChild(GetNodeChild(AB, 0), 0), PersonNodeDataTwo)

PersonNodeDataOne\Name = "I"
PersonNodeDataTwo\Name = "J"
SpawnChild(GetNodeChild(GetNodeChild(AB, 0), 1), PersonNodeDataOne)
SpawnChild(GetNodeChild(GetNodeChild(AB, 0), 1), PersonNodeDataTwo)

PersonNodeDataOne\Name = "K"
PersonNodeDataTwo\Name = "L"
SpawnChild(GetNodeChild(GetNodeChild(AB, 1), 0), PersonNodeDataOne)
SpawnChild(GetNodeChild(GetNodeChild(AB, 1), 0), PersonNodeDataTwo)

PersonNodeDataOne\Name = "M"
PersonNodeDataTwo\Name = "N"
SpawnChild(GetNodeChild(GetNodeChild(AB, 1), 1), PersonNodeDataOne)
SpawnChild(GetNodeChild(GetNodeChild(AB, 1), 1), PersonNodeDataTwo)
WalkChildrenNodes(AB)
CallDebugger

Posted: **Sat Aug 19, 2006 4:22 pm**

Thanks, its a great code for MLM softwares and binary tree's
Thanks for providing this cool good commented code

PureBasic Forums - English

Binary Tree System

Binary Tree System