This program outputs the nodes of a tree using inorder tree traversal algorithm.
Each Node is prefixed by k number of “-” where k is the level of the node. I have included comments along to explain, if you find something confusing, drop a comment.
#include “iostream”
using namespace std;
//This template is for creating a node of any date type T.
template <typename T>
class tnode
{
public:// tnode is a class implementation structure. making the
// data public simplifies building class functions
T nodeValue;//value in a NODE
tnode<T> *left, *right;// pointers to the right and left child of a node
// default constructor. data not initialized
tnode()
{}
// initialize the data members
tnode (const T& item, tnode<T> *lptr = NULL,
tnode<T> *rptr = NULL):
nodeValue(item), left(lptr), right(rptr)
{}
};
//Function buildtree builds the tree based on the tree number given.
tnode<char> *buildTree(int n)
{
// 10 tnode pointers; points to the 10 items in the tree
tnode<char> *root, *b, *c, *d, *e, *f, *g, *h, *i,*j;
// parameter n specifies a tree in the range 0 – 2
switch(n)
{
// nodes d and e are leaf nodes
case 0:
d = new tnode<char> (‘D’);
e = new tnode<char> (‘E’);
b = new tnode<char> (‘B’,(tnode<char> *)NULL, d);
c = new tnode<char> (‘C’,e, (tnode<char> *)NULL);
root = new tnode<char> (‘A’,b, c);
break;
// nodes g, h, j, and d are leaf nodes
case 1:
g = new tnode<char> (‘G’);
h = new tnode<char> (‘H’);
j = new tnode<char> (‘J’);
d = new tnode<char> (‘D’);
e = new tnode<char> (‘E’,g, (tnode<char> *)NULL);
f = new tnode<char> (‘F’,h, j);
b = new tnode<char> (‘B’,d, e);
c = new tnode<char> (‘C’,(tnode<char> *)NULL, f);
root = new tnode<char> (‘A’,b, c);
break;
// nodes g, h, i and f are leaf nodes
case 2:
g = new tnode<char> (‘G’);
h = new tnode<char> (‘H’);
i = new tnode<char> (‘I’);
d = new tnode<char> (‘D’,(tnode<char> *)NULL, g);
e = new tnode<char> (‘E’,h, i);
f = new tnode<char> (‘F’);
b = new tnode<char> (‘B’,d, (tnode<char> *)NULL);
c = new tnode<char> (‘C’,e, f);
root = new tnode<char> (‘A’,b, c);
break;
}
return root;
}
//Display function outputs the nodes in the INORDER(LNR)form of tree traversal Algorithm.
void Display(tnode<char> *t,int level)
{
level++;//initially, this was assigned -1 and increases anytime inorderOutput is called to show a descent to another level.
// the recursive scan terminates on a empty subtree
if (t != NULL)
{
Display(t->left,level); // descend left
for( int i = 0; i< level;i++)// This loop outputs a number of “-” which is equal to the level of the current NODE to display.
cout<<“-“;
cout << t->nodeValue<<“n”; // output the node and move to next line.
Display(t->right,level); // descend right
}
}
int main()
{
//count determines the level of a node.
int count = -1;
//myroot is a pointer to the root of the tree.
tnode<char> *myroot;
//call buildTree() with option 1 for tree 1 and let myroot points to the returned root of the tree built.
myroot = buildTree(1);
//display function with myroot and count to display the nodes in LNR form.
Display(myroot,count);
//This code only retain the output screen until a keyboard entry is made.
cin.get();
//end of main program
return 0;
}
