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)
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)
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
/'
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
#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
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.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
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
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")
/'
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
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 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 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...
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):
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):