Searching through a tree structure

[gohym]

Hi,

I am trying to do some calculations which require some kind of depth 1st search algorithm. I have some ideas as to how to do it, but I think there should be a better way to do it. Hopefully someone can give me some advice. Thanks in advance. FYI, I'm not an expert in coding, would appreciate if replies are simple. Thanks again.

I have a table, tblEvent, with the following columns: EventID, PreEventID, EventType, EventValue, Score

The EventID (1) is related to PreEventID (many) hence forming a tree structure.

What I need to do is to determine TotScore for certain type of events under a specified TopEvent, which can be any event in the table. Note that TotScore = (Sum of score of events with EventType = "CSQ")

Another point to note is that EventType "CSQ" is always at the bottom of the tree, i.e. no other events' PreEventID points to an event with EventType = "CSQ". Furthermore gor each branch in the tree structure there are either 3 OR 4 levels.

Here's a (far from perfect) pseudo code that I came up with:

rst1 = (select events with preevent = TopEvent's EventID)
If Not rst1.eof AND rst1.BOF then 'If there are child events
  Do until rst1.eof
    If EventType = "CSQ" then TotScore = TotScore + Score
    rst2 = (select events with preevent = rst1!EventID)
    If Not rst2.eof AND rst2.BOF then
      Do Until rst2.EOF
        If EventType = "CSQ" then TotScore = TotScore + Score
        rst3 = (select events with preevent = rst2!EventID)
        If Not rst3.eof AND rst3.BOF then
          Do Until rst3.EOF
            If EventType = "CSQ" then TotScore = TotScore + Score
            rst4 = (select events with preevent = rst3!EventID)
            If Not rst4.eof AND rst4.BOF then
              Do Until rst4.EOF
                If EventType = "CSQ" then TotScore = TotScore + Score
              Loop
            End if
            rst4.close
          loop
        end if   
        rst3.close
      Loop
    End If
    rst2.Close
  Loop
End if
rst1.Close

I can see that there are a lot of repetitions, but I am not sure how that can be make full use of.

 

[jmeadows7]

You should really look up tree traversal utilizing either an infix, postfix, or prefix algorithm - depending upon your need. I've written a few in my day to do calculators, relate documents in a knowledge base, etc.

If you can combine these algorithms with a recursive language, it's not too bad of a task.
However, something like this does require a good bit of study, knowledge, and expertise of the algorithms.

If it were easy - everyone would do it - sorry I don't have an easy answer.

 

[gohym]

Hi jmeadows7,

Really appreciate your advice. I will try to do some readings on tree traversal with "infix, postfix or prefix" algo... These terms sound pretty intimidating.

Can you point me to some good resource for my readings?

Thanks!

 

[CajunCenturion]

I would suggest that research recursive algorithms, as they are the standard approach to reading heirarchical structures like a tree or a directory structure and such. I haven't written one for the TreeView control, but here is a recursive directory search routine. The key fact in recursirve algorithms is that each sub-structure, is logically the same as the main structure. A directory contains subdirectories. But each subdirectory is a directory that contains subdirectories. Logically, the same structure.

The same holds true for a Tree-View. Each node of the tree, may just simply be another tree. This code is quite a few years old, but it does recursively traverse through a tree view control.

Private Sub treMusicTree_NodeCheck(ByVal vNod_ThisNode As MSComctlLib.Node)

   If (vNod_ThisNode.Children > 0) Then
      ResetAllChildren vNod_ThisNode.Child, vNod_ThisNode.Checked
   Else
      ProcessThisNode vNod_ThisNode
   End If
   edCount.Text = Str(fInt_CopyCount)
   edAvail.Text = Str(fLng_AvailBlocks)
   
End Sub

Private Sub ResetAllChildren(ByVal vNod_ThisNode As MSComctlLib.Node, _
                             rBol_CheckStatus As Boolean)

   Dim lNod_SiblingNode          As MSComctlLib.Node
   
   Set lNod_SiblingNode = vNod_ThisNode
   Do While Not lNod_SiblingNode Is Nothing
      If (lNod_SiblingNode.Children > 0) Then
         lNod_SiblingNode.Checked = rBol_CheckStatus
         ResetAllChildren lNod_SiblingNode.Child, rBol_CheckStatus
      Else
         If (lNod_SiblingNode.Checked <> rBol_CheckStatus) Then
            lNod_SiblingNode.Checked = rBol_CheckStatus
            ProcessThisNode lNod_SiblingNode
         End If
      End If
      Set lNod_SiblingNode = lNod_SiblingNode.Next
   Loop
   
End Sub

Private Sub ProcessThisNode(ByVal vNod_ThisNode As MSComctlLib.Node)

   Dim lInt_FileHand    As Integer
   Dim lLng_FileSize    As Long
   Dim lLng_ThisBlocks  As Long
   
   lInt_FileHand = FreeFile
   Open "c:\" & vNod_ThisNode.Key For Input As #lInt_FileHand
   lLng_FileSize = LOF(lInt_FileHand)
   Close #lInt_FileHand
   
   lLng_ThisBlocks = Int((lLng_FileSize - 1) / 2048) + 1
   
   If (vNod_ThisNode.Checked = True) Then
      fInt_CopyCount = fInt_CopyCount + 1
      fLng_AvailBlocks = fLng_AvailBlocks - lLng_ThisBlocks
   Else
      fInt_CopyCount = fInt_CopyCount - 1
      fLng_AvailBlocks = fLng_AvailBlocks + lLng_ThisBlocks
   End If

End Sub

I'm sorry that the code is old and not very good, and I wouldn't be a bit surprised if it had a bug in it, but I hope it at least gives you a flavor of how to recursively traverse a tree.

Good Luck
--------------
As a circle of light increases so does the circumference of darkness around it. - Albert Einstein

 

[gohym]

Hi CajunCenturion,

Thank you so much for the algorithm! Well it is definitely a good start for me. I'll study the algorithm, but it won't be so soon as I have gone on to other tasks already. Guess I'll come back to this problem in 1 or 2 months time.

Thanks.