Welcome Back!
Learning ObjectivesBy the end of this class, you should know...
Announcements - Midterm 1 next class
- Return quizzes
- Lab 5 posted
- Project Report 1 graded
- Advice: Take these reports seriously. Worth 10% of project grade.
Finish Algorithm Efficiency
Tree ADTs
Introducing Trees - Consider the ADTs we have studied so far:
- Array
- Linked List
- Queue
- Stack
- These structures all store data in a linear fashion, as in the example of a linked list show below:
- However, storing data linearly is not the only option.
- In many cases, our data might not have a linear relationship.
- Consider, for example, a company's org. chart:
- Or, consider this depiction of the relationship among the countries in the world and their cities and states:
Image source.
- Or, consider this data which is arranged into what we call a decision tree:

Image source.
- Given the nature of certain types of data, sometimes it can make more sense to organize the data in hierarchical structure.
- Also,
certain operations, such as search and insertion or deletion can be
more efficient when we organize data hierarchically rather than
linearly.
- In computer science, we can use a tree ADT to organize data hierarchically.
The Structure of the Tree ADT- Like linked lists, trees are comprised of nodes.
- These nodes store data and pointers to other nodes in the tree.
- Like the head and tail of a linked list, trees have specially-named nodes that serve important functions in the tree.
- The most important node is known as the root.
- Like the head of a linked list, a root is what allows us to access the first node in the tree.
- You can visualize a tree ADT with its root node like this:
- Trees in computer science are usually depicted with the root node on top.
- Therefore, you have to visualize the tree upside down.
- The branches of the tree are called links or edges.
- Unless the tree is empty or has size==1, each Node in the tree is connected to other nodes by these pointers (links).
- Nodes in a tree have parent-child relationships.
- Each node can have only one parent node. But a node can have 0 or more child nodes.
- The root node in the image below has four child nodes.
- The root is considered the parent node of those four child nodes.
- For example, A is considered the child node of the root and the root is considered the parent node of A.
- In other words, the terminology we use to describe trees and their nodes, is similar to that of a family tree.
- Nodes in a tree can have parents, grandparents, cousins, siblings, children and grandchildren.
- They can also have ancestors and descendants.
- For example, in the tree below, Nodes 1,4,7, and 10 and their parents are all descendants of the the root node 5.
- The root node 5 is thus their ancestor.
- Another important node in a tree is the leaf node.
- The leaf node is any node in the tree with no children.
- In other words, the links of a leaf node point to Null.
- Any node that is not the root or a leaf is called an interior node as depicted above.
- The root and leaves of the tree are exterior nodes.
Properties of Trees- Consider a tree with n nodes. How many edges will it contain.
- Exactly n-1. Why is this the case?
- The reason is that all nodes, except the root, have exactly one incoming edge.
- The depth of a node X in a tree is defined as the number of edges from the root to the node X.
- What is the depth of the root node, given this definition?
- The height of a node X is defined as the number of edges in the longest path from the node X down to a leaf node.
- What is the height of any leaf node given this definition?
- Trees themselves can also have heights. The height of any tree is the same as the height of its root.
Activity Labeling a Tree
- Given the tree below, answer the following questions:
- Step 1: Label the root and leaf nodes
- Step 2: List at least one of each of the following relationships:
- Parent-child
- Siblings
- Grandparent-grandchild
- Ancestor-Descendant
- Step 3: identify 3 interior nodes
- Step 4: label the depth of the following nodes:
- Step 5: label the height of the same nodes.
Upcoming Assignments - Lab 5 due on Monday
- Midterm 1 next class
|
|