Chapter 10 Trees
The
previous data structures you have studied, namely the list, the stack and the
queue, are all linear in nature, in that an item in the structure usually has
some kind of predecessor and some kind of successor.
Now
we will study a different form of data structure, the tree, where an item can
have more than one successor. A tree is nothing more than a group of nodes, but
we think of those nodes as being connected by edges. A tree has one specific
node which is called the “root” node of the tree. From the root, a group of
edges descends to other nodes, called “children”. Obviously the root is then
called a “parent”. Each child node may have a number of nodes beneath it. It
then is the parent of those nodes. Children of the same parent node are called
“siblings”. A node that has no child nodes beneath it is called a “leaf” node.
Any node together with all of its descendents is called a “subtree”.
Let me draw an example on the board. It is a little difficult
to draw one here on the web page. What is the root?
What are the leaves? What is a subtree?
A general tree T is a set of one or more nodes such
that T can be partitioned into disjoint sets:
A
single node r, the root
Sets
that are general trees, called subtrees of r
One of the most used tree structures in computer
science is a “binary tree” where a given node may have at most two children. In
particular the subtrees that can be found at the two child nodes of a node N
are called the left and right subtrees of N.
Binary trees have a number of uses. Consider the
simple example given in your text of representing an arithmetic expression via
a binary tree structure. How could we represent the
expression (a + b) * (c – d) / (e + f +
g) ? (Hint: Use the precedence of operators to determine the order in which the
computer would do the calculation.
Most of the time, nodes of a tree contain values, like numbers. A “binary search tree” is a binary tree that is “sorted” according to the values of the nodes. But it is sorted according to the following rules:
1.
For each node “n”, n’s value is greater than all values in
its left subtree.
2.
For each node “n”, n’s valus is less than all values in its
right subtree.
3.
Both the right and left subtrees are themselves binary
trees
Take the following numbers and try to draw a binary search tree with the values at the nodes:
3
9 1 7 6 8 4 2 0 5
More terminology:
The
“height of a tree is the number of nodes on the longest path from the root to a
leaf node. Each node is on what is called a “level”. The level of the root node
is 1. The level of the child nodes of the root node is 2, etc.
A
“full binary tree” is one that if it has height h, then all nodes that are at a
level less than h have two children each.
A
“complete binary tree” of height h is a binary tree that is full down to level
h-1, with level h being filled in from the left to the right.
Try to draw a full binary tree of height 4. Try to draw a complete binary tree that has 14 nodes.
How many nodes will a full binary tree of
height “h” have?
Operations of a binary tree: (these come from a particular implementation of a tree of page 441 of your textbook.
1.
BinaryTree ( )
2.
BinaryTree(Object rootItem)
3.
BinaryTree(Object rootItem, BinaryTree leftTree, BinaryTree
rightTree)
4.
setRootItem(Object newItem)
5.
attachLeft(Object newItem)
6.
attachRight(Object newItem)
7.
attachLeftSubtree(BinaryTree leftTree)
8.
attachRightSubTree(BinaryTree rightTree)
9.
detachLeftSubtree( )
10.
detachRightSubtree( )
With these definitions, what tree will finally be produced by the following lines of code:
tree1.setRootItem(“F”)
tree1.attachLeft(“G”)
tree2.setRootItem(“D”)
tree2.attachLeftSubtree(tree1)
tree3.setRootItem(“B”)
tree3.attachLeftSubtree(tree2)
tree3.attachRight(“E”)
tree4.setRootItem(“C”)
binTree.createBinaryTree(“A”,
tree3, tree4)
There are many times that we need to
traverse a binary tree, going from node to node until we have traveled to all
of the nodes, perhaps picking up information or changing information. For a
binary tree there are three ways in which this can be done:
Preorder
Inorder
Postorder
Each has a recursive method:
preorder(binTree)
if(binTree
is not empty) {
display
the data in the root of binTree
preorder(left
subtree of binTree’s root)
preorder(right
subtree of binTree’s root)
}
inorder(binTree)
if(binTree
is not empty) {
inorder(left
subtree of binTree’s root)
display
the data in the root of binTree
inorder(right
subtree of binTree’s root)
}
postorder(binTree)
if(binTree
is not empty) {
postorder(left
subtree of binTree’s root)
postorder(right
subtree of binTree’s root)
display
the data in the root of binTree
}
As you can see the only difference in the three is when we display the root data.
Let’s go back to the tree we drew for our arithmetic expression before and see what would get printed if we traversed that tree using these three algorithms.
One of the easiest ways to represent a binary tree in the computer is by using an array. Now you could be fancy in Java and define two classes, one for a given node and one for a tree:
public class TreeNode {
private Object item;
private int leftChild; // index in
array of left child
private int rightChild; // ditto for
right child
…
}
public
class BinaryTreeArrayBased {
protected final int MAX_NODES = 100;
protected TreeNode tree [ ];
protected int root; // index of tree’s root
protected int free; // index of next unused location
…
}
However, this is sometimes too fancy. In fact, just by using the array indexes properly, you can find any node directly. Suppose you had an array like this to represent a binary tree filled with integers.
int tree [ ] = new int [100];
The value for the root node will be placed in tree[0].
The value for the left child of the root will be placed in tree[1].
The value for the right child of the root will be placed in tree[2].
The value of the left child of the left child of the root will be placed in tree[3], etc.
What would the tree look
like that has the following array representation?
|
1 |
2 |
3 |
4 |
|
5 |
6 |
|
7 |
|
|
8 |
|
9 |
10 |
|
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
Can you develop a method so that, given a position (a node) in the array, will tell you which array indexes the left and right children of that node will be in?
Can you develop a method so that, given a
position (a node) in the array, will tell you which array index will hold the
parent of that node?
ONE
WORD – SEARCHING!!!!
Consider the ways in which you can store
a bunch of numbers and the fact that you know you will have to search the
numbers to see if a particular number is in the bunch. 1. You can simply use an array or list and stick the
numbers in
2.
You can use an array or list and sort the numbers
3.
You can use a binary search tree
Let’s just call out some numbers, about 20 of them and try these three methods.
I do not want to get into algorithm analysis
in this course, but can you see that the binary search tree will give you an
answer much quicker than the other two methods?
I am not going to give you an assignment on trees but there will be questions on the final about trees. Therefore we will do some of the exercises from page 485 in class on Wednesday and also go over the rest of the final.