Jess: Data Structures, Week 5

Chapter 4: Trees

4.1 For the tree in Figure 4.70:
a. Which node is the root?

/usr is the root

b. Which nodes are leaves?
junk, junk, work,

4.2 For each node in the tree of Figure 4.70:
a. Name the parent node.

Node: mark, alex, bill -> parent = /usr
Node: book, course, junk -> parent = mark
Node: junk -> parent = alex
Node: work, course -> parent = bill

b. List the children.
ch1.r, ch2.r, ch3.r, syl.r, syl.r, syl.r, grades, prog1.r, prog2.r

c. List the siblings.
ch1.r, ch2.r, ch3.r, syl.r, prog1.r, prog2.r

d. Compute the depth.
5

e. Compute the height.
5

4.3 What is the depth of the tree in Figure 4.70?
5

A preorder traversal is where work at a node is performed before (pre) its children are processed. In a postorder traversal, the work at a node is performed after (post) its children are evaluated.

Binary Trees
A binary tree is a tree in which no node can have more than two children. Binary trees are used for a lot of other important uses instead of searching, such as compiler design. Here is an example from the book of a binary tree with the root having two nodes (TL and TR).

Binary Search Trees
The property that makes a binary tree into a binary search tree is that for every node, X, in the tree, the values of all the items in its left subtree are smaller than the item in X, and the values of all the items in its right subtree are larger than the item in X.
smaller (left) ← Node X →(right) larger

For example, below, the tree on the left is a binary search tree, but the tree on the right is not. The tree on the right is not a binary search tree because it has a node with item 7 on the left subtree of a node with item 6.