I&C SCI 46 Lecture Notes - Lecture 13: Quadtree, Tree Traversal, Parent Pointer Tree

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

Document Summary

In this lecture we will look at generalizations of simple binary trees (beyond bsts, heaps, and avl trees). Specifically, we will see n-ary trees, for storing nodes that have an arbitrary number of childen; expression trees, for storing formulas, quadtrees for storing pictures, and digital trees for storing dictionaries (and sets and maps). In these trees we will also see examples of how to store a node"s children by using the set, queue, priority queue, and map templated classes, and even by using just two pointers (as in binary trees). To start, we will examine a simple way to store n-ary trees: trees that can have any number (n) of children. To store the later we might declare class folder_or_file { public: : is_file(item_is_file), name(item_name), contents(item_contents), children() bool is_file; std::string name; //for file or folder std::string contents; //used if is_file ics::arrayset children; //used if !is_file which can represent an arbitrary file structure.