Notes 10a:
Addendum A to Essentials of Data Structures, Cpt 10

Math 61 -- D. C. Smolarski, S.J.
Santa Clara University, Department of Mathematics and Computer Science

Contents

• Tree Type Declaration (DCS 10.3)
• Generating and Printing a Tree

Tree Type Declaration

class node
{   public:
	node *left;
	int info;
	node *right;
};

Generating and Printing a Tree

The gentree differs slightly from that found in The Essentials of Data Structures to avoid the global variable in C++ (a style highly discourage).

//* * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
//*       F U N C T I O N   G E N T R E E                   *
//      This generates a tree.  n is a small positive integer
//	specifying an upper bound on the depth
//	of the tree.  The nodes can have two children, and
//	an information field.  The information field is 
//*	given a sequential node number.                     *
//* * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
node *gentree(int n, int & numnode)
{	node *t;
	t = new node;
	t->info = ++numnode; //numnode is the unique number
		     //stored in each node after its creation
	if (n<=0)  t->left = NULL;
	else       t->left = gentree(n-1,numnode);
	if (n<=0)  t->right = NULL;
	else	   t->right = gentree(n-1,numnode);
	return(t);
}

//* * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
//*       P R O C E D U R E   I N P R I N T               *
//*	The information fields of the nodes of a tree
//	are printed in inorder traversal order.           *
//* * * * * * * * * * * * * * * * * * * * * * * * * * * * *
void inprint(node *t)
{	if (t!=NULL)
	{	inprint(t->left);
		cout << t->info << endl;
		inprint(t->right);
	}
}

//* * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
//* main program
//* * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
int main ()
{	node *root;
	int numnode;
//  (* initialization *)
	numnode = 0;
	root = gentree(4,numnode);
	inprint(root);
	return 0;
}

This page is maintained by Dennis C. Smolarski, S.J.
© Copyright 1998, 1999 Dennis C. Smolarski, SJ, All rights reserved.
Last changed: 7 April 1999.