TAILIEUCHUNG - Lecture Data structures and algorithms in Java (6th edition): Chapter 8 - Goodrich, Tamassia, Goldwasser

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 (. 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 .

• Cơ sở dữ liệu
• Data structures
• Data structures and algorithms
• Computer science
• Design of data structures
• Algorithms in Java
• Ebook Data structures and algorithms made easy
• Data structures and algorithms made easy
• Data structures and algorithmic puzzles
• Data structures for storing strings
• Algorithms design techniques
• algorithms
• data structure lectures
• structured document data
• teaching data structures
• algorithms in data structures
• Lecture Data Structures
• Bài giảng Cấu trúc dữ liệu
• Programming assignments
• Data structures organize data
• Resource constraints
• Lecture Data structures and algorithms
• Cấu trúc dữ liệu và giải thuật
• Abstract data type
• Lecture ECE 250
• Lecture Algorithms and data structures
• Algorithm analysis
• Graph algorithms
• Memory allocation
• AVL trees
• Binary search trees
• Red black trees
• Splay trees
• Dynamic programming