BLOG

Posts

Creative T-shirts anyone?

My sister is quite the artist. Here are some of the designs she put up on Teepublic (here's a link to her profile):

Hi I'm an astronaut with fish around my head Please kill me... kill me now

My co-worker also has a knack for t-shirt design, except she does it one better: she prints the designs herself! Here are the links to her etsy pages for her natural oil clothing and her other humorous line. Check out some of her designs (if you're a lover of natural oils, cats, or wine, then these might be up your alley—however if you're a dude then consider buying one for your SO!):

Paging AA Love my oily life tank
Natural oil people... Dogs and beer

nodeCount and leavesCount: why D.S. Malik, why?!

As promised, here are the functions to count the total nodes and leaves in a binary tree (building off the source code in the below post). The solution isn't too difficult, and through some googling I found my way. Let's look at what we'll write for nodeCount:

if (p == NULL)
return 0;
return 1 + nodeCount(p->llink) + nodeCount(p->rlink);

First remember that this is the private function, and the argument being thrown here is from a public function that throws in root. If the root node is not null then it's going to count 1 for itself, plus it will call two recursive functions. This will branch to all the nodes in the left and the right. As you probably guessed, it'll count 1 for each node as well as call the same funtion for each of those nodes. If they don't have any child nodes, then it will stop as per return 0. Let's look at what we'll write for leavesCount:

if (p == NULL)
return 0;
if (p->llink == NULL && p->rlink == NULL)
return 1;
else
return leavesCount(p->llink) + leavesCount(p->rlink);

A little more work, but same principle. You only want to count the nodes that don't have any child nodes, so if to the left of a node is empty and to the right of that node is also empty, return 1. Else, keep going. Now unless the binary tree consists of only the root node, it's not going to hit return 1 on its first run, so this works because we're adding both the return value of the recursive functions being called on both branches.

Implementation of a binary tree in C++

I won't go into detail about the useful applications of binary trees. However if you are interested then the information provided in this StackOverflow question is great.

Below I provided close to the bare minimum in order to do an inorder traversal of a binary tree (minus the insert function definition). Most of the source code provided for the object below is from Data Structures Using C++ by D.S. Malik.

In a next post, I will go over how to define functions for counting the total nodes and the total leaves in a binary tree, which the book asks you do in a programming exercise but does not provide an answer for.

Define your node:

template <class elemType>
struct binaryTreeNode
{
elemType info;
binaryTreeNode<elemType> *llink;
binaryTreeNode<elemType> *rlink;
};

Define the class:

template <class elemType>
class binaryTreeType
{
public:
void inorderTraversal() const;
void insert(const elemType& insertItem);
binaryTreeType();
~binaryTreeType();
protected:
binaryTreeNode<elemType> *root;
private:
void inorder(binaryTreeNode<elemType> *p) const;
void destroy(binaryTreeNode<elemType>* &p);
};

Define member functions:

template <class elemType>
binaryTreeType<elemType>::binaryTreeType()
{
root = NULL;
}
template <class elemType>
void binaryTreeType<elemType>::inorderTraversal() const
{
inorder(root);
}
template <class elemType>
void binaryTreeType<elemType>::inorder(binaryTreeNode<elemType> *p) const
{
if (p != NULL)
{
inorder(p->llink);
cout << p->info << " ";
inorder(p->rlink);
}
}
template <class elemType>
void binaryTreeType<elemType>::destroy(binaryTreeNode<elemType>* &p)
{
if (p != NULL)
{
destroy(p->llink);
destroy(p->rlink);
delete p;
p = NULL;
}
}
template <class elemType>
binaryTreeType<elemType>::~binaryTreeType()
{
destroy(root);
}
PLACE DEFINITION FOR INSERT FUNCTION HERE.

Note that in the book, the author uses a derived class for binary search tree functions, such as the one we need in particular: insert. I just placed the insert function in the main class. He also uses an assert function, so be sure to include the cassert header file. Now here's your implementation:

int main()
{
int num = 0;
binaryTreeType<int> T1;
cout << "Enter a list of integers to build " <<
"binary tree T1. End with -999." << endl;
while (num != -999)
{
cin >> num;
if (num != -999)
T1.insert(num);
}
T1.inorderTraversal();
return 0;
}

Fork me on GitHub