At the forefront of Artificial Intelligence

Binary Decision Tree implementation in C++

University of Newcastle upon Tyne, United Kingdom

Overview

Binary decision trees (BDTs) are essentially computer science binary tree structures, enabling a conclusion state to be reached from a root node (which you could think of as a question or decision choice) via a set of binary (yes/no) decision states. In more down-to-earth terms, it is a technique to allow a conclusion to be made based on a specified problem definition. Decision trees are a popular technique in classification systems as well as in computer game AI and there are a whole host of related algorithms of interest, e.g. ID3.

Reasoning

A BDT documents the reasoning process behind a specific problem statement. It can be used to explain why a certain question is being asked by the questions location in the decision tree structure. BDTs dictate that the questions which form the nodes can only be answered with a “yes” or “no”. A tree that allows answering with a partial “yes” or “no” would have a much larger number of nodes. The design of a decision tree more often than not requires a human proficient in expert systems or decision support design (or alternatively a specialist in the problem domain). For much smaller scale solutions like this tutorial though a logical mind is enough!

Tree Structure

A BDT comprises of a set of body nodes which are attached to a root node and which terminate at n leaf nodes. The root and each body node must have connections to two other nodes, otherwise they are classed as terminating nodes where a decision outcome state has been reached. The uniform design of the tree based on two nodes leads to it being called a binary decision tree.

The leaf nodes in a BDT represent a set of terminating "answers" or decision outcome states as I have called them, the root and body nodes representing the "questions". The BDT arrives at a decision state by gaining answers to the body (yes/no) nodes. The nature of the response to a particular question dictates which node should be followed to the next question (or answer if a leaf node is arrived at). In the case of a binary decision tree the responses can only be “yes” or “no”, each corresponding to one of the two available branches at each body node.

Binary Decision Tree Implementation

The purpose of this article is to detail how a BDT can be implemented in C++. The following description and UML class diagrams represent the classes involved and a demonstration decision tree (game AI related) will be provided. Please consult the source code for further implementation details.

TreeNode

m_strQuestOrAns : string

m_iNodeID : int

m_pYesBranch : TreeNode*

m_pNoBranch : TreeNode*

The TreeNode class forms the basic node data type used within the BDT. The TreeNode has a string containing either the question to be asked (if a body node) or the actual outcome (or “answer”) if a leaf node. The data type holds pointers to both a “yes” and “no” TreeNode, similar in an abstract way to variations of the linked list data structure.

DecisionTree

m_pRootNode : TreeNode*

RemoveNode

OutputBinaryTree

Output

AskQuestion

Query

QueryBinaryTree

SearchTreeAndAddNoNode

AddNoNode

SearchTreeAndAddYesNode

AddYesNode

CreateRootNode

The DecisionTree class is the implementation of a decision tree structure. As you can see from the class diagram, the class holds a single root node element pointer form which the tree can be traversed (since the nodes themselves hold the pointers to subsequent nodes). The DecisionTree class mainly consists of tree generation methods to allow the addition of nodes and output / query methods for tree traversal.

Creating a root node

The creation of a root node is a simple process of creating the TreeNode m_pRootNode in memory. This is the root of the tree and all subsequent branches are attached to this root.

Adding a TreeNode

Both of the methods for adding a node (AddYesNode, AddNoNode) search from the root node until they find the matching node ID to add the new node to. The addition of the new node is a simple task of creating the object/s in that particular node.

Querying the tree

To query the tree we start at the root node and either ask the relevant question at the current node (if a body (question) node) or output the string representing the decision outcome state of the binary decision tree (if a leaf node). If both the yes and no branch of the current node are NULL then this means that there are no more questions to ask and the decision outcome state has been reached. Otherwise, the current node represents a question or decision point on the tree.

Outputting the tree

Outputting the tree for visual perusal is a simple method of going down the yes and no branches of the tree respectively.

This class contains no safeguards to ensure that the tree is “balanced”, meaning that the root and body nodes all have exactly two child nodes.

Example Implementation

This example demonstrates the decision tree classes in use. The sample covers the reasoning involved to determine if a game agent should switch to its “attack” mode.

The above diagram shows the structure implemented in the following code –

DecisionTree* newTree = new DecisionTree();
newTree->CreateRootNode(1,"Have you got a weapon?");
newTree->AddYesNode(1,2,"Are you close enough to attack?");
newTree->AddNoNode(1,3,"Can you tackle bare-handed?");
newTree->AddYesNode(2,4, "Attack!!!");
newTree->AddNoNode(2,5, "Don't attack!!!");
newTree->AddYesNode(3,6, "Attack!!!");
newTree->AddNoNode(3,7, "Don't attack!!!");
newTree->Output();
newTree->Query();
delete newTree;

Conclusion

There are many ways these classes could be used as the basis for further investigation of binary decision trees. They were made purposely easily to understand and to use, the separation of members into public and private / protected members would be necessary in order to ensure the robustness of this class. Further BDT specific safeguards could be added to ensure balance in the tree as well. The code was put together quickly so please don’t complain about its robustness, if you see a problem please get in touch and I will correct it!

Of course the data involved does not have to be as basic as strings for output, nor do the question nodes need to be answered in such a manual way. You could easily return function pointers or similar mechanisms depending on the decision outcome state (for example using this with a finite state machine, state changes could be determined by a decision tree structure). You could easily automatically traverse the tree answering the nodes along the way based on game data or perceptual data from a game agent for example.

Please consult the basic source code, any comments welcome. I hope this has been an interesting demonstration of the technique which you can learn from and build upon!

Submitted: 18/04/2004

Article Toolbar

BibTeX entry