Page 1 of 1

## Binary Trees, the Question Game, and car rides! Rate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=279716&amp;s=f7bcd096375f6ff224ca867a833f954c&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 modi123_1

• Suitor #2

Reputation: 11611
• Posts: 45,774
• Joined: 12-June 08

Posted 17 May 2012 - 11:55 AM

POPULAR

Intro
Here's a fun little tutorial that shows the usage of a binary tree with a simple question and answer game. Think of something like '20 Questions' and you get the idea. The major areas of this are:
- binary tree structures,
- recursively writing a binary tree to a file
- recursively reading a binary tree from a file
- fun with classes

Sometimes you can do this with a neural network, but there's also a time and place for a more simple structure. Further extrapolation this can be used for a directed FAQ for troubleshooting, or actual species identification.

If you are not familiar with some of the concepts of a binary tree - check out my other tutorial here on it.

Back story
If you are not familiar with the game Twenty Questions then you are missing out. It was a game from my childhood summer vacations.. you, your siblings, annoyed parents, and nothing but all the time in the world. One player would think of an animal.. then the other person would ask yes or no questions to narrow down what the other person was thinking of. You could guess early or use up all possible 20 questions. It was always tough maximizing your question to try and cut large swaths of possible candidates out, but a fun source of remembering which questions you hit on early when you are at question 18.

Ideally the game should have broken down into a binary tree... specific yes or no questions shaping the possible space. Given enough input and responses you can build up a shockingly large array of seemingly incongruous questions that lead to right answers. Heck the guy at 20q.net did this and then ported part of the database to a toy and sold it!

Specific rules
In my tree if you pick yes that means go to the left branch.. no then means go to the right branch. It's important to keep which side your affirmatives and negatives are on!

This also means you can extrapolate that branches are for questions and leaves are for answers. The tree updates itself so if the application is on a leaf and guesses, but FAILS, the question the user provides replace of the current leaf, the old value becomes the left child and the user's answer becomes the right!

I also rely on some end game user feed back. Since I am too lazy to sit around entering questions and possible answers - I only feel up for one question. If it turns out that answer is not right then prompt the user for input to further define things! That's right - with each start of the game - if my program fails to guess right it gets the answer from the user and asks them to provide a question that differentiates between the failed guess and the user's answer. Sure the first hundred or so games might not be exciting but once the structure fleshes out looks spooky smart!

Also, for you math buffs out there have you thought about the number of nodes I could have? I start out with one root note (1). Then that node can have two children (2). Each of those can have two children (4).. and those can have a pair of children (8).. that looks like a series! To get how many nodes are on a row it looks like: 2^n will do! n is what level you are want to check (and assuming the root is level 0). That means we can extrapolate that each layer is a question and if we wanted to see how many answers we could house that would be 2^20! (See we start counting at 0 and that last row of answer leaves are sort of questions.. so you have twenty proper questions before you ask "is it X".

A quick calculation says 2^20 is 1,048,576 possible answers!

Now if you are curious the total number of nodes in this whole structure could be (playing 20 questions) - that is a (2^(n+1))-1. (Trust me on this). That is two to the the power of n minus 1... all of that minus one. n is the level.. and again the root is level 0.

This means at level 20 we have a total of: (2^(20+1))-1 or 2,097,151 nodes! Just a bit!

Code
The first bit is the basic node.. It's a modification of my previous tutorial's node with the addition of a property to tell if it is a string or not, and the stored value is a string. The node is just a fancy name for a container of a string and two other node objects...

Class Node
```''' <summary>
''' Basic node.. it can have up to two children, and stores one string value.
''' </summary>
''' <remarks></remarks>
Public Class Node
Private _leftNode As Node = Nothing
Private _rightNode As Node = Nothing

Private _oValue As String = Nothing

Public Property LeftNode As Node
Get
Return _leftNode
End Get
Set(value As Node)
_leftNode = value
End Set
End Property

Public Property RightNode As Node
Get
Return _rightNode
End Get
Set(value As Node)
_rightNode = value
End Set
End Property

Public Property Value As String
Get
Return _oValue
End Get
Set(value As String)
_oValue = value
End Set
End Property

''' <summary>
''' If the node has no children it must be a leaf and not a branch.
''' </summary>
''' <value></value>
''' <returns></returns>
''' <remarks></remarks>
Public ReadOnly Property IsLeaf As Boolean
Get
Return (LeftNode Is Nothing AndAlso RightNode Is Nothing)
End Get
End Property

''' <summary>
''' Define a node with no children but a value.
''' </summary>
''' <param name="value"></param>
''' <remarks></remarks>
Public Sub New(ByVal value As String)
'-- new nodes don't have children yet, just a value
_leftNode = Nothing
_rightNode = Nothing
_oValue = value
End Sub
End Class

```

On top of that class I have a 'BinaryTree' class. This makes use of one starter node. The important part is this class takes care of interacting with the entire node structure.. the printing, the writing to a file, and the reading from a file. Basically - all the annoying recursive objects. If my previous tutorial I was doing a numeric insert here - I removed that to the next class.

Class BinTree
```''' <summary>
''' A structure in tree related functions to operate on the nodes.
''' </summary>
''' <remarks></remarks>
Public Class BinTree
Public Property Root As Node

''' <summary>
''' Define that root node at the start.
''' </summary>
''' <param name="value"></param>
''' <remarks></remarks>
Public Sub New(ByVal value As String)
_root = New Node(value)  '-- create our node
'     Console.WriteLine(String.Format("Root Inserting: {0}", value)) '-- output what we have done.
End Sub

Public Sub Print()
Console.WriteLine("================")

PrintPreOrder(_Root, 0, "")

End Sub

'-- PreOrder I decided to take some liberties and make it pretty.  I added a hyphen to signifiy the leve, and
'-- also visual indicators on which node (left or right) the value is from.
'-- The idea here is we print which node we are on, check left, check right.
'--
'-- The level As Int32 is only needed for printing the hypen.. you can remove it and it still works (sans printing hyphens).
Private Sub PrintPreOrder(ByVal myNode As Node, ByVal level As Int32, ByVal side As String)
Dim sVal As String = String.Empty

For i As Int32 = 0 To level - 1
sVal += "-"
Next

If myNode Is Root Then sVal = "*"
'-- Actual meat of the method.
Console.WriteLine(String.Format("{0}{1} {2}", sVal, side, myNode.Value))
If myNode.LeftNode IsNot Nothing Then PrintPreOrder(myNode.LeftNode, level + 1, "L")
If myNode.RightNode IsNot Nothing Then PrintPreOrder(myNode.RightNode, level + 1, "R")
End Sub

''' <summary>
''' Very similar to the PrintPreOrder... If we have struck 'nothing' then put a token flag to alert us when we read in that there are no more down this path.
''' If we are not nothing then write our value and traverse to the left and traverse to the right.  T
''' This makes use of heavy recursion... the function will go left until it hits a leaf.. back up and go right until it leaf..
''' and then the recursive calls return to the parent call which means it goes left right until it can't...
''' </summary>
''' <param name="myNode"></param>
''' <param name="sw"></param>
''' <remarks></remarks>
Public Sub WriteToFilePreOrder(ByVal myNode As Node, ByRef sw As IO.StreamWriter)
If myNode Is Nothing Then
sw.WriteLine("#")
sw.Flush()
Else
sw.WriteLine(myNode.Value)
sw.Flush()
WriteToFilePreOrder(myNode.LeftNode, sw)
WriteToFilePreOrder(myNode.RightNode, sw)
End If
End Sub

''' <summary>
''' Read each line in the file until we hit the token flag.. then we know we can stop and return to the parent call.
''' </summary>
''' <param name="myNode"></param>
''' <param name="sr"></param>
''' <remarks></remarks>
Dim temp As String = String.Empty

If temp = "#" Then
Exit Sub
Else
myNode = New Node(temp)
End If
End Sub
End Class

```

An example of what the first question and two answers look like written to a file:
Spoiler

The 'TwentyQuestions' should be the main class the user would operate with. This simply contains the binary tree object, basic calls for setting up the reading and writing of the tree, and the all the logic of tracking the current node, asking questions, and taking in responses.

Yes, the more important function is the "StartQuestioning()". This sets up the loop that takes you from question 1 to the way to a leaf/potential answer. If it fails it asks the user for what they were thinking about and a question that would differentiate between the two. Of course I am assuming benign user input here - so they would go along with the spirit of the game and not troll it.

Class TwentyQuestions
```''' <summary>
''' Takes care of the super class for tracking the tree object,
''' dealing with asking user input, dealing with recording user input, and the read/write to file options.
''' </summary>
''' <remarks></remarks>
Public Class TwentyQuestions
Private _binaryTree As BinTree

Private _curNode As Node

Public Sub New()
'-- basic seeding of the tree... a first question
_binaryTree = New BinTree("Does it fly?")

_curNode = _binaryTree.Root

_curNode.LeftNode = New Node("Bird")
_curNode.RightNode = New Node("Snake")
'524,288
'1'048'575
End Sub

''' <summary>
''' This starts the round of questioning.
''' </summary>
''' <remarks></remarks>
Public Sub StartQuestioning()
Dim sIn As String = String.Empty

Dim _sWhatWasIt As String = String.Empty
Dim _sNewQuestion As String = String.Empty

_curNode = _binaryTree.Root
Console.WriteLine(Environment.NewLine + "-----------")
While Not _curNode.IsLeaf
sIn = String.Empty

Console.WriteLine(_curNode.Value)

If sIn.ToUpper = "Y" OrElse sIn.ToUpper = "YES" Then
_curNode = _curNode.LeftNode
Else
_curNode = _curNode.RightNode
End If

End While

Console.WriteLine(String.Format("Is it a {0}? ", _curNode.Value))

If sIn.ToUpper = "Y" OrElse sIn.ToUpper = "YES" Then
Console.WriteLine("Win!")
Else
Console.WriteLine("What was it?")
Console.WriteLine(String.Format("What question would different {0} from {1}? ", _curNode.Value, _sWhatWasIt))

_curNode.LeftNode = New Node(_curNode.Value)
_curNode.RightNode = New Node(_sWhatWasIt)
_curNode.Value = _sNewQuestion
End If

_binaryTree.Print()
End Sub

''' <summary>
''' Basic function to create the streamwriter object and start off the recursion.
''' </summary>
''' <param name="filelocation"></param>
''' <remarks></remarks>
Public Sub Write(ByVal filelocation As String)
Dim sw As IO.StreamWriter = Nothing

Try
sw = New IO.StreamWriter(filelocation)

_binaryTree.WriteToFilePreOrder(_binaryTree.Root, sw)
sw.Flush()
Catch ex As Exception
MsgBox(ex.Message)
Finally
sw.Dispose()
End Try

End Sub

''' <summary>
''' Basic function to create the reader, empty the roto, and start the recursion.
''' </summary>
''' <param name="filelocation"></param>
''' <remarks></remarks>
Public Sub Read(ByVal filelocation As String)
Dim sr As IO.StreamReader = Nothing

Try

_binaryTree.Root = Nothing

_binaryTree.Print()
Catch ex As Exception
MsgBox(ex.Message)
Finally
sr.Dispose()
End Try

End Sub
End Class

```

All together the Node provides the backbone for the information, the BinTree provides a structure to interpret the connections between the nodes, and TwentyQuestions provides all the game data and how to do inserts based on user input!

Class main
```        Dim foo As New TwentyQuestions

For i As Int32 = 0 To 4 '-- five iterations of the game
foo.StartQuestioning()
Next

'foo.Write("C:\test\20q.txt")

```

Here is an example of using the self contained structure - it's all pretty black box!

Pretty Pretty Print Out
A few run throughs provided me with this print out:

(the dashes indicate the level.. the * is the root node.. so 'bird' is two levels down from the root')

Quote

================
* Does it fly?
-L Does it have feathers?
--L Bird
--R Does it collect honey?
---L Bee
---R is it alive?
----L Flying Squirrel
----R Kite
-R Does it have scales?
--L Is it armless?
---L Snake
---R alligator
--R Does it bark?
---L Dog
---R Cow
================

Here's that same thing, but more visual.. yeah I did this by hand because I love ya!
```
____________Does it fly?_____________________
/                                             \
Does it                                              Does it
have feathers?                                     have scales?
/       \                                       /            \
Bird      Does it                            Is it                Does it
collect honey?                     armless?              bark?
/       \                          /     \               /  \
Bee      is it                    Snake    alligator     Dog   Cow
alive?
/     \
Flying     Kite
Squirrel

```

There you have it! A fun working example of a binary tree in action. Go out there and shock some people!