CSE 116 Lecture Notes - Lecture 25: Binary Tree, Abstract Data Type, Genderqueer

• School: University at Buffalo
• Department: Computer Science & Engineering
• Course: CSE 116
• Professor: Matthew Hertz

Document Summary

Represent hierarchical relationships: parent-child bases of this abstract data type real-world example: directories and files. Yet another collection: any implementation is okay, # of elements is its size some things are familiar, using nodes to hold elements. Others are very different: node class has little overlap, cannot discuss next & prev. Tree rooted at node a: (cid:862)top(cid:863) or (cid:862)start(cid:863) of tree. B, c, d are children of a: a is parent of b, c, d, b, c, d are siblings, e, f, g, h are grandchildren of a. Nodes either leaf or interior: both or neither not options. A, b, c, f are parents: at least 1 child for each, also (cid:272)alled (cid:862)i(cid:374)terior (cid:374)odes(cid:863) (cid:862)lea(cid:448)es(cid:863) (cid:374)a(cid:373)e of others leaf node has no children. Trees are recursive structure: subtree defined by a node, c is root of this subtree, b root of this subtree, d root of this subtree.