CMPS 260: Data Structures

Introduction

Trees are an extremely useful data structure that pops up in different places. Many hierarchical things can be represented by trees, such as the structure of an organization or the elements in an HTML document (i.e., the document object model). Binary trees also allow to search for elements quickly. The implementation of binary search trees should remind you of the linked list, but instead of each node having a next node there is a left and right node. An important aspect of trees is traversal, and we will spend some time on exploring different ways.

Module Objectives

• Describe the tree data structure
• Define tree terminology
• Implement and use the binary and binary search trees
• Implement tree traversal
• Implement searching for values in a tree

Learning Resources

• Module 9 Readings: Chapter 8 (skip ECMAScript and self balancing trees sections)
• Module 9 Slides: Chapter 8

Learning Activities

• Module 9 Assignment

For Further Study

• Read more about trees on Wikipedia