Binary Tree example

Post your FreeBASIC source, examples, tips and tricks here. Please don’t post code without including an explanation.
demosthenesk
Posts: 237
Joined: Jul 15, 2021 7:23
Location: Greece
Contact:

Re: Binary Tree example

Post by demosthenesk »

demosthenesk wrote: Sep 04, 2022 13:51 i want to implement a Function which return a node

Code: Select all

Type Tree##nameTree
    Public:
        value As datatype
        Declare Sub printPreorder()
        Declare Sub printPostorder()
        Declare Sub printInorder()
        Declare Function doesNodeExistInBST(searchValue As datatype) As Boolean
        Declare Function getBinaryTreeHeight() As Integer
	Declare Function getBinaryTreeSize() As Integer
        Declare Sub Insert(value As datatype)
	Declare Sub removeNode(value As datatype)
        Declare Destructor()
    Private:
    bstSize As Integer = 0
        nodeLeft As Tree##nameTree Ptr
        nodeRight As Tree##nameTree Ptr
	Declare Function getSize() As Integer
        Declare Function addNodeLeft(value As datatype) As Integer
        Declare Function addNodeRight(value As datatype) As Integer
        
-->	Declare Function kthSmallestNode(node As Tree##nameTree Ptr) As Tree##nameTree Ptr

End Type


Function Tree##nameTree.kthSmallestNode(node As Tree##nameTree Ptr) As Tree##nameTree Ptr
	Do While Not node.nodeLeft = 0
		node = node.nodeLeft
	Loop
	Return node
End Function
but i get compiling errors
error 265: Symbol not a CLASS, ENUM, TYPE or UNION type, before '.' in 'MakeTree(Double, T1)
Thanks fxm again, i will try your proposal on deletevalue(), but a question of curiosity...
why the above code fails?
i tried to port this https://levelup.gitconnected.com/deleti ... ed82e1791c
demosthenesk
Posts: 237
Joined: Jul 15, 2021 7:23
Location: Greece
Contact:

Re: Binary Tree example

Post by demosthenesk »

fxm wrote: Sep 04, 2022 14:02
demosthenesk wrote: Sep 04, 2022 13:51 i want to implement a Function which return a node

Code: Select all

Type Tree##nameTree
    Public:
        value As datatype
        Declare Sub printPreorder()
        Declare Sub printPostorder()
        Declare Sub printInorder()
        Declare Function doesNodeExistInBST(searchValue As datatype) As Boolean
        Declare Function getBinaryTreeHeight() As Integer
	Declare Function getBinaryTreeSize() As Integer
        Declare Sub Insert(value As datatype)
	Declare Sub removeNode(value As datatype)
        Declare Destructor()
    Private:
    bstSize As Integer = 0
        nodeLeft As Tree##nameTree Ptr
        nodeRight As Tree##nameTree Ptr
	Declare Function getSize() As Integer
        Declare Function addNodeLeft(value As datatype) As Integer
        Declare Function addNodeRight(value As datatype) As Integer
        
-->	Declare Function kthSmallestNode(node As Tree##nameTree Ptr) As Tree##nameTree Ptr

End Type


Function Tree##nameTree.kthSmallestNode(node As Tree##nameTree Ptr) As Tree##nameTree Ptr
	Do While Not node.nodeLeft = 0
		node = node.nodeLeft
	Loop
	Return node
End Function
but i get compiling errors
error 265: Symbol not a CLASS, ENUM, TYPE or UNION type, before '.' in 'MakeTree(Double, T1)

Code: Select all

Function Tree##nameTree.kthSmallestNode(node As Tree##nameTree Ptr) As Tree##nameTree Ptr
	Do While Not node->nodeLeft = 0
		node = node->nodeLeft
	Loop
	Return node
End Function
thanks...stupid bug...!!!
demosthenesk
Posts: 237
Joined: Jul 15, 2021 7:23
Location: Greece
Contact:

Re: Binary Tree example

Post by demosthenesk »

i upload the so far current work.
i added a Function getBinaryTreeSize() As Integer

btree.bi

Code: Select all

/'
Developers fxm, demosthenesk
'/
#Macro MakeTree(datatype, nameTree)
Type Tree##nameTree
    Public:
        value As datatype
        Declare Sub printPreorder()
        Declare Sub printPostorder()
        Declare Sub printInorder()
        Declare Function doesNodeExistInBST(searchValue As datatype) As Boolean
        Declare Function getBinaryTreeHeight() As Integer
		Declare Function getBinaryTreeSize() As Integer
        Declare Sub Insert(value As datatype)
		Declare Function deleteValue(value As datatype) As Boolean
        Declare Destructor()
    Private:
		bstSize As Integer = 0
        nodeLeft As Tree##nameTree Ptr
        nodeRight As Tree##nameTree Ptr
		Declare Function getSize() As Integer
        Declare Function addNodeLeft(value As datatype) As Integer
        Declare Function addNodeRight(value As datatype) As Integer
        Declare Function searchParentNode(value As datatype) Byref As Tree##nameTree
        Declare Sub insertNode(node AS Tree##nameTree)
        Declare Function insertNodeLeft(node AS Tree##nameTree) As Integer
        Declare Function insertNodeRight(node AS Tree##nameTree) As Integer
End Type

Destructor Tree##nameTree()
	If this.nodeLeft <> 0 Then
		this.value = 0
		Delete this.nodeLeft
	EndIf
	If this.nodeRight <> 0 Then
		this.value = 0
		Delete this.nodeRight
	EndIf
End Destructor


Function Tree##nameTree.insertNodeLeft(node AS Tree##nameTree) As Integer
	If this.nodeLeft = 0 Then
		this.nodeLeft = @node
		Return 0
	EndIf
	Return -1
End Function

Function Tree##nameTree.insertNodeRight(node AS Tree##nameTree) As Integer
	If this.nodeRight = 0 Then
		this.nodeRight = @node
		Return 0
	EndIf
	Return -1
End Function

Function Tree##nameTree.searchParentNode(value As datatype) Byref As Tree##nameTree
    Static as Tree##nameTree Ptr p
    if this.value = value then
        Return *p
    else
        p = @this
        if value > this.value then
            Return this.nodeRight->searchParentNode(value)
        else
            Return this.nodeLeft->searchParentNode(value)
        end if
    end if
End Function

Sub Tree##nameTree.insertNode(node AS Tree##nameTree)
    If (node.value < this.value) Then
        If this.insertNodeLeft(node) = 0 Then
            Return
        Else
            this.nodeLeft->insertNode(node)
        End If
    Else
        If this.insertNodeRight(node) = 0 Then
            Return
        Else
            this.nodeRight->insertNode(node)
        End If
    End If    
End Sub

Function Tree##nameTree.deleteValue(value As datatype) As Boolean
    If (this.value = value) Or (this.doesNodeExistInBST(value) = False) Then
        Return False
    End If
    
    Dim Byref As Tree##nameTree parentNode = this.searchParentNode(value)
    if parentNode.nodeLeft->value = value then
        dim as Tree##nameTree ptr p = parentNode.nodeLeft
        parentNode.nodeLeft = p->nodeLeft
        p->nodeLeft = 0
        if p->nodeRight <> 0 then
            this.insertNode(*p->nodeRight)
            p->nodeRight = 0
        end if
        Delete p
    else
        dim as Tree##nameTree ptr p = parentNode.nodeRight
        parentNode.nodeRight = p->nodeRight
        p->nodeRight = 0
        if p->nodeLeft <> 0 then
            this.insertNode(*p->nodeLeft)
            p->nodeLeft = 0
        end if
        Delete p
    end if
    return True
End Function


Function Tree##nameTree.addNodeLeft(value As datatype) As Integer
	If this.nodeLeft = 0 Then
		this.nodeLeft = New Tree##nameTree
		this.nodeLeft->value = value
		Return 0
	EndIf
	Return -1
End Function

Function Tree##nameTree.addNodeRight(value As datatype) As Integer
	If this.nodeRight = 0 Then
		this.nodeRight = New Tree##nameTree
		this.nodeRight->value = value
		Return 0
	EndIf
	Return -1
End Function


Sub Tree##nameTree.printPreorder()
	If @this = 0 Then
		Return
	Endif
	Print this.value & " " 'process node
	this.nodeLeft->printPreorder() 'recurse on left
	this.nodeRight->printPreorder() 'recurse on right
End Sub

Sub Tree##nameTree.printPostorder()
	If @this = 0 Then
		Return
	Endif
	this.nodeLeft->printPreorder() 'recurse on left
	this.nodeRight->printPreorder() 'recurse on right
	Print this.value & " " 'process node
End Sub

Sub Tree##nameTree.printInorder()
	If @this = 0 Then
		Return
	Endif
	this.nodeLeft->printPreorder() 'recurse on left
	Print this.value & " " 'process node
	this.nodeRight->printPreorder() 'recurse on right	
End Sub

Function Tree##nameTree.doesNodeExistInBST(searchValue As datatype) As Boolean
    if @this = 0 Then
        Return False
    elseif this.value = searchValue Then
        Return True
    else
        ' if the node we're at is smaller than the value we're looking for, traverse on the right side
        if searchValue > this.value Then
            Return this.nodeRight->doesNodeExistInBST(searchValue)
        else
            ' if the node we're at is bigger than the value we're looking for, traverse the left side
            Return this.nodeLeft->doesNodeExistInBST(searchValue)
        Endif
    Endif	
End Function

Function Tree##nameTree.getBinaryTreeHeight() As Integer
	If @this = 0 Then
		Return -1
	EndIf

    Dim leftHeight As Integer = this.nodeLeft->getBinaryTreeHeight()
    Dim rightHeight As Integer = this.nodeRight->getBinaryTreeHeight()

    if leftHeight > rightHeight Then
        Return leftHeight + 1
    else
        return rightHeight + 1
    Endif	
End Function

Function Tree##nameTree.getBinaryTreeSize() As Integer
	Dim size As Integer = 0 
	
	If @this = 0 Then
		Return -1
	EndIf
	
	this.bstSize=0
	size = this.getSize()
	Return size-1
End Function

Function Tree##nameTree.getSize() As Integer
	If @this = 0 Then
		Return 1
	Endif
	
	Dim a As Integer = this.nodeLeft->getSize() 'recurse on left
	Dim b As Integer = this.nodeRight->getSize() 'recurse on right	
	this.bstSize = a + b
	Return this.bstSize

End Function

Sub Tree##nameTree.Insert(value As datatype)
    If (value < this.value) Then
        If this.addNodeLeft(value) = 0 Then
            Return
        Else
            this.nodeLeft->Insert(value)
        End If
    Else
        If this.addNodeRight(value) = 0 Then
            Return
        Else
            this.nodeRight->Insert(value)
        End If
    End If    
End Sub
#Endmacro
main.bas

Code: Select all

#Include "btree.bi"

MakeTree(Double, T1)		'make a double tree, with name T1
Dim b As Boolean			'b as boolean
Dim height As Integer		'height as integer
Dim size As Integer			'size of tree as integer
Dim T As TreeT1				'Dim tree to variable T

T.value = 8				'root value


'insert values into tree
T.Insert(4)
T.Insert(12)
T.Insert(2)
T.Insert(6)
T.Insert(10)
T.Insert(14)
T.Insert(1)
T.Insert(3)
T.Insert(5)
T.Insert(7)
T.Insert(9)
T.Insert(11)
T.Insert(13)
T.Insert(15)
T.Insert(15.4)


/'
'insert values into tree
T.Insert(7)
T.Insert(6)
T.Insert(5)
T.Insert(4)
T.Insert(3)
T.Insert(2)
T.Insert(1)
T.Insert(0)
'/

'T.printPreorder()
T.printInorder()
'T.printPostorder()

'search for 6
b=T.doesNodeExistInBST(6)
Print "6 is found in tree ? " & b

'search for 5.4
b=T.doesNodeExistInBST(5.4)
Print "5.4 is found in tree ? " & b

'get tree height
height = T.getBinaryTreeHeight()
Print "Binary Tree height=" & height

'get tree size
size = T.getBinaryTreeSize()
Print "Binary Tree size = " & size

'delete node
Print
b=T.deleteValue(6)
Print "6 is deleted in tree ? " & b
Print
T.printInorder()

'get tree size
size = T.getBinaryTreeSize()
Print "Binary Tree size = " & size

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

Re: Binary Tree example

Post by fxm »

After an exhaustive test of deleting all entered values one to one, a bug is found for the '15.4' value (the parent node has its 'nodeLeft' = 0).

'Tree##nameTree.deleteValue(value As datatype) As Boolean' function corrected (only one line to correct):

Code: Select all

Function Tree##nameTree.deleteValue(value As datatype) As Boolean
    If (this.value = value) Or (this.doesNodeExistInBST(value) = False) Then
        Return False
    End If
    
    Dim Byref As Tree##nameTree parentNode = this.searchParentNode(value)
    if (parentNode.nodeLeft <> 0) Andalso (parentNode.nodeLeft->value = value) then  '' <------  correction
        dim as Tree##nameTree ptr p = parentNode.nodeLeft
        parentNode.nodeLeft = p->nodeLeft
        p->nodeLeft = 0
        if p->nodeRight <> 0 then
            this.insertNode(*p->nodeRight)
            p->nodeRight = 0
        end if
        Delete p
    else
        dim as Tree##nameTree ptr p = parentNode.nodeRight
        parentNode.nodeRight = p->nodeRight
        p->nodeRight = 0
        if p->nodeLeft <> 0 then
            this.insertNode(*p->nodeLeft)
            p->nodeLeft = 0
        end if
        Delete p
    end if
    return True
End Function
demosthenesk
Posts: 237
Joined: Jul 15, 2021 7:23
Location: Greece
Contact:

Re: Binary Tree example

Post by demosthenesk »

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

Re: Binary Tree example

Post by fxm »

The private 'bstSize' data member is useless:

Code: Select all

Function Tree##nameTree.getBinaryTreeSize() As Integer
	If @this = 0 Then
		Return -1
	EndIf
	
	Dim size As Integer = this.getSize()
	Return size-1
End Function

Function Tree##nameTree.getSize() As Integer
	If @this = 0 Then
		Return 1
	Endif
	
	Dim a As Integer = this.nodeLeft->getSize() 'recurse on left
	Dim b As Integer = this.nodeRight->getSize() 'recurse on right	
	Return a + b
End Function
demosthenesk
Posts: 237
Joined: Jul 15, 2021 7:23
Location: Greece
Contact:

Re: Binary Tree example

Post by demosthenesk »

fxm wrote: Sep 05, 2022 9:23 The private 'bstSize' data member is useless:

Code: Select all

Function Tree##nameTree.getBinaryTreeSize() As Integer
	If @this = 0 Then
		Return -1
	EndIf
	
	Dim size As Integer = this.getSize()
	Return size-1
End Function

Function Tree##nameTree.getSize() As Integer
	If @this = 0 Then
		Return 1
	Endif
	
	Dim a As Integer = this.nodeLeft->getSize() 'recurse on left
	Dim b As Integer = this.nodeRight->getSize() 'recurse on right	
	Return a + b
End Function
ok fixed!
fxm
Moderator
Posts: 12081
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Binary Tree example

Post by fxm »

I propose to add a public member procedure to print for each node value its path from the seed's node, path expressed by a sequence of 'L' (left branch) and 'R' (right branch) from the seed's node:
+ Declare Sub printPath(path As String = "seed node")

Code: Select all

/'
Developers fxm, demosthenesk
'/
#Macro MakeTree(datatype, nameTree)
Type Tree##nameTree
    Public:
        value As datatype
        Declare Sub printPreorder()
        Declare Sub printPostorder()
        Declare Sub printInorder()
        Declare Sub printPath(path As String = "seed node")
        Declare Function doesNodeExistInBST(searchValue As datatype) As Boolean
        Declare Function getBinaryTreeHeight() As Integer
		Declare Function getBinaryTreeSize() As Integer
        Declare Sub Insert(value As datatype)
		Declare Function deleteValue(value As datatype) As Boolean
        Declare Destructor()
    Private:
        nodeLeft As Tree##nameTree Ptr
        nodeRight As Tree##nameTree Ptr
		Declare Function getSize() As Integer
        Declare Function addNodeLeft(value As datatype) As Integer
        Declare Function addNodeRight(value As datatype) As Integer
        Declare Function searchParentNode(value As datatype) Byref As Tree##nameTree
        Declare Sub insertNode(node AS Tree##nameTree)
        Declare Function insertNodeLeft(node AS Tree##nameTree) As Integer
        Declare Function insertNodeRight(node AS Tree##nameTree) As Integer
End Type

Destructor Tree##nameTree()
	If this.nodeLeft <> 0 Then
		this.value = 0
		Delete this.nodeLeft
	EndIf
	If this.nodeRight <> 0 Then
		this.value = 0
		Delete this.nodeRight
	EndIf
End Destructor


Function Tree##nameTree.insertNodeLeft(node AS Tree##nameTree) As Integer
	If this.nodeLeft = 0 Then
		this.nodeLeft = @node
		Return 0
	EndIf
	Return -1
End Function

Function Tree##nameTree.insertNodeRight(node AS Tree##nameTree) As Integer
	If this.nodeRight = 0 Then
		this.nodeRight = @node
		Return 0
	EndIf
	Return -1
End Function

Function Tree##nameTree.searchParentNode(value As datatype) Byref As Tree##nameTree
    Static as Tree##nameTree Ptr p
    if this.value = value then
        Return *p
    else
        p = @this
        if value > this.value then
            Return this.nodeRight->searchParentNode(value)
        else
            Return this.nodeLeft->searchParentNode(value)
        end if
    end if
End Function

Sub Tree##nameTree.insertNode(node AS Tree##nameTree)
    If (node.value < this.value) Then
        If this.insertNodeLeft(node) = 0 Then
            Return
        Else
            this.nodeLeft->insertNode(node)
        End If
    Else
        If this.insertNodeRight(node) = 0 Then
            Return
        Else
            this.nodeRight->insertNode(node)
        End If
    End If    
End Sub

Function Tree##nameTree.deleteValue(value As datatype) As Boolean
    If (this.value = value) Or (this.doesNodeExistInBST(value) = False) Then
        Return False
    End If
    
    Dim Byref As Tree##nameTree parentNode = this.searchParentNode(value)
    if (parentNode.nodeLeft <> 0) Andalso (parentNode.nodeLeft->value = value) then  '' <------  correction
        dim as Tree##nameTree ptr p = parentNode.nodeLeft
        parentNode.nodeLeft = p->nodeLeft
        p->nodeLeft = 0
        if p->nodeRight <> 0 then
            this.insertNode(*p->nodeRight)
            p->nodeRight = 0
        end if
        Delete p
    else
        dim as Tree##nameTree ptr p = parentNode.nodeRight
        parentNode.nodeRight = p->nodeRight
        p->nodeRight = 0
        if p->nodeLeft <> 0 then
            this.insertNode(*p->nodeLeft)
            p->nodeLeft = 0
        end if
        Delete p
    end if
    return True
End Function

Function Tree##nameTree.addNodeLeft(value As datatype) As Integer
	If this.nodeLeft = 0 Then
		this.nodeLeft = New Tree##nameTree
		this.nodeLeft->value = value
		Return 0
	EndIf
	Return -1
End Function

Function Tree##nameTree.addNodeRight(value As datatype) As Integer
	If this.nodeRight = 0 Then
		this.nodeRight = New Tree##nameTree
		this.nodeRight->value = value
		Return 0
	EndIf
	Return -1
End Function


Sub Tree##nameTree.printPreorder()
	If @this = 0 Then
		Return
	Endif
	Print this.value & " " 'process node
	this.nodeLeft->printPreorder() 'recurse on left
	this.nodeRight->printPreorder() 'recurse on right
End Sub

Sub Tree##nameTree.printPostorder()
	If @this = 0 Then
		Return
	Endif
	this.nodeLeft->printPreorder() 'recurse on left
	this.nodeRight->printPreorder() 'recurse on right
	Print this.value & " " 'process node
End Sub

Sub Tree##nameTree.printInorder()
	If @this = 0 Then
		Return
	Endif
	this.nodeLeft->printPreorder() 'recurse on left
	Print this.value & " " 'process node
	this.nodeRight->printPreorder() 'recurse on right	
End Sub

Sub Tree##nameTree.printPath(path As String = "seed node")
    If @This = 0 Then
        Return
    Else
        Print This.value & " ", path
        This.nodeLeft->printPath(path & " + L")
        This.nodeRight->printPath(path & " + R")
    End if	
End Sub

Function Tree##nameTree.doesNodeExistInBST(searchValue As datatype) As Boolean
    if @this = 0 Then
        Return False
    elseif this.value = searchValue Then
        Return True
    else
        ' if the node we're at is smaller than the value we're looking for, traverse on the right side
        if searchValue > this.value Then
            Return this.nodeRight->doesNodeExistInBST(searchValue)
        else
            ' if the node we're at is bigger than the value we're looking for, traverse the left side
            Return this.nodeLeft->doesNodeExistInBST(searchValue)
        Endif
    Endif	
End Function

Function Tree##nameTree.getBinaryTreeHeight() As Integer
	If @this = 0 Then
		Return -1
	EndIf

    Dim leftHeight As Integer = this.nodeLeft->getBinaryTreeHeight()
    Dim rightHeight As Integer = this.nodeRight->getBinaryTreeHeight()

    if leftHeight > rightHeight Then
        Return leftHeight + 1
    else
        return rightHeight + 1
    Endif	
End Function

Function Tree##nameTree.getBinaryTreeSize() As Integer
	If @this = 0 Then
		Return -1
	EndIf
	
	Dim size As Integer = this.getSize()
	Return size-1
End Function

Function Tree##nameTree.getSize() As Integer
	If @this = 0 Then
		Return 1
	Endif
	
	Dim a As Integer = this.nodeLeft->getSize() 'recurse on left
	Dim b As Integer = this.nodeRight->getSize() 'recurse on right	
	Return a + b
End Function

Sub Tree##nameTree.Insert(value As datatype)
    If (value < this.value) Then
        If this.addNodeLeft(value) = 0 Then
            Return
        Else
            this.nodeLeft->Insert(value)
        End If
    Else
        If this.addNodeRight(value) = 0 Then
            Return
        Else
            this.nodeRight->Insert(value)
        End If
    End If    
End Sub
#Endmacro



'#Include "btree.bi"

MakeTree(Double, T1)		'make a double tree, with name T1
Dim b As Boolean			'b as boolean
Dim height As Integer		'height as integer
Dim size As Integer			'size of tree as integer
Dim T As TreeT1				'Dim tree to variable T

T.value = 8				'root value


'insert values into tree
T.Insert(4)
T.Insert(12)
T.Insert(2)
T.Insert(6)
T.Insert(10)
T.Insert(14)
T.Insert(1)
T.Insert(3)
T.Insert(5)
T.Insert(7)
T.Insert(9)
T.Insert(11)
T.Insert(13)
T.Insert(15)
T.Insert(15.4)


/'
'insert values into tree
T.Insert(7)
T.Insert(6)
T.Insert(5)
T.Insert(4)
T.Insert(3)
T.Insert(2)
T.Insert(1)
T.Insert(0)
'/

'T.printPreorder()
T.printInorder()
'T.printPostorder()

'search for 6
b=T.doesNodeExistInBST(6)
Print "6 is found in tree ? " & b

'search for 5.4
b=T.doesNodeExistInBST(5.4)
Print "5.4 is found in tree ? " & b

'get tree height
height = T.getBinaryTreeHeight()
Print "Binary Tree height=" & height

'get tree size
size = T.getBinaryTreeSize()
Print "Binary Tree size = " & size

'delete node
Print
b=T.deleteValue(6)
Print "6 is deleted in tree ? " & b
Print
T.printInorder()

'get tree size
size = T.getBinaryTreeSize()
Print "Binary Tree size = " & size

Print
T.printPath()

Sleep
  • Code: Select all

    4
    2
    1
    3
    6
    5
    7
    8
    12
    10
    9
    11
    14
    13
    15
    15.4
    6 is found in tree ? true
    5.4 is found in tree ? false
    Binary Tree height=4
    Binary Tree size = 16
    
    6 is deleted in tree ? true
    
    4
    2
    1
    3
    7
    5
    8
    12
    10
    9
    11
    14
    13
    15
    15.4
    Binary Tree size = 15
    
    8            seed node
    4            seed node + L
    2            seed node + L + L
    1            seed node + L + L + L
    3            seed node + L + L + R
    7            seed node + L + R
    5            seed node + L + R + L
    12           seed node + R
    10           seed node + R + L
    9            seed node + R + L + L
    11           seed node + R + L + R
    14           seed node + R + R
    13           seed node + R + R + L
    15           seed node + R + R + R
    15.4         seed node + R + R + R + R
    
demosthenesk
Posts: 237
Joined: Jul 15, 2021 7:23
Location: Greece
Contact:

Re: Binary Tree example

Post by demosthenesk »

ok!
printPath() added !
nice feature !!! i have n't seen it in any other example on the web...!
fxm
Moderator
Posts: 12081
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Binary Tree example

Post by fxm »

demosthenesk wrote: Sep 05, 2022 19:43 i have n't seen it in any other example on the web...!
Me neither (but I didn't look!).
I think this is also useful to the developer for checking the different functionalities (insert, delete, and the future ones).
demosthenesk
Posts: 237
Joined: Jul 15, 2021 7:23
Location: Greece
Contact:

Re: Binary Tree example

Post by demosthenesk »

fxm wrote: Sep 05, 2022 20:29
demosthenesk wrote: Sep 05, 2022 19:43 i have n't seen it in any other example on the web...!
Me neither (but I didn't look!).
I think this is also useful to the developer for checking the different functionalities (insert, delete, and the future ones).
yes it is cool and nice !!!
thanks for the brain storming... :)
demosthenesk
Posts: 237
Joined: Jul 15, 2021 7:23
Location: Greece
Contact:

Re: Binary Tree example

Post by demosthenesk »

i tried to make a pointer on TreeT1 ... compiles ok but it fails run why ?
i wanted to be able to free pT deleting root value...

Code: Select all

Dim pT As TreeT1 Ptr
pT->value = 8
pT->Insert(4)
pT->Insert(12)
pT->Insert(2)
pT->Insert(6)
pT->Insert(10)
pT->Insert(14)
pT->Insert(1)
pT->Insert(3)
pT->Insert(5)
pT->Insert(7)
pT->Insert(9)
pT->Insert(11)
pT->Insert(13)
pT->Insert(15)
pT->Insert(15.4)

pT->printInorder()
:?:
fxm
Moderator
Posts: 12081
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Binary Tree example

Post by fxm »

You have only declared a TreeT1 pointer, but not constructed a TreeT1 object.

Using a TreeT1 pointer, you have two options to construct an object:
- Static object with 'Dim' (with self-destruction of object when it goes out of scope):

Code: Select all

MakeTree(Double, T1)		'make a double tree, with name T1
Dim T As TreeT1
Dim pT As TreeT1 Ptr = @T

pT->value = 8
pT->Insert(4)
pT->Insert(12)
pT->Insert(2)
pT->Insert(6)
pT->Insert(10)
pT->Insert(14)
pT->Insert(1)
pT->Insert(3)
pT->Insert(5)
pT->Insert(7)
pT->Insert(9)
pT->Insert(11)
pT->Insert(13)
pT->Insert(15)
pT->Insert(15.4)

pT->printInorder()
- Dynamic object with 'New...Delete' (with user destruction of object when he wishes):

Code: Select all

MakeTree(Double, T1)		'make a double tree, with name T1
Dim pT As TreeT1 Ptr = New TreeT1

pT->value = 8
pT->Insert(4)
pT->Insert(12)
pT->Insert(2)
pT->Insert(6)
pT->Insert(10)
pT->Insert(14)
pT->Insert(1)
pT->Insert(3)
pT->Insert(5)
pT->Insert(7)
pT->Insert(9)
pT->Insert(11)
pT->Insert(13)
pT->Insert(15)
pT->Insert(15.4)

pT->printInorder()

Delete pT
demosthenesk
Posts: 237
Joined: Jul 15, 2021 7:23
Location: Greece
Contact:

Re: Binary Tree example

Post by demosthenesk »

if i Delete pT are all node pointers deleted ?

according Destructor ...

Code: Select all

Destructor Tree##nameTree()
	If this.nodeLeft <> 0 Then
		this.value = 0
		Delete this.nodeLeft
	EndIf
	If this.nodeRight <> 0 Then
		this.value = 0
		Delete this.nodeRight
	EndIf
End Destructor
fxm
Moderator
Posts: 12081
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Binary Tree example

Post by fxm »

Yes thanks to the destructor()'s body which chains the destruction of all nodes.
To check it:

Code: Select all

Constructor Tree##nameTree()
	Print "construct", @this
End Constructor

Destructor Tree##nameTree()
	Print "delete", @this, this.value
	If this.nodeLeft <> 0 Then
		this.value = 0
		Delete this.nodeLeft
	EndIf
	If this.nodeRight <> 0 Then
		this.value = 0
		Delete this.nodeRight
	EndIf
End Destructor
Post Reply