This type of recursion is called a convolution. One can solve this for T(N) usin
ID: 3631417 • Letter: T
Question
This type of recursion is called a convolution. One can solve this for T(N) using the method of
generating functions (known also as the z transform) but this is not our topic here.
We verify this recursion
T(0) = 1
T(1) = T(0)T(0) = 1
T(2) = T(0)T(1) + T(1)T(0) = 1 + 1 = 2
T(3) = T(0)T(2) + T(1)T(1) + T(2)T(0) = 2 + 1 + 2 = 5
T(4) = T(0)T(3) + T(1)T(2) + T(2)T(1) + T(3)T(0) = 5 + 2 + 2 + 5 = 14
And we program this recursion to get
0 1
1 1
2 2
3 5
....
....
19 1767263190
20 6564120420
...
99 227508830794229349661819540395688853956041682601541047340
An 32 bit integer can not store the number of trees when N > 19, so we need a large integer
class.
Assignment
• Write an ANSI C++ program that calculates the number of binary trees up to 200 nodes.
Important Points
• Within your code, implement a LargeInteger class that can do addition and multiplication with
large integers.
• You are expected to use C++ with as many related features as possible. This can (but does
not have to) include operator overloading, classes, dynamic memory management, templates.
• Make sure that your output format is exactly as above example, that is each line i for i 2 [0, 200]
should have i T(i), and only that. This is important for the automated testing of correctness
of your program.
Explanation / Answer
int countNodes( TreeNode *root ) {
// Count the nodes in the binary tree to which
// root points, and return the answer.
if ( root == NULL )
return 0; // The tree is empty. It contains no nodes.
else {
int count = 1; // Start by counting the root.
count += countNodes(root->left); // Add the number of nodes
// in the left subtree.
count += countNodes(root->right); // Add the number of nodes
// in the right subtree.
return count; // Return the total.
}
} // end countNodes()
void preorderPrint( TreeNode *root ) {
// Print all the items in the tree to which root points.
// The item in the root is printed first, followed by the
// items in the left subtree and then the items in the
// right subtree.
if ( root != NULL ) { // (Otherwise, there's nothing to print.)
cout << root->item << " "; // Print the root item.
preorderPrint( root->left ); // Print items in left subtree.
preorderPrint( root->right ); // Print items in right subtree.
}
} // end preorderPrint()
void postorderPrint( TreeNode *root ) {
// Print all the items in the tree to which root points.
// The items in the left subtree are printed first, followed
// by the items in the right subtree and then the item in the
// root node.
if ( root != NULL ) { // (Otherwise, there's nothing to print.)
postorderPrint( root->left ); // Print items in left subtree.
postorderPrint( root->right ); // Print items in right subtree.
cout << root->item << " "; // Print the root item.
}
} // end postorderPrint()
void inorderPrint( TreeNode *root ) {
// Print all the items in the tree to which root points.
// The items in the left subtree are printed first, followed
// by the item in the root node, followed by the items in
// the right subtree.
if ( root != NULL ) { // (Otherwise, there's nothing to print.)
inorderPrint( root->left ); // Print items in left subtree.
cout << root->item << " "; // Print the root item.
inorderPrint( root->right ); // Print items in right subtree.
}
} // end inorderPrint()
Each of these functions can be applied to the binary tree shown in the illustration at the beginning of this section. The order in which the items are printed differs in each case:
preorderPrint outputs: 1 2 4 5 3 6
postorderPrint outputs: 4 5 2 6 3 1
inorderPrint outputs: 4 2 5 1 3 6
In preorderPrint, for example, the item at the root of the tree, 1, is output before anything else. But the preorder printing also applies to each of the subtrees of the root. The root item of the left subtree, 2, is printed before the other items in that subtree, 4 and 5. As for the right subtree of the root, 3 is output before 6. A preorder traversal applies at all levels in the tree. The other two traversal orders can be analyzed similarly.
const int NUMBER = 0, // Values representing two kinds of nodes.
OPERATOR = 1;
struct ExpNode { // A node in an expression tree.
int kind; // Which type of node is this?
// (Value is NUMBER or OPERATOR.)
double number; // The value in a node of type NUMBER.
char op; // The operator in a node of type OPERATOR.
ExpNode *left; // Pointers to subtrees,
ExpNode *right; // in a node of type OPERATOR.
ExpNode( double val ) {
// Constructor for making a node of type NUMBER.
kind = NUMBER;
number = val;
}
ExpNode( char op, ExpNode *left, ExpNode *right ) {
// Constructor for making a node of type OPERATOR.
kind = OPERATOR;
this->op = op;
this->left = left;
this->right = right;
}
}; // end ExpNode
Given this definition, the following recursive function will find the value of an expression tree:
double getValue( ExpNode *node ) {
// Return the value of the expression represented by
// the tree to which node refers. Node must be non-NULL.
if ( node->kind == NUMBER ) {
// The value of a NUMBER node is the number it holds.
return node->number;
}
else { // The kind must be OPERATOR.
// Get the values of the operands and combine them
// using the operator.
double leftVal = getValue( node->left );
double rightVal = getValue( node->right );
switch ( node->op ) {
case '+': return leftVal + rightVal;
case '-': return leftVal - rightVal;
case '*': return leftVal * rightVal;
case '/': return leftVal / rightVal;
}
}
} // end getValue()
OR
class ExpNode {
// Represents a node of any type in an expression tree.
// This is an "abstract" class, since it contains an undefined
// function, value(), that must be defined in subclasses.
// The word "virtual" says that the defintion can change
// in a subclass. The "= 0" says that this function has
// no definition in this class.
public:
virtual double value() = 0; // Return the value of this node.
}; // end class ExpNode
class ConstNode : public ExpNode {
// Represents a node that holds a number. (The
// ": public ExpNode" says that this class is
// a subclass of ExpNode.)
double number; // The number in the node.
public:
ConstNode( double val ) {
// Constructor. Create a node to hold val.
number = val;
}
double value() {
// The value is just the number that the node holds.
return number;
}
}; // end class ConstNode
class BinOpNode : public ExpNode {
// Represents a node that holds an operator.
char op; // The operator.
ExpNode *left; // The left operand.
ExpNode *right; // The right operand.
public:
BinOpNode( char op, ExpNode *left, ExpNode *right ) {
// Constructor. Create a node to hold the given data.
this->op = op;
this->left = left;
this->right = right;
}
double value() {
// To get the value, compute the value of the left and
// right operands, and combine them with the operator.
double leftVal = left->value();
double rightVal = right->value();
switch ( op ) {
case '+': return leftVal + rightVal;
case '-': return leftVal - rightVal;
case '*': return leftVal * rightVal;
case '/': return leftVal / rightVal;
}
}
}; // end class BinOpNode
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.