Community

Upcoming Events

Unite 2010

11/10 - 11/12 @ Montréal, Canada

GDC China

12/5 - 12/7 @ Shanghai, China

Asia Game Show 2010

12/24 - 12/27

GDC 2011

2/28 - 3/4 @ San Francisco, CA

More events...

11/10 - 11/12 @ Montréal, Canada

GDC China

12/5 - 12/7 @ Shanghai, China

Asia Game Show 2010

12/24 - 12/27

GDC 2011

2/28 - 3/4 @ San Francisco, CA

More events...

Quick Stats

66 people currently visiting GDNet.

2406 articles in the reference section.

Help us fight cancer!

Join SETI Team GDNet!

2406 articles in the reference section.

Help us fight cancer!

Join SETI Team GDNet!

## Binary TreesAs the name implies, a binary tree is simply a recursively-defined tree that can have a maximum of two children. The two children are commonly given the names , and as I said in the last article, binary trees have an additional traversal called the right childtraversal. Binary trees are used for many things, ranging from efficient searching techniques, data compression, and even arithmetic expression parsers (simple compilers). Note that some people refer to binary trees as ‘in-depth ’, which is B-Treesincorrect! B-Trees are a special kind of multi-data per node tree used for advanced balancing algorithms, and Apple Macintoshes even use B-trees for their file systems. Be careful to not call a ‘Binary Tree’ a ‘B-Tree’! Before we discuss structure implementation strategies, there are a few properties that a binary tree can have which are important.## Properties of a Binary TreeSince binary tree nodes can only have a maximum of two children, this fact introduces several properties that do not make sense on general trees. There are three important properties that a binary tree can have: , and balance. leftness## FullnessThe first property is called fullness. A binary tree is considered full if, and only if, every node in the tree has either two or zero children, and every node which has zero children is on the lowest level of the tree. Because there is no limit to how many child nodes a general tree may contain, fullness of a general tree just doesn’t make sense, but any tree which has a limit on the number of children (ternary, quadnary, etc) can have this property. ## BalanceThe second property I’d like to discuss is balance. A binary tree can be balanced, such that one branch of the tree is about the same size and depth as the other. In order to find out if a tree node is balanced, you need to find out the maximum height level of both children in each node, and if they differ by more than one level, it is considered unbalanced. The easiest way to do this is to use a recursive function (the depth() function of the binary tree class which I have provided does this) to find the maximum depth of the left child, find the maximum depth of the right child, then subtract the two. If the number is -1, 0, or 1, the node is balanced. If the difference is anything else, then it is unbalanced. Note that a balanced binary tree requires In this example, we see that the only node which is unbalanced is node #3, because the depth of its left side is 0, and the depth of the right side is 2. Subtracting 2 from 0 yields -2, thus that node is unbalanced. Note that node #1, the root, is considered balanced, since the maximum height level of both of its’ children is 3. This raises an important point: You cannot check just the root node for balancing, because it may be balanced but its child nodes may not be. Therefore, every node in the tree must be balanced in order for the tree to be considered balanced. The example tree above can be easily balanced by giving node #3 a left child. ## LeftnessThe third property I would like to discuss is leftness. This term is of my own creation, as I have never seen this term used before in textbooks, but it fairly important when dealing with some binary trees, such as So, every child on the lowest level is pushed to the left of the tree. If you were to add one more node, it would need to be a right child of node #5 if the leftness property is to be maintained. This property becomes important when dealing with array-represented binary trees and heaps. ## Structure Implementations of a Binary Tree## Linked Binary TreesBinary Trees can be General structure definition for a linked binary tree node: template <class dataType> class BinaryTree { public: typedef BinaryTree<dataType> node; // -------------------------------------------------------------- // Name: BinaryTree::m_data // Description: data stored in current tree node // -------------------------------------------------------------- dataType m_data; // -------------------------------------------------------------- // Name: BinaryTree::m_parent // Description: pointer to the parent of the node. // -------------------------------------------------------------- node* m_parent; // -------------------------------------------------------------- // Name: BinaryTree::m_left // Description: pointer to the left child of the node. // -------------------------------------------------------------- node* m_left; // -------------------------------------------------------------- // Name: BinaryTree::m_right // Description: pointer to the right child of the node. // -------------------------------------------------------------- node* m_right; }; Notice how I made all the data public. While this destroys any semblance of good Object Oriented Design (OOD), there is a reason behind this. First of all, this is a tutorial on trees, not on object oriented design. If I were to go all out with OOD, I’d be using all sorts of esoteric features, totally eclipsing the theory behind the trees. Second, the binary tree node class is so simple, its definition is not likely to change anytime in the near future.
## Arrayed Binary TreesThere is one major variation of the structure of a binary tree: an in the next tutorial. Right now, you should just know that the tree is represented as one large array:heapsIt is traditional to represent arrayed nodes as boxes, rather than circles. This makes it easy to distinguish between the major structural differences. Note how the indexing starts at 1, and not 0. This is because of the rules that must be followed when traversing an arrayed binary tree: The
The
The So, having an index of 0 would make traversal impossible. Take special care to note this fact: if node #2 does not exist within the tree, indices 2, 4, 5, 8, 9, 10, and 11 are all unusable, and therefore wasted. Also note that adding a right child to node #15 would increase the size of the array to 31 indices, of which #16 through #30 would not be used.
d represents the maximum depth of any given node in the tree.## Methods of a Binary TreeHere is a listing of all the methods in the binary tree class: // ---------------------------------------------------------------- // Name: BinaryTree::BinaryTree // Description: Default Constructor. Creates a tree node. // Arguments: - data: data to initialize node with // Return Value: None. // ---------------------------------------------------------------- BinaryTree( dataType p_data ) // ---------------------------------------------------------------- // Name: BinaryTree::~BinaryTree // Description: Destructor. Deletes all child nodes. // Arguments: None. // Return Value: None. // ---------------------------------------------------------------- ~BinaryTree() // ---------------------------------------------------------------- // Name: BinaryTree::setLeft // Description: sets the left child pointer, rearranging parents // as necessary. Existing left child is promoted // to the root of its own tree, but beware, it is // up to the client to remember where it is, or // else there is a memory leak. // Arguments: pointer to a binary tree node. // Return Value: None. // ---------------------------------------------------------------- void setLeft( node* p_left ) // ---------------------------------------------------------------- // Name: BinaryTree::setRight // Description: sets the right child pointer, rearranging parents // as necessary. Existing right child is promoted // to the root of its own tree, but beware, it is // up to the client to remember where it is, or // else there is a memory leak. // Arguments: pointer to a binary tree node. // Return Value: None. // ---------------------------------------------------------------- void setRight( node* p_right ) // ---------------------------------------------------------------- // Name: BinaryTree::preorder // Description: processes the tree using a pre-order traversal // Arguments: - process: A function which takes a reference // to a dataType and performs an // operation on it. // Return Value: None. // ---------------------------------------------------------------- void preorder( void (*process)(dataType& item) ) // ---------------------------------------------------------------- // Name: BinaryTree::postorder // Description: processes the tree using a post-order traversal // Arguments: - process: A function which takes a reference // to a dataType and performs an // operation on it. // Return Value: None. // ---------------------------------------------------------------- void postorder( void (*process)(dataType& item) ) // ---------------------------------------------------------------- // Name: BinaryTree::inorder // Description: processes the tree using an in-order traversal // Arguments: - process: A function which takes a reference // to a dataType and performs an // operation on it. // Return Value: None. // ---------------------------------------------------------------- void inorder( void (*process)(dataType& item) ) // ---------------------------------------------------------------- // Name: BinaryTree::isLeft // Description: determines if node is a left subtree. Note that // a result of false does NOT mean that it is a // right child; it may be a root instead. // Arguments: None. // Return Value: True or False. // ---------------------------------------------------------------- bool isLeft() // ---------------------------------------------------------------- // Name: BinaryTree::isRight // Description: determines if node is a right subtree. Note that // a result of false does NOT mean that it is a // left child; it may be a root instead. // Arguments: None. // Return Value: True or False. // ---------------------------------------------------------------- bool isRight() // ---------------------------------------------------------------- // Name: BinaryTree::isRoot // Description: determines if node is a root node. // Arguments: None. // Return Value: True or False. // ---------------------------------------------------------------- bool isRoot() // ---------------------------------------------------------------- // Name: BinaryTree::count // Description: recursively counts all children. // Arguments: None. // Return Value: the number of children. // ---------------------------------------------------------------- int count() // ---------------------------------------------------------------- // Name: BinaryTree::depth // Description: recursively determines the lowest relative // depth of all its children. // Arguments: None. // Return Value: the lowest depth of the current node. // ---------------------------------------------------------------- int depth() The setLeft/Right functions provide an easy way to set children in the tree. If a child already exists where you are inserting, it sets the existing child’s parent pointer to 0, making it a new tree. Then it puts the passed in node to whichever side you told it, and then sets the new nodes parent to the current node. All of this could be done manually, of course, but the method makes it simpler because that sequence of events happens quite frequently. Next, I’ve added another traversal routine: inorder. I briefly touched on this in the last tutorial, so I’m going to explain it more in depth this time. An in-order traversal traverses the tree in this order: - process left child
- process current data
- process right child
So the traversal only makes sense on binary trees, because it processes the current data in any given node between its two children. isLeft/Right/Root should all make sense, they are just simple status functions. count and depth are the two recursive status routines. As such, they should be used sparingly, because they are recalculated on each call. Count is simple to understand, it just recursively tells each of its children to return its count, adds one, and returns the result. Depth is a bit more complex, as it takes the maximum of the relative depth of its left child and the relative depth of the right child, adds one and returns the result. The tree balancing routines discussed later on uses this method. int depth() { int left = -1; // clear left int right = -1; // and right if( m_left != 0 ) // if the left child exists left = m_left->depth(); // update the left depth if( m_right != 0 ) // if the right child exists right = m_right->depth(); // update the right depth if( left > right ) // if left is larger than return left + 1; // right, return left + 1 return right + 1; // else return right + 1 } |