Binary Trees
- 参考：David J. Eck year03_c++
- 基础知识：Binary Trees，pointers，reference，recursion，oop
1. TreeNode Defination
struct TreeNode
{
int item; // The data in this node.
TreeNode *left; // Pointer to the left subtree.
TreeNOde *right; // Pointer to the right subtree.
}
2. Counting the nodes in a binary tree.
int CountNodes(TreeNode *root) // define Pointer to the root
{
if (root == NULL) return 0;
else
{
// Strat by counting the root
int cnt = 1;s
// Add the number of nodes in the left subtree
cnt += CountNodes(root -> left) ;
// Add the number of nodes in the left subtree
cnt += CountNodes(root -> right) ;
// return total
return cnt;
}
}
3. printing the items in a binary tree.
preorder : root -> left -> right
// The item in the root is printed first, followed by the
// items in the left subtree and then the items in the
// right subtree.
void preorderPrint(TreeNode *root)
{
if (root != NULL)
{
cout << root -> item << " "; // Print the root item.
preorderPrint(root -> left); // Print items in left subtrees
preorderPrint(root -> right); // Print items in right sunbtrees
}
}
postorder:left -> right ->root
// 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
void postorderPrint(Tree *root)
{
if (root != NULL)
{
postorderPrint(root->left);
postorderPrint(root->right);
cout << root->item << " ";
}
}
inorder : left -> root -> right
// 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.
void inorderPrint(TreeNode *root)
{
if (root != NULL)
{
postorderPrint(root->left);
cout << root->item << " ";
postorderPrint(root->right);
}
}
output:
preorderPrint outputs: 1 2 4 5 3 6
postorderPrint outputs: 4 5 2 6 3 1
inorderPrint outputs: 4 2 5 1 3 6
4. Binary Search(sort) Trees
In this program, nodes in the binary tree are represented using the following class, including a simple constructor that makes creating nodes easier
struct TreeNode
{
// An object of type TreeNode represents one node
// in a binary tree of strings.
string item;
TreeNode *left; // Pointer to left subtree
TreeNode *right;
TreeNode(string str) //constructor, make a node contain str
{
item = str;
left = NULL;
right = NULL;
}
}
A variable in the main program of type pointer-to-TreeNode points to the binary sort tree that is used by the program:
TreeNode *root; // Pointer to the root node in the tree.
root = NULL; // Start with an empty tree.
A recursive function named treeContains is used to search for a given item in the tree. This routine implements the search algorithm for binary trees that was outlined above:
bool treeContains(TreeNode *root, string item)
{
// Return true if item is one of the items in the binary
// sort tree to which root points. Return false if not.
// Tree is empty, so it certainly doesn't contain item.
if (root == NULL) return false;
// Yes, the item has been found in the root node.
if (item = root -> item) return true;
// If the item occurs, it must be in the left subtree.
if (item < root -> item) return treeContains(root -> left, item);
// If the item occurs, it must be in the right subtree.
else return treeContains(root -> right, item);
}
When this routine is called in the main() function, the first parameter is the local variable root, which points to the root of the entire binary sort tree.
It’s worth noting that recursion is not really essential in this case. A simple, non-recursive algorithm for searching a binary sort tree just follows the rule: Move down the tree until you find the item or reach a NULL pointer. Since the search follows a single path down the tree, it can be implemented as a while loop. Here is non-recursive version of the search routine:
bool treeContainsNR(TreeNode *root, string item)
{
// Return true if item is one of the items in the binary
// sort tree to which root points. Return false if not.
TreeNode *runner; // For running down the tree
runner = root; // start at the root node
while(true)
{
// We've fallen off the tree without finding item.
if (runner == NULL) return fasle;
// We've found the item.
if (item = runner -> item) return true;
// If the item occurs, it must be in the left subtree,
// So, advance the runner down one level to the left.
if (item < runner -> item) runner = runner -> left;
else runner = runner -> right;
}
}
A recursive function for inserting a new item into the tree is similar to the recursive search function. If the tree is empty, then we have to set the tree equal to a new tree, consisting of a single node that holds the item. Otherwise, we test whether the new item is less than or greater than the item in the root node.
Based on this test, we decide whether to insert the new item into the left subtree or into the right subtree. In either case, we do the inserting by calling the same function recursively.
Note that since the value of the parameter, root, can change in the function, this parameter must be passed by reference. Here is the definition of the insertion function. A non-recursive version is possible, but it would be much more complicated:
void treeInsert(TreeNode *&root, string newItem)
{
// Add the item to the binary sort tree to which the parameter
// "root" refers. Note that root is passed by reference since
// its value can change in the case where the tree is empty.
// The tree is empty. Set root to point to a new node containing
// the new item. This becomes the only node in the tree.
// NOTE: The left and right subtrees of root
// are automatically set to NULL by the constructor.
// This is important!
if (root == NULL) root = new TreeNode(newItem);
if (newItem < root->item) treeInsert(root->left, newItem);
else treeInsert(root->right, newItem);
}
5. Expression Trees
Another application of trees is to store mathematical expressions such as 15(x+y) or sqrt(42)+7 in a convenient form. Let’s stick for the moment to expressions made up of numbers and the operators +, -, , and /. Consider the expression 3((7+1)/4)+(17-5). This expression is made up of two subexpressions, 3((7+1)/4) and (17-5), combined with the operator “+”.
When the expression is represented as a binary tree, the root node holds the operator +, while the subtrees of the root node represent the subexpressions 3*((7+1)/4) and (17-5).
Every node in the tree holds either a number or an operator. A node that holds a number is a leaf node of the tree. A node that holds an operator has two subtrees representing the operands to which the operator applies.
An expression tree contains two types of nodes: nodes that contain numbers and nodes that contain operators. Furthermore, we might want to add other types of nodes to make the trees more useful, such as nodes that contain variables. If we want to work with expression trees in C++, how can we deal with this variety of nodes? One way – which will be frowned upon by object-oriented purists – is to include an instance variable in each node object to record which type of node it is:
// Values represent two kinds of nodes
const int NUMBER = 0, operator = 1;
struct ExpNode
{
// a node in a 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;
}
};
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.
// The value of a NUMBER node is the number it holds.
if (node->kind == NUMBER) return node->number;
else
{
// The kind must be OPERATOR.
// Get the values of the operands and combine the
// using the operator.
doule 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;
}
}
}
Although this approach works, a more object-oriented approach is to note that since there are two types of nodes, there should be two classes to represent them, ConstNode and BinOpNode. To represent the general idea of a node in an expression tree, we need another class, ExpNode.
Both ConstNode and BinOpNode will be subclasses of ExpNode. Since any actual node will be either a ConstNode or a BinOpNode, ExpNode should be an abstract class. Since one of the things we want to do with nodes is find their values, each class should have an instance method for finding the value:
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
};
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;
}
};
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
Note that the left and right operands of a BinOpNode are of type ExpNode, not BinOpNode. This allows the operand to be either a ConstNode or another BinOpNode – or any other type of ExpNode that we might eventually create. Since every ExpNode has a value() method, we can call left->value() to compute the value of the left operand. If left is in fact a ConstNode, this will call the value() method in the ConstNode class. If it is in fact a BinOpNode, then left->value() will call the value() method in the BinOpNode class. Each node knows how to compute its own value.
Although it might seem more complicated at first, the object-oriented approach has some advantages. For one thing, it doesn’t waste memory. In the original ExpNode class, only some of the instance variables in each node were actually used, and we needed an extra instance variable to keep track of the type of node. More important, though, is the fact that new types of nodes can be added more cleanly, since it can be done by creating a new subclass of ExpNode rather than by modifying an existing class.
