'Binary Search Tree sample http://www.debug.ir/Shervin
Public Class BSTree
Private Root As TreeNode
Public Sub New()
Root = Nothing
End Sub
Public Sub New(ByVal iData As Integer)
Root = New TreeNode(iData)
End Sub
Public Function IsEmpty() As Boolean
Return IsNothing(Root)
End Function
Public Function Search(ByVal x As Integer) As Boolean
Dim p As TreeNode = Root, q As TreeNode = Nothing
While Not p Is Nothing
q = p
If x < p.Data Then
p = p.LeftChild
ElseIf x > p.Data Then
p = p.RightChild
Else
Return True
End If
End While
Return False
End Function
Public Function Insert(ByVal x As Integer) As Boolean
Dim p As TreeNode = Root, q As TreeNode = Nothing
While Not p Is Nothing
q = p
If x < p.Data Then
p = p.LeftChild
ElseIf x > p.Data Then
p = p.RightChild
Else
Return False
End If
End While
p = New TreeNode(x)
If Me.IsEmpty Then
Root = p
ElseIf x < q.Data Then
q.LeftChild = p
Else
q.RightChild = p
End If
Return True
End Function
Public Function Remove(ByVal x As Integer) As Boolean
Dim p As TreeNode = Root, q As TreeNode = Nothing
While Not p Is Nothing AndAlso p.Data <> x
q = p
If x < p.Data Then
p = p.LeftChild
ElseIf x > p.Data Then
p = p.RightChild
End If
End While
If p Is Nothing Then Return False
If Not p.HaveChild Then
If q.LeftChild Is p Then
q.LeftChild = Nothing
Else
q.RightChild = Nothing
End If
ElseIf (Not p.HaveLChild) And (p.HaveRChild) Then
If q.LeftChild Is p Then
q.LeftChild = p.RightChild
Else
q.RightChild = p.RightChild
End If
ElseIf (p.HaveLChild) And (Not p.HaveRChild) Then
If q.LeftChild Is p Then
q.LeftChild = p.LeftChild
Else
q.RightChild = p.LeftChild
End If
Else
Dim d As TreeNode = p.RightChild
While d.HaveLChild
d = d.LeftChild
End While
Dim t As Integer = d.Data
Me.Remove(t)
p.Data = t
End If
Return True
End Function
Private Class TreeNode
Public Data As Integer
Public LeftChild As TreeNode
Public RightChild As TreeNode
Public Sub New(ByVal iData As Integer)
Data = iData
LeftChild = Nothing
RightChild = Nothing
End Sub
Public Function HaveChild() As Boolean
If IsNothing(LeftChild) AndAlso IsNothing(RightChild) Then
Return False
Else
Return True
End If
End Function
Public Function HaveLChild() As Boolean
Return Not IsNothing(LeftChild)
End Function
Public Function HaveRChild() As Boolean
Return Not IsNothing(RightChild)
End Function
End Class
End Class