数据结构、算法与应用 第8章.pdf

Chapter 8 Binary and Other Trees 信息科学与技术学院 黄方军 huangfj@mail.sysu.edu.cn 东校区实验中心B502 数据结构算法与应用 1 Bird’s-Eye View • General trees (or simply trees) • Binary trees 数据结构算法与应用 2 8.1 Trees In hierarchical data we have an ancestor- descendant, superior-subordinate whole- part, or similar relationship among the data elements. • Subtrees • Level • Degree • … 数据结构算法与应用 3 Trees 4 Nature Lover’s View Of A Tree leaves branches root 5 Computer Scientist’s View root leaves branches nodes 6 Linear Lists And Trees • Linear lists are useful for serially ordered data. – (e , e , e , …, e ) 0 1 2 n-1 – Days of week. – Months in a year. – Students in this class. • Trees are useful for hierarchically ordered data. – Employees of a corporation. • President, vice presidents, managers, and so on. – classes. • Object is at the top of the hierarchy. • Subclasses of Object are next, and so on. 7 Hierarchical Data And Trees • The element at the top of the hierarchy is the root. • Elements next in t