Hello everyone,
I am trying to create a class to manage a binary tree. I fill in the tree letter by letter for each word.
If anyone could help me I would be very grateful.
One of the problems is knowing when to remove the letter that has been added to the tree: Word = Right( Word, Len(Word) - 1 )
BlockquoteClass
Tree(Head as Node, Current As Node)
Node(fLeft As Node, fRight As Node, Char As String, Full As Boolean)
Insertion( Word As String )
if Word = “$” Then // End of Word.
Full = True
Exit
end if
Charac = Mid( Word, 1, 1 )
if Charac < Char Then
if fLeft = Nil Then
fLeft = New Node( Charac )// We add the character to the left.
else
fLeft.INSERTION( Word )
end if
else
if fRight = Nil Then
fRight = New Node( Charac ) // We add the character to the right.
else
fRight.INSERTION( Word )
end if
end if
Word = Right( Word, Len(Word) - 1 )
Call for all of the words
Current = Head
Current.INSERTION( Word )
Your recursion should take a single character and insert it in the tree, nothing else. Take the word apart in your main code loop and call Insertion on each character. Your line of code using Right looks correct, it’s just in the wrong place.
You can also use
dim chars() as string
chars = split(word, "")
for i = 0 to ubound(chars)
head.Insertion(chars(i))
next
Hello Tim,
Once again thank you very much; you had already helped me a lot with my previous problem but as we cannot transmit a class by parametersit was too heavy in memory I think by going through intermediate variables.
OK Il will use your method, I was trying to make a full recursive function.
I had one last question regarding the search for a word in the tree, I don’t see where is the problem.
type or paste code hereSEARCH( Word As String, Posit As Integer) Boolean
if Len(Word) < Posit Then
if Char = EndofWord Then // EndofWord = “$”
Return True // The word exists
else
Return False // The word does not exist.
end if
else
if Char < Mid(Word, Posit, 1) Then
Return fLeft.SEARCH( Word, Posit )
else
if Char = UpperCase( Mid(Word, Posit, 1) ) Then
Return fRight.SEARCH( Word, Posit+1 )
else
Return False
end if
end if
end if
Call :
PushButton : if Dico.SEARCH( Word ) Then MsgBox(“Found !”) else MsgBox(“Not found !”)
Call Tree : Current = Head
Return Current.SEARCH( Word, 1 )
And you’re still trying to do too much in the recursive function. For each one, insertion and search, you need 2 functions. One that is called from outside the class and sets up what is needed for recursion (hiding the details from outside) and a recursive one that does the work. You’re trying to do the “set up” inside the recursive function, which is making everything more difficult.
Tim and Kem, thank you but I don’t see how we can edit the code after sending the message.
Tim,
To summarize my problems.
Coming from another language, I translated a word game program into RealBasic.
My first problem with recursion is the following, here is the original code of calling a function to fill a tree with words: FILL_TREE( Tree.Left, Word, Position + 1 )
I get an error saying you can’t pass an expression as a parmeter defined by reference (ByRef)
So I used an intermediate variable : Temp = Tree.Left FILL_TREE( Temp, Word, Position + 1 )
And there it works but as it takes 144 seconds to fill the tree with 402325 words I thought to proceed differently by creating a class.
In my last codes it is normal that I cannot find a word as my tree is incorrect.
In fact I have introduced all the letters of each word.
So I don’t see how to do it.
You shouldn’t need to pass the parameter ByRef. Leave that out. You are right to use a class, though. I would need to see your current code to help further.
Nicholas,
You’re teaching me something here, from everything I’ve read and studied they only talk about recursion but I’ll try.
Tim, I feel like I’m getting closer to the truth. At least the tree fills up but not correctly it seems to me.
Function Insert(Char As String) Boolean
if fData > Char Then
if Left <> Nil Then
Call Left.Insert( Char )
else
Left = New Tree( Char )
Call Left.Insert( Char )
end if
else // fData <= Char
if fData = Char Then
Return True
else // fData < Char
if Right <> Nil Then
Call Right.Insert( Char )
else
Right = New Tree( Char )
Call Right.Insert( Char )
end if
end if
end if
It doesn’t look like you fill in fData anywhere. Try this:
Sub Insert (Char As String)
If Char = "" Then
// Maybe raise an exception?
Return
End If
If fData = "" Or fData = Char Then
fData = Char
Return
End If
Select Case Char
Case Is > fData
If Right Is Nil Then
Right = New Tree( Char )
Else
Right.Insert( Char )
End If
Case Else // Is < fData
If Left Is Nil Then
Left = New Tree( Char )
Else
Left.Insert( Char )
End If
End Select
End Sub
(Not tested.)
Note that my version doesn’t return anything since this code will always end up doing something.
Recursion is an amusing novelty where the dataset is modest, but the outcome isn’t deterministic and eventually, if your data is large enough you’ll trigger a stack overflow exception - for example case in the help for stackoverflow:
It is always possible to refactor the code to remove recursion and in doing so you may often achieve a better result and code that runs reliably and easier to understand. NB Recursion and self-modifying code (I’ve been there done that, too) are not permitted in environments where software is used to perform a safety function (eg railways, aircraft, power stations, process oil & gas).
Nicholas, at first I thought like you but since everything I read talks about recursion I wanted to try to understand and make my program like that. I found it strange that for a word of 15 letters, for example, you need to browse through the branch 15 times to introduce the letters.
I will try it later.
Tim, I know there’s no need to call the function back but I was thinking maybe I was repositioning myself correctly in the tree, but the result is the same.
Kem, I used FILL_TREE in my previous program where I used the tree as a parameter but now I would like to avoid it.
Your code seems quite logical but I get the same tree. May I ask you to test your code with this code in a in button for example. Thank you.
Dim Word As String
Dim Words(-1) As String
Dim i,j As Integer
Words.Append "SHORT$"
Words.Append "ABOUT$"
Words.Append "DANCE$"
Words.Append "CRUAL$"
For j = 0 To Words.Ubound
Word = Words(j)
For i = 1 To Len(Word)
if bt = Nil Then
bt = New TBtreeNode( " " )
end if
Call bt.Insert( Mid( Word, i, 1 ) )
Next
Next
