Graphing a Binary Tree (Due tomorrow)

[Tec-Nico]

Lets say I have developed a Binary Tree structure in a module creating my own user defined Type named "BTree"...

My problem is... How can I graph this tree I created?
I need to be able to graph or paint at least 4 levels. I would appreciate help.

Thank you in advance

This would be somewhat what I would need...
O
/ \
O O
/ \ / \
O O O O
/ \ / \ / \ / \
O O O OO OO O

[jim mcnamara]

That's what the treeview control is meant for.

[Tec-Nico]

I know, but this is a homework and I cannot go to my professor showing I used a control for what I was supposed to program...

[riis]

What would you like to know?
Learn how you can draw pictures in VB or need to calculate the coordinates of items in the binary tree?

The first one has been explained many times in this forum.
The second one is pretty easy.
Suppose you have a drawing box. W is the width. H is the height of every generation (level). The location of the first item will be (1/2 * W, H)
Of the second level the coordinates will be (1/4 * W, 2 * H) and (3/4 * W, 2 * H).
Third level: (1/8 * W, 3 * H), (3/8 * W, 3 * H), etc, etc.
Fourth level: (1/16 * W, 4 * H), etc.
Good luck!

[riis]

You can also do this trick with paper.
The orientation should be landscape (will be easier to fold)
Draw four horizontal lines on it, spaced evenly. Fold your paper one time vertically. Unfold the paper. At the crossing line of the topmost line and the fold, draw a circle.
Now, fold the paper again, using the same fold. Fold the paper another time, so you will have 3 parallel vertical folds. Unfold your paper. Draw circles where the first and third folds cross the second topmost line.
Refold your paper twice, using the same folds. Fold it yet another time. Unfold it, and you'll see seven folds. Mark the crossings of the first, third, fifth and seventh folds (these are the new folds) and the third topmost line.
The fourth time should be easy enough now

You can do this for as many levels as you want, supposedly that you can still fold the paper more
When you're done, draw a line from the topmost circle, to both circles at the next level. Those two circles should be connected with the four at the third level, two lines per second-level circle. Etc.

[techgnome]

Originally posted by riis
What would you like to know?
Learn how you can draw pictures in VB or need to calculate the coordinates of items in the binary tree?

The first one has been explained many times in this forum.
The second one is pretty easy.
Suppose you have a drawing box. W is the width. H is the height of every generation (level). The location of the first item will be (1/2 * W, H)
Of the second level the coordinates will be (1/4 * W, 2 * H) and (3/4 * W, 2 * H).
Third level: (1/8 * W, 3 * H), (3/8 * W, 3 * H), etc, etc.
Fourth level: (1/16 * W, 4 * H), etc.
Good luck!

I think I saw a pattern developing here......

Given L = Level; H = Generation Height; W = Width of drawing area

x = ( 1/(2^(L+1)) * W
y = H * L

But that only helps to get the co-ords of the left most node on each level.....
maybe some one else can take it from there........

[Tec-Nico]

Don't think I sat down here waiting on you all to answer my question, I also developed my own trick...

But there is a little detail on my trick and I wonder if it happens with yours too... What about if the tree is not completely filled? I mean, think there are gaps and some nodes have just one child. This is the code I used:

Public Sub ShowNodesInForm(MeForm As Form, TrN As Variant, ShpN As Variant, LnN As Variant)
If Tree.Valid = True Then
 Dim i As Long
 
 Set TreeN = TrN 'A label control Array
 Set ShapeN = ShpN 'A shape control Array
 Set LineN = LnN 'A line control Array
 
 DistDefault = TreeN(0).Width
 
 Set OCode = New OrdersCode 'This is to be able to call the code from the InOrder
 CTree = Tree
 
 ReDim LastX(Tree.Height + 1)
 ReDim DistNodes(Tree.Height + 1)
 ReDim PosY(Tree.Height + 1)
 
 For i = 1 To Tree.Height + 1
  DistNodes(i) = CalcDNode(Tree, i)
  LastX(i) = CalcFirstX(DistNodes(i))
  PosY(i) = 2 * DistDefault * (i - 1)
 Next i
  
 InOrden Tree.Node, Tree.Root, OCode, "PrintNode"
 
Else
 MsgBox "Error, the specified Tree is invalid", vbCritical, "Error"
End If
End Sub
 
Public Function CalcFirstX(DistNodes As Single) As Single
If DistNodes = DistDefault Then
 CalcFirstX = 0
Else
 CalcFirstX = (DistNodes - 1) / 2
End If
End Function
 
Public Function CalcDNode(Arbol As BTree, Level As Long) As Single
If Arbol.Height - Level = -1 Then
 CalcDNode = DistDefault
Else
 CalcDNode = 2 * CalcDNode(Arbol, Level + 1) + 1
End If
End Function
 
Public Sub InOrden(n() As BTNode, Num As Long, MyObject As Object, MyFun As String)
If n(Num).ChildLeft >= 0 Then InOrden n(), n(Num).ChildLeft, MyObject, MyFun
CallByName MyObject, MyFun, VbMethod, Num
If n(Num).ChildRight >= 0 Then InOrden n(), n(Num).ChildRight, MyObject, MyFun
End Sub
 
'This is in the Class Module "OrdersCode"
 
Public Sub PrintNode(Num As Long)
Dim Lvl As Long
Lvl = CTree.Node(Num).Level
 
If Lvl <= 4 Then
 TreeN(CG).Left = LastX(Lvl) '+ DistNodes(Lvl)
 TreeN(CG).Top = PosY(Lvl)
 ShapeN(CG).Left = TreeN(CG).Left
 ShapeN(CG).Top = TreeN(CG).Top
 'LineN(CG).Left = True " As you can see, I am working still on this
 'LineN(CG).Top = True " Still working, don't mind this code
 
 LastX(Lvl) = TreeN(CG).Left + DistNodes(Lvl)
 MsgBox "LastX(" & Lvl & ") = TreeN(" & CG & ") [" & TreeN(CG) & "] + DistNodes(" & Lvl & ") [" & DistNodes(Lvl) & "] = " & LastX(Lvl)
 
 TreeN(CG).Visible = True
 TreeN(CG).Caption = CTree.Node(Num).Info(0)
 ShapeN(CG).Visible = True
 'LineN(CG).Visible = True
 
 CG = CG + 1
End If
End Sub

[riis]

If a node has zero or one children, then skip the missing children. That shouldn't be a problem, since you don't need extra space.
Of course you can make it so that when a node has only one child, the X-position of the child is the same as its parent.

[Tec-Nico]

Because of you two I could develop my own code. But I would like to see what you stated as pseudo or already coded, it sounds interesting.

Here I will add the code I used... It was simple... I felt bad I did not think about it before. I used the following reasoning:

1.- Print the Root (Calculate where the root should be using the levels and the following recursive formula: Dist(level) = 2*Dist(level+1) - 1*Unit. The exit condition would be If the level given is the maximum level of the tree, then: Dist(MaxLevel) = 1*Unit. Then simply draw it in y = 0*unit, x = (Dist(level) -1 * unit)/2 where level will be 1, of course.)
2.- Now you go through the tree using the Pre-Order starting from the root and:
a) If the node has a Left Child, print the Node in y = 2*(level-1) units and x = node's Parent Left + 1/2* node's Parent Width - (Dist(level) - 1 * unit)/2. Now point a line from the node's Parent to the node.
b) If the node has a Right Child, print the node in the same y, and x = node's Parent Left + 1/2 * node's Parent Width + (Dist(level) - 1 * unit)/2. Now point a line from the node's Parent to the node.

Anyway, a doubt comes to me... What can I do if the nodes are graphied out of the form? Isn't there a way to be able to add scrolling bars so you can see all the way right until the right-most node and all the way down until the down-most node?

And also, how can I create another instance of the Label array I am using? Thanks in advance...

Code:

Public Tree As BTree 'The Tree created by Me
Public CTree As BTree 'The Tree created by Me
Public OCode As Object
 
Public CG As Integer
Public TreeN As Variant 'Label Array to contain the Info
Public ShapeN As Variant 'Shape Array: Circle
Public LineN As Variant 'Line Array to point to the "node"
 
Public DistDefault As Single
Public MaxLevel As Long
 
Public LastX() As Single
Public DistNodes() As Single
Public PosY() As Single
 
Public Sub ShowNodesInForm(MeForm As Form, TrN As Variant, ShpN As Variant, LnN As Variant)
If Tree.Valid = True Then
 Dim i As Long
 
 Set TreeN = TrN
 Set ShapeN = ShpN
 Set LineN = LnN
 
 DistDefault = TreeN(0).Width
 
 Set OCode = New OrdersCode
 CTree = Tree
 
 'MaxLevel = Tree.Height + 1 'Normal
 MaxLevel = 4
 
 ReDim LastX(MaxLevel)
 ReDim DistNodes(MaxLevel)
 ReDim PosY(MaxLevel)
 
 For i = 1 To MaxLevel
  DistNodes(i) = CalcDNode(Tree, i)
  LastX(i) = CalcFirstX(DistNodes(i))
  PosY(i) = 2 * DistDefault * (i - 1)
 Next i
  
  CG = 0
  
  Tree.Node(Tree.Root).GraphNode = CG
  TreeN(CG).Left = LastX(1)
  TreeN(CG).Top = (Tree.Node(Tree.Root).Level - 1) * 2 * DistDefault
  ShapeN(CG).Left = TreeN(CG).Left
  ShapeN(CG).Top = TreeN(CG).Top
  
  TreeN(CG).Top = TreeN(CG).Top + 90
  
  TreeN(CG).Visible = True
  TreeN(CG).Caption = Tree.Node(Tree.Root).Info(0)
  ShapeN(CG).Visible = True
  LineN(CG).Visible = False
  CG = CG + 1
 
 PreOrden Tree.Node, Tree.Root, OCode, "PrintNode"
Else
 MsgBox "Error, not a valid Tree", vbCritical, "Error"
End If
End Sub
 
Public Function CalcFirstX(DistNodes As Single) As Single
If DistNodes = DistDefault Then
 CalcFirstX = 0
Else
 CalcFirstX = (DistNodes - 1 * DistDefault) / 2
End If
End Function
 
Public Function CalcDNode(Arbol As BTree, Nivel As Long) As Single
If MaxLevel - Nivel = 0 Then
 CalcDNode = DistDefault
Else
 CalcDNode = (2 * CalcDNode(Arbol, Nivel + 1)) + 1 * DistDefault
End If
End Function
 
Public Sub PreOrden(n() As BTNode, Num As Long, MyObject As Object, MyFun As String)
CallByName MyObject, MyFun, VbMethod, Num 'PreOrder
If n(Num).ChildLeft >= 0 Then PreOrden n(), n(Num).ChildLeft, MyObject, MyFun
If n(Num).ChildRight >= 0 Then PreOrden n(), n(Num).ChildRight, MyObject, MyFun
End Sub
 
'---- This is inside of a Class Module called "OrdersCode" ----
 
Public Sub PrintNode(Num As Long)
Dim Lvl As Long
 
With CTree
Lvl = .Node(Num).Level
 
If Lvl < MaxLevel Then
 Dim Dist As Single
 Dim ChL As Long
 Dim ChR As Long
 
 ChL = .Node(Num).ChildLeft
 ChR = .Node(Num).ChildRight
 
 If ChL <> -1 Then
  Dist = (DistNodes(Lvl + 1) + 1 * DistDefault) / 2
 
  .Node(ChL).GraphNode = CG
  TreeN(CG).Left = TreeN(.Node(Num).GraphNode).Left - Dist
  TreeN(CG).Top = (.Node(ChL).Level - 1) * 2 * DistDefault
  ShapeN(CG).Left = TreeN(CG).Left
  ShapeN(CG).Top = TreeN(CG).Top
  LineN(CG).X1 = TreeN(CG).Left + (DistDefault / 2)
  LineN(CG).X2 = TreeN(.Node(Num).GraphNode).Left + (DistDefault / 2)
  LineN(CG).Y1 = TreeN(CG).Top
  LineN(CG).Y2 = TreeN(.Node(Num).GraphNode).Top + (DistDefault / 2)
  
  TreeN(CG).Top = TreeN(CG).Top + 90
  
  TreeN(CG).Visible = True
  TreeN(CG).Caption = .Node(ChL).Info(0)
  ShapeN(CG).Visible = True
  LineN(CG).Visible = True
  CG = CG + 1
 End If
 
 If ChR <> -1 Then
  .Node(ChR).GraphNode = CG
  TreeN(CG).Left = TreeN(.Node(Num).GraphNode).Left + Dist
  TreeN(CG).Top = (.Node(ChR).Level - 1) * 2 * DistDefault
  ShapeN(CG).Left = TreeN(CG).Left
  ShapeN(CG).Top = TreeN(CG).Top
  LineN(CG).X1 = TreeN(CG).Left + (DistDefault / 2)
  LineN(CG).X2 = TreeN(.Node(Num).GraphNode).Left + (DistDefault / 2)
  LineN(CG).Y1 = TreeN(CG).Top
  LineN(CG).Y2 = TreeN(.Node(Num).GraphNode).Top + (DistDefault / 2)
  
  TreeN(CG).Top = TreeN(CG).Top + 90
  
  TreeN(CG).Visible = True
  TreeN(CG).Caption = .Node(ChR).Info(0)
  ShapeN(CG).Visible = True
  LineN(CG).Visible = True
  CG = CG + 1
 End If
  
End If
 
End With
End Sub

[Tec-Nico]

Ignore my other doubts, I would just like to see the other way to graph the nodes in pseudo-code or in VB Code...

My method now is working and I could post "Solved" but before that... I would love to see your method working too. I consider it very interesting