#Macro MakeTree(datatype, nameTree)
Type Tree##nameTree
value As datatype
nodeLeft As Tree##nameTree Ptr
nodeRight As Tree##nameTree Ptr
Declare Function addNodeLeft(value As datatype) As Integer
Declare Function addNodeRight(value As datatype) As Integer
Declare Destructor()
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.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 printPreorder(node As Tree##nameTree Ptr)
If node = 0 Then
Return
Endif
Print node->value & " " 'process node
printPreorder(node->nodeLeft) 'recurse on left
printPreorder(node->nodeRight) 'recurse on right
End Sub
Sub printPostorder(node As Tree##nameTree Ptr)
If node = 0 Then
Return
Endif
printPreorder(node->nodeLeft) 'recurse on left
printPreorder(node->nodeRight) 'recurse on right
Print node->value & " " 'process node
End Sub
Sub printInorder(node As Tree##nameTree Ptr)
If node = 0 Then
Return
Endif
printPreorder(node->nodeLeft) 'recurse on left
Print node->value & " " 'process node
printPreorder(node->nodeRight) 'recurse on right
End Sub
Function doesNodeExistInBST(bstRoot As Tree##nameTree Ptr, searchValue As datatype) As Boolean
if bstRoot = 0 Then
Return False
elseif bstRoot->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 > bstRoot->value Then
Return doesNodeExistInBST(bstRoot->nodeRight, searchValue)
else
' if the node we're at is bigger than the value we're looking for, traverse the left side
Return doesNodeExistInBST(bstRoot->nodeLeft, searchValue)
Endif
Endif
End Function
Function getBinaryTreeHeight(node As Tree##nameTree Ptr) As Integer
If node = 0 Then
Return -1
EndIf
Dim leftHeight As Integer = getBinaryTreeHeight(node->nodeLeft)
Dim rightHeight As Integer = getBinaryTreeHeight(node->nodeRight)
if leftHeight > rightHeight Then
Return leftHeight + 1
else
return rightHeight + 1
Endif
End Function
Sub Insert(node As Tree##nameTree Ptr, value As datatype)
If node->nodeLeft = 0 Or node->nodeRight = 0 Then
If (value < node->value) Then
node->addNodeLeft(value)
Return
Else
node->addNodeRight(value)
Return
Endif
EndIf
If node->nodeLeft <> 0 Or node->nodeRight <> 0 Then
If (value < node->value) Then
Insert(node->nodeLeft, value)
Else
Insert(node->nodeRight, value)
Endif
EndIf
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 T As TreeT1 'Dim tree to variable T
Dim pT As TreeT1 Ptr 'pT a pointer to TreeT1 T
pT = @T 'pT points to T
pT->value = 8 'root value
'insert values into tree
Insert(pT, 4)
Insert(pT, 12)
Insert(pT, 2)
Insert(pT, 6)
Insert(pT, 10)
Insert(pT, 14)
Insert(pT, 1)
Insert(pT, 3)
Insert(pT, 5)
Insert(pT, 7)
Insert(pT, 9)
Insert(pT, 11)
Insert(pT, 13)
Insert(pT, 15)
Insert(pT, 15.4)
'print tree
'printPreorder(pT)
printInorder(pT)
'printPostorder(pT)
'search for 6
b=doesNodeExistInBST(pT, 6)
Print "6 is found in tree ? " & b
'search for 5.4
b=doesNodeExistInBST(pT, 5.4)
Print "5.4 is found in tree ? " & b
'get tree height
height = getBinaryTreeHeight(pT)
Print "Binary Tree height=" & height
Sleep
End
END (statement) is used to exit the program, and return to the operating system. An optional integer return value can be specified to indicate an error code to the system. If no return value is given, a value of 0 is automatically returned at the end of the program.
Usage of this statement does not cleanly close scope. Local variables will not have their destructors called automatically, because FreeBASIC does not do stack unwinding. Only the destructors of global variables will be called in this case.
For this reason, it is discouraged to use End simply to mark the end of a program; the program will come to an end automatically, and in a cleaner fashion, when the last line of module-level code has executed.
2)
I see in your code that many procedures are not members of the Type although a Type's pointer is passed to each.
If these procedures are defined as members of the Type, the previous test of a null Type's pointer passed can be transposed to a test of a null @This.
(one can always call a member procedure on a null Type's pointer, and there is no crash in the member procedure body as long as one does not use This, explicitly or implicitly, to access a member variable)
#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 Sub Insert(value As datatype)
Declare Destructor()
Private:
nodeLeft As Tree##nameTree Ptr
nodeRight As Tree##nameTree Ptr
Declare Function addNodeLeft(value As datatype) As Integer
Declare Function addNodeRight(value As datatype) 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.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
Sub Tree##nameTree.Insert(value As datatype)
If this.nodeLeft = 0 Or this.nodeRight = 0 Then
If (value < this.value) Then
this.addNodeLeft(value)
Return
Else
this.addNodeRight(value)
Return
Endif
EndIf
If this.nodeLeft <> 0 Or this.nodeRight <> 0 Then
If (value < this.value) Then
this.nodeLeft->Insert(value)
Else
this.nodeRight->Insert(value)
Endif
EndIf
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 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)
'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
Sleep
First, I do not agree with your Tree##nameTree.Insert(value As datatype):
- That works with your example because the inserted values are alternatively lower then higher and so on...
- Your code does not work for example with this sequence:
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
To add a Tree##nameTree.deleteValue(value As datatype) procedure, the problem is more complex because one of the two child branches can easily be reconnected to the parent node if exists (the branch on the same side), but for the other child branch, you have to do a search for a place in the whole tree similar to inserting a new value (the value of the first node of this second child branch).
If the value to delete corresponds to the seed node ???
fxm wrote: ↑Sep 04, 2022 8:12
First, I do not agree with your Tree##nameTree.Insert(value As datatype):
- That works with your example because the inserted values are alternatively lower then higher and so on...
- Your code does not work for example with this sequence:
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
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)
Last edited by demosthenesk on Sep 04, 2022 13:55, edited 1 time in total.
fxm wrote: ↑Sep 04, 2022 8:35
To add a Tree##nameTree.deleteValue(value As datatype) procedure, the problem is more complex because one of the two child branches can easily be reconnected to the parent node if exists (the branch on the same side), but for the other child branch, you have to do a search for a place in the whole tree similar to inserting a new value (the value of the first node of this second child branch).
If the value to delete corresponds to the seed node ???
Added one public member procedure:
- Function deleteValue(value As datatype) As Boolean
Added four private member procedures (to break down the problem):
- Function searchParentNode(value As datatype) Byref As Tree##nameTree
- Sub insertNode(node AS Tree##nameTree)
- Function insertNodeLeft(node AS Tree##nameTree) As Integer
- Function insertNodeRight(node AS Tree##nameTree) As Integer
Only the value corresponding to the seed node (8 in the example here) can not be deleted.
Code proposal to be tested more exhaustively, to be corrected and improved if necessary:
#Macro MakeTree(datatype, nameTree)
Type Tree##nameTree
Public:
value As datatype
Declare Sub printPreorder()
Declare Sub printPostorder()
Declare Sub printInorder()
Declare Function doesNodeExistInBST(value As datatype) As Boolean
Declare Function getBinaryTreeHeight() 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 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.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
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
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(value As datatype) As Boolean
if @this = 0 Then
Return False
elseif this.value = value 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 value > this.value Then
Return this.nodeRight->doesNodeExistInBST(value)
else
' if the node we're at is bigger than the value we're looking for, traverse the left side
Return this.nodeLeft->doesNodeExistInBST(value)
Endif
Endif
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
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
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
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
#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 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)
'T.printPreorder()
T.printInorder()
Print
'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
Print
b=T.deleteValue(6)
Print "6 is deleted in tree ? " & b
Print
T.printInorder()
Sleep
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