* 13.2(m,n,o), 13.3(m,n,o), 13.4(a).
Reading Assignments
* Ch 11-11.3.
Assignment #5
* due Mon, Aug 7.
* 1 extra credit if you turn in today.
Assignment #6
* due Wed, Aug 16.
Searching a binary search tree
class Char_Node { // partial declaration required
// in .h file
friend class Char_Tree;
private:
...
Boolean is_member(char label) const;
char data;
Char_Node* left;
Char_Node* right;
};
class Char_Tree {
public
...
Boolean is_member(char label) const;
private:
Char_Node* root;
};
Boolean
Char_Tree::is_member(char label) const
{
return root && root->is_member(label);
}
Boolean
Char_Node::is_member(char label) const
{
if (data == label) {
return TRUE;
} else if (data < label) {
return left && left->is_member(label);
} else {
return right && right->is_member(label);
}
}
Inserting values (specification)
class Char_Node { // only partial declaration
// required in .h file
...
Boolean insert(char label);
};
class Char_Tree {
...
Boolean insert(char label);
};
Boolean
Char_Tree::insert(char label)
{
if (root) {
return root->insert(label);
} else {
root = new Char_Node(label);
return TRUE;
}
}
Boolean
Char_Node::insert(char label)
{
if (label == data) {
return FALSE;
} else if (label < data) {
if (left) {
return left->insert(label);
} else {
left = new Char_Node(label);
return TRUE;
}
} else {
if (right) {
return right->insert(label);
} else {
right = new Char_Node(label);
return TRUE;
}
}
}
Exercise
* What is the result of inserting the following to an empty tree?
1. c
2. b
3. s
4. t
5. r
6. e
Binary Tree Traversal
* An algorithm for processing or visiting every node of a tree is referred to as a "tree traversal algorithm".
* Inorder traversal
1. visit the left subtree.
2. visit the current node.
3. visit the right subtree.
* Preorder traversal
1. visit the current node.
2. visit the left subtree.
3. visit the right subtree.
* Postorder traversal
1. visit the left subtree.
2. visit the right subtree.
3. visit the current node.
e.g. print the data values of the nodes
class Char_Node {
...
void print_preorder(ostream& ost) const;
void print_inorder(ostream& ost) const;
void print_postorder(ostream& ost) const;
};
class Char_Tree {
...
void print_preorder(ostream& ost) const;
void print_inorder(ostream& ost) const;
void print_postorder(ostream& ost) const;
};
void
Char_Tree::print_preorder(ostream& ost) const
{
if (root) {
root->print_preorder(ost);
}
ost << "\n";
}
void
Char_Node::print_preorder(ostream& ost) const
{
ost << " " << data;
if (left) {
left->print_preorder(ost);
}
if (right) {
right->print_preorder(ost);
}
}
void
Char_Tree::print_inorder(ostream& ost) const
{
if (root) {
root->print_inorder(ost);
}
ost << "\n";
}
void
Char_Node::print_inorder(ostream& ost) const
{
if (left) {
left->print_inorder(ost);
}
ost << " " << data;
if (right) {
right->print_inorder(ost);
}
}
void
Char_Tree::print_postorder(ostream& ost) const
{
if (root) {
root->print_postorder(ost);
}
ost << "\n";
}
void
Char_Node::print_postorder(ostream& ost) const
{
if (left) {
left->print_postorder(ost);
}
if (right) {
right->print_postorder(ost);
}
ost << " " << data;
}
Destructors
Char_Node::~Char_Node()
{
delete left;
delete right;
}
Char_Tree::~Char_Tree()
{
delete root;
}