* 13.1
Reading Assignments
* (Fri) Ch 13.3-13.4.
Assignment #5
* due Fri, Aug 4.
Data structures
* Linear form
1. arrays
2. lists
3. stacks
4. queues
* Hierarchical form
1. trees (binary trees*, other trees)
2. graphs
The terminology of trees
Components of a tree
* nodes
* Components of a tree.
* root
* The "single" node at the top of a tree.
* The node that has no parent.
* leaves
* The nodes that have no other nodes below them.
* The nodes that have no children.
* empty tree
* a tree with no nodes.
Relationships between nodes
* child
* A child of a node is an immediate successor of that node. A node may have several children.
* parent
* If C is a child node of P, then P is a parent of C. A node can have at most one parent.
* descendant (recursive definition)
1. If C is a child of P, then C is a descendant of P.
2. If C is a child of a descendant of A, then C is a descendant of A.
* Ancestor
* If D is a descendant of A, then A is an ancestor of D.
Some characteristics of a tree
* subtree
1. Any node of a tree, together with all its descendants, is a subtree.
* level (recursive definition)
1. The level of the root node is 1.
2. The level of any node other than the root is one greater than the level of its parent.
* height (depth)
1. The height of a tree is the maximum of the levels of its leaves.
Exercises
* Use the tree from slide #3 to answer these questions.
1. The ancestors of node "e" are:
2. The ancestors of node "a" are:
3. The descendants of node "h" are:
4. The descendants of node "j" are:
5. The number of non-empty subtrees is:
6. The level of node "e" is:
7. The level of node "k" is:
8. The height of the tree is:
Binary Trees
* A node in a binary tree can have at most two children.
* The two children of a node have special names:
1. the left child, and
2. the right child.
* Every child in a binary tree must be designated as the left child or the right child of its parent.
Examples of binary trees
A binary tree ADT (class diagrams)
1. The Tree class contains a pointer to a Tree_Node instance.
2. Each Tree_Node instance contains a left pointer and a right pointer.
3. The left pointer points to the left child.
4. The right pointer points to the right child.
A layout of a tree
Char_Node (different from text)
class Char_Node {
public:
Char_Node(char label, Char_Node* in_left = NULL,
Char_Node* in_right = NULL);
Boolean append_left(char label);
Boolean append_right(char label);
char get_label() const;
void store_label(char label);
Char_Node* get_left() const;
Char_Node* get_right() const;
Boolean is_leaf() const;
private:
char data;
Char_Node* left;
Char_Node* right;
};
Char_Tree (similar to text)
class Char_Tree {
public:
Char_Tree();
Boolean is_empty() const;
Boolean build_root(char label);
Char_Node* get_root() const;
private:
Char_Node* root;
};
Implementation of Char_Node
Char_Node::Char_Node(char label,
Char_Node* in_left,
Char_Node* in_right)
{
data = label;
left = in_left;
right = in_right;
}
Boolean
Char_Node::append_left(char label)
{
if (left) {
return FALSE;
} else {
left = new Char_Node(label);
return TRUE;
}
}
Boolean
Char_Node::append_right(char label)
{
if (right) {
return FALSE;
} else {
right = new Char_Node(label);
return TRUE;
}
}
char
Char_Node::get_label() const
{
return data;
}
void
Char_Node::store_label(char label)
{
data = label;
}
Char_Node*
Char_Node::get_left() const
{
return left;
}
Char_Node*
Char_Node::get_right() const
{
return right;
}
Boolean
Char_Node::is_leaf() const
{
return (!left && !right);
}
Implementation of Char_Tree
Char_Tree::Char_Tree()
{
root = NULL;
}
Boolean
Char_Tree::is_empty() const
{
return (!root);
}
Boolean
Char_Tree::build_root(char label)
{
if (root) {
return FALSE;
} else {
root = new Char_Node(label);
return TRUE;
}
}
Char_Node*
Char_Tree::get_root() const
{
return root;
}
The driver
Char_Node* root = tree.get_root();
assert(root->append_left(`h'));
assert(root->append_right(`T'));
assert(root->get_left()->append_left(`C'));
assert(root->get_left()->append_right(`a'));
assert(root->get_right()->append_right(`e'));
assert(root->get_right()->get_right()
->append_left(`r'));
assert(root->get_right()->get_right()
->append_right(`e'));
cout << "Printing contents of the binary tree.\n";
cout << "\"CharTree\" should be output: ";
cout << tree.get_root()->get_left()->get_left()
->get_label();
cout << tree.get_root()->get_left()->get_label();
cout << tree.get_root()->get_left()->get_right()
->get_label();
cout << tree.get_root()->get_label();
cout << tree.get_root()->get_right()->get_label();
cout << tree.get_root()->get_right()->get_right()
->get_left()->get_label();
cout << tree.get_root()->get_right()->get_right()
->get_label();
cout << tree.get_root()->get_right()->get_right()
->get_right()->get_label();
cout << "\n";
Binary Search Trees
* Properties:
1. No duplicates.
2. The "greater-than" (e.g. >) and "less-than" (e.g. <) relations are defined for the data values.
3. The data value of every node in the tree is
* greater than any data values of its left subtree;
* less than any data values of its right subtree.
Examples