I&C SCI 46 Lecture Notes - Lecture 9: Binary Tree, Linked List, Longest Path Problem

• School: UC-Irvine
• Department: Information and Computer Science
• Course: I&C SCI 46
• Professor: Richard Pattis

Document Summary

Trees are one of the two most important data structure studied in computer science and. Mathematics (the other is graphs; in fact, trees are just a special -but important- kind of a graph: one with no cycles). Trees are useful for representing all kinds of interesting information and relationships (like the structure of a file system or the inheritance hierarchy of classes in c++ libraries), and have been studied extensively. In this lecture we will continue our study of self-referential classes by examining trees. Like linked lists, trees contain nodes: these nodes are objects instantiated from a class that contains instance variables that refer to other nodes from this same class. Although we will first examine general tree structures, we will focus most of our attention in the upcoming lectures on defining and processing binary trees. Within this category we will soon see examples of ordered (search) trees and structure (expression) trees.