Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
This chapter provides knowledge of trees. Data structures and algorithms in java provides an introduction to data structures and algorithms, including their design, analysis, and implementation. | Trees 3/19/14 Presentation for use with the textbook Data Structures and Algorithms in Java, 6th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014 Trees Mammal Dog © 2014 Goodrich, Tamassia, Goldwasser Cat Pig Trees 1 What is a Tree q q q In computer science, a tree is an abstract model of a hierarchical structure A tree consists of nodes with a parent-child relation US Applications: n n n Computers”R”Us Sales International Organization charts File systems Europe Programming environments © 2014 Goodrich, Tamassia, Goldwasser Manufacturing Trees Asia Laptops R&D Desktops Canada 2 1 Trees 3/19/14 Tree Terminology q q q q q q q Root: node without parent (A) q Subtree: tree consisting of a node and its Internal node: node with at least descendants one child (A, B, C, F) External node (a.k.a. leaf ): node A without children (E, I, J, K, G, H, D) Ancestors of a node: parent, grandparent, grand-grandparent, B C D etc. Depth of a node: number of ancestors E F G H Height of a tree: maximum depth of any node (3) Descendant of a node: child, I J K subtree grandchild, grand-grandchild, etc. © 2014 Goodrich, Tamassia, Goldwasser Trees 3 Tree ADT q q We use positions to abstract nodes Generic methods: n n n n q integer size() boolean isEmpty() Iterator iterator() Iterable positions() n n n n boolean isInternal(p) boolean isExternal(p) boolean isRoot(p) " Additional update methods may be defined by data structures implementing the Tree ADT position root() position parent(p) Iterable children(p) Integer numChildren(p) © 2014 Goodrich, Tamassia, Goldwasser n n Accessor methods: n " Query methods: Trees 4 2 Trees 3/19/14 Java Interface Methods for a Tree interface: © 2014 Goodrich, Tamassia, Goldwasser Trees 5 Preorder Traversal q q q A traversal visits the nodes of a tree in a systematic manner In a preorder traversal, a node .
