Binärer Baum

[Karl]

Hallo,

kann man eigentlich mit Bordmitteln binäre Bäume in PB erstellen?

Sowas wie "new" oder "dispose" scheint es wohl nicht zu geben.

Gruß Karl

[Zaphod]

Da gibt es trotzdem einige Möglichkeiten. Prinzipiel könnte ich mir vorstellen, dass man einen Binärbaum auch in einer linkedlist abbilden könnte, was aber auf jeden fall geht: einen Speicherbereich Alloziieren und werte selber setzen. Also ein node sind dann bei einem 32 bit rechner optimalerweise 12 byte (drei longs, die sind am schnellstens referenzierbar). Der erste long-wert ist der Wert der an der Knotenstelle gespeichert ist. Der zweite long ist die Position des linken Knotens im Speicherbereich. Der dritte long ist die Position des rechten Knotens im Speicherbereich.

Ich hab das mal in Assembly gemacht, weiß daher definitiv dass das so funktioniert und auch ziemlich flott ist.

[Froggerprogger]

einen vollständigen binären Baum mit vorher festgelegter maximaler Tiefe kann man auch einfach und effizient auf ein Array abbilden.

Wurzel: 0
Linkes Kind: 1
Rechtes Kind: 2
Linkes Kind des Linken Kindes: 3
Rechtes Kind des Linken Kindes: 4
Linkes Kind des Rechten Kindes: 5
Rechtes Kind des Rechten Kindes: 6
...

Also Ebene für Ebene.
Die Blätter befinden sich dann an den Stellen #Arraysize/2 - #Arraysize
Zum Linken Kind des Knotens i navigiert man durch: 2*i+1
Zum Rechten Kind des Knotens i navigiert man durch: 2*i+2
Zum Eltern des Knotens i navigiert man durch: floor((i-1)/2)


Allgemein einfach eine Datenstruktur Node, z.B. so:

Code: Alles auswählen

Structure NODE
  parent.l
  leftChild.l
  rightChild.l
  value.l
EndStructure

parent und left/rightChild halten einfach einen Pointer auf die entsprechende NODE-Instanz.

[Karl]

Danke, ich werde mal beide Varianten austesten.

Gruß Karl

[edel]

Code: Alles auswählen

  Structure _RECT 
    X.l
    Y.l
    cx.l
    cy.l 
  EndStructure
  Structure _OBJECT 
    *_NEXT._OBJECT
    *_PREV._OBJECT
    *_OWNER._OBJECT
    *_CHILD._OBJECT
    TYP.l
  EndStructure
  Structure _WINDOW Extends _OBJECT
    TITLE.s
    FLAGS.l
    rect._RECT
  EndStructure
  Structure _BUTTON Extends _OBJECT
    TITLE.s
    FLAGS.l
    rect._RECT
  EndStructure
  Declare.l Q_CreateWindow(X,Y,cx,cy,TITLE.s,FLAGS)
  Declare.l Q_CreateButton(X,Y,cx,cy,parent,TITLE.s,FLAGS)
  Declare.l AddObject(*OBJECT._OBJECT) 
  Declare.l AddChild(*OBJECT._OBJECT,*CHILD._OBJECT)
  #TYP_WINDOW = 1
  #TYP_BUTTON = 2
  
  Global *WINDOWLIST._OBJECT
  
  Procedure.l Q_CreateWindow(X,Y,cx,cy,TITLE.s,FLAGS)
    *TEMP._WINDOW   = AllocateMemory(SizeOf(_WINDOW))
    *TEMP\_NEXT     = #Null
    *TEMP\_PREV     = #Null
    *TEMP\_OWNER    = *TEMP
    *TEMP\_CHILD    = #Null 
    *TEMP\rect\X    = X
    *TEMP\rect\Y    = Y
    *TEMP\rect\cx   = cx
    *TEMP\rect\cy   = cy
    *TEMP\TITLE     = TITLE
    *TEMP\FLAGS     = FLAGS
    *TEMP\TYP = #TYP_WINDOW
    
    If AddObject(*TEMP) <> 0  
      ProcedureReturn *TEMP
    Else
      ProcedureReturn 0
    EndIf 
    
  EndProcedure
  
  Procedure.l Q_CreateButton(X,Y,cx,cy,parent,TITLE.s,FLAGS)
    *TEMP._BUTTON   = AllocateMemory(SizeOf(_BUTTON))
    *TEMP\_NEXT     = #Null
    *TEMP\_PREV     = #Null
    *TEMP\_OWNER    = #Null
    *TEMP\_CHILD    = #Null 
    *TEMP\rect\X    = X
    *TEMP\rect\Y    = Y
    *TEMP\rect\cx   = cx
    *TEMP\rect\cy   = cy
    *TEMP\TITLE     = TITLE
    *TEMP\FLAGS     = FLAGS
    *TEMP\TYP = #TYP_BUTTON
    
    If AddChild(parent,*TEMP) <> 0 
      ProcedureReturn *TEMP
    Else
      ProcedureReturn 0
    EndIf   
    
  EndProcedure
  
  Procedure.l AddObject(*OBJECT._OBJECT) 
    If *WINDOWLIST = 0 
      *WINDOWLIST = *OBJECT
    Else
      *OBJECT\_NEXT = *WINDOWLIST
      *WINDOWLIST\_PREV = *OBJECT
      *WINDOWLIST = *OBJECT
    EndIf
    ProcedureReturn *OBJECT
  EndProcedure
  Procedure.l AddChild(*OBJECT._OBJECT,*CHILD._OBJECT)
    
    If *CHILD = 0 Or *OBJECT = 0
      ProcedureReturn 0 
    EndIf   
    
    If *OBJECT\_CHILD = #Null
      *OBJECT\_CHILD = *CHILD 
      *CHILD\_OWNER  = *OBJECT
      *CHILD\_NEXT   = #Null
      *CHILD\_PREV   = #Null
    Else
      *CHILD\_NEXT = *OBJECT\_CHILD
      *OBJECT\_CHILD\_PREV  = *CHILD
      *CHILD\_OWNER         = *OBJECT
      *OBJECT\_CHILD        = *CHILD
      *CHILD\_PREV          = #Null
    EndIf
    ;*CHILD\_CHILD = #Null 
    
    ProcedureReturn *CHILD
  EndProcedure
  *Window_1 = Q_CreateWindow(10,10,500,500,"fenster 1",0)
  *Window_2 = Q_CreateWindow(10,10,500,500,"fenster 2",0)
  *Button_1 = Q_CreateButton(10,10,100,25,*Window_1,"Button 1",0)
  *Button_2 = Q_CreateButton(10,10,100,25,*Window_1,"Button 2",0)
  *Button_2 = Q_CreateButton(10,10,100,25,*Window_2,"Button 1",0)
  Debug "Begin Debug"
  Debug "-----------"
  
  GLOBAL Dim OBJECTTYPES.s(20)
  OBJECTTYPES(#TYP_WINDOW) = "WINDOW"
  OBJECTTYPES(#TYP_BUTTON) = "BUTTON"
  
  Global Instanz
  Instanz = 0
  
  Procedure ExamineObjects(*_Base._OBJECT)
    While *_Base <> #Null
      Debug Space(Instanz*3)+"Objekt   : "+Str(*_Base)+" TYP : "+OBJECTTYPES(*_Base\TYP)
  ;   If *_Base\_NEXT : Debug Space(Instanz*3)+"|- _NEXT : "+Str(*_Base\_NEXT) : EndIf
  ;   If *_Base\_PREV : Debug Space(Instanz*3)+"|- _PREV : "+Str(*_Base\_PREV) : EndIf
  ;   If *_Base\_CHILD : Debug Space(Instanz*3)+"|- CHILD : "+Str(*_Base\_CHILD) : EndIf
  ;   If *_Base\_OWNER : Debug Space(Instanz*3)+"|- OWNER : "+Str(*_Base\_OWNER): EndIf
      If *_Base\_CHILD <> #Null
        Instanz + 1 
        ExamineObjects(*_Base\_CHILD)
        Instanz - 1
      EndIf
      *_Base = *_Base\_NEXT
    Wend
  EndProcedure
  
  ExamineObjects(*WINDOWLIST)   

Vielleicht kannst du dir daraus was basteln.