Binary Tree example

Post your FreeBASIC source, examples, tips and tricks here. Please don’t post code without including an explanation.
fxm
Moderator
Posts: 12081
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Binary Tree example

Post by fxm »

1)
I improved and simplified the body of the 'getNearestNeighbour()' member function:

Code: Select all

Function Tree##nameTree.getNearestNeighbour(value As datatype) As datatype
    Static As Tree##nameTree Ptr p
    If @This = 0 Then
        Dim As Tree##nameTree Ptr p0
        p0 = p
        p = 0
        Return p0->value
    Else
        If p <> 0 Then
            If Abs(value - This.value) < Abs(value - p->value) Then
                p = @This
            End If
        Else
            p = @This
        End If
        If (value < This.value) Then
            Return This.nodeLeft->getNearestNeighbour(value)
        Else
            Return This.nodeRight->getNearestNeighbour(value)
        End If
    End If
End Function

2)
Removed 2 unnecessary lines in Destructor:

Code: Select all

Destructor Tree##nameTree()
    If This.nodeLeft <> 0 Then
        Delete This.nodeLeft
    End If
    If This.nodeRight <> 0 Then
        Delete This.nodeRight
    End If
End Destructor

Both member procedures to be updated in 'btree.bi'.
demosthenesk
Posts: 237
Joined: Jul 15, 2021 7:23
Location: Greece
Contact:

Re: Binary Tree example

Post by demosthenesk »

ok fixed !
fxm
Moderator
Posts: 12081
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Binary Tree example

Post by fxm »

Remark on 'btree.bi'

'btree.bi' can process not only any numeric datatype, but also a UDT if the user defines for this UDT:
- the 'Cast' operator (returning a string)
- the '=' comparison operator (returning a boolean)
- the '>' comparison operator (returning a boolean)
- the '<' comparison operator (returning a boolean)
- the '-' operator (returning a double)

Beginning of example for a list of 2D points with the distance to the origin point as criterion to build the tree and search for nearest neighbour:

Code: Select all

#Include "btree.bi"

Type P2D
    Dim As Double x
    Dim As Double y
    Declare Operator Cast() As String
End Type

Operator P2D.Cast() As String
    Return "(" & This.x & ", " & This.y & ")"
End Operator

Operator =(p1 As P2D, p2 As P2D) As Boolean
    If (p1.x = p2.x) And (p1.y = p2.y) Then
        Return True
    Else
        Return False
    End If
End Operator

Operator >(p1 As P2D, p2 As P2D) As Boolean
    If p1.x * p1.x + p1.y * p1.y > p2.x * p2.x + p2.y * p2.y Then
        Return True
    Else
        Return False
    End If
End Operator

Operator <(p1 As P2D, p2 As P2D) As Boolean
    If p1.x * p1.x + p1.y * p1.y < p2.x * p2.x + p2.y * p2.y Then
        Return True
    Else
        Return False
    End If
End Operator

Operator -(p1 As P2D, p2 As P2D) As Double
    Return Sqr(p2.x * p2.x + p2.y * p2.y) - Sqr(p1.x * p1.x + p1.y * p1.y)
End Operator



MakeTree(P2D, T1)                  'make a P2D tree structure, with name T1

Dim As TreeT1 Ptr pT = New TreeT1(Type<P2D>(1, 2))

pT->insertValue(Type<P2D>(3, 4))
pT->insertValue(Type<P2D>(0.5, 1))
pT->insertValue(Type<P2D>(2.5, 3.5))

pT->printValuesPaths("seed node")

'.....

Sleep
Post Reply