Page 1 of 1

Binary Trees, the Question Game, and car rides! Rate Topic: -----

#1 modi123_1  Icon User is offline

  • Suitor #2
  • member icon



Reputation: 8390
  • View blog
  • Posts: 31,200
  • 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>
    Public Sub ReadFilePreOrder(ByRef myNode As Node, ByRef sr As IO.StreamReader)
        Dim temp As String = String.Empty

        temp = sr.ReadLine

        If temp = "#" Then
            Exit Sub
        Else
            myNode = New Node(temp)
            ReadFilePreOrder(myNode.LeftNode, sr)
            ReadFilePreOrder(myNode.RightNode, sr)
        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

        '-- and two first answers
        _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)
            sIn = Console.ReadLine()

            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))
        sIn = Console.ReadLine()

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

            _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
            sr = New IO.StreamReader(filelocation)

            _binaryTree.Root = Nothing

            _binaryTree.ReadFilePreOrder(_binaryTree.Root, sr)
            _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")  
        'foo.Read("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!

Advanced topics
- Try to modify the code to load the binary tree data before each question session, and save the data afterwards.
- Read up on tree balancing, how that might positively affect the tree, and try to implement it.
- Think of a way to prune nodes that have the wrong question entered. Is there a better way off preserving questions and answers from being totally wiped out if by removing a parent node?
- Think about if it is possible to morph this into a ternary tree..

Is This A Good Question/Topic? 7
  • +

Page 1 of 1