Chapter 23 - Binary trees. In this chapter, the learning objectives are: Learn about binary trees; learn how to represent and handle a binary tree using the TreeNode class; learn about binary search trees; review sets and maps, and the classes that implement them. | Java Methods A & AB Object-Oriented Programming and Data Structures Maria Litvin ● Gary Litvin Copyright © 2006 by Maria Litvin, Gary Litvin, and Skylight Publishing. All rights reserved. Binary Trees 23- A heap is another type of a binary tree. It is used for implementing a priority queue efficiently (Chapter 25). Objectives: Learn about binary trees Learn how to represent and handle a binary tree using the TreeNode class Learn about binary search trees Review sets and maps, and the classes that implement them 23- The AP CS course description states that students must be familiar with the and Map interfaces and and TreeMap classes, as well as with manipulating “do-it-yourself” binary trees based on the College Board’s TreeNode class. Some Applications of Trees Data retrieval (search) Priority queues Decision systems Hierarchies Games 23- The key property of trees for data retrieval and decision systems is that a shallow tree can . | Java Methods A & AB Object-Oriented Programming and Data Structures Maria Litvin ● Gary Litvin Copyright © 2006 by Maria Litvin, Gary Litvin, and Skylight Publishing. All rights reserved. Binary Trees 23- A heap is another type of a binary tree. It is used for implementing a priority queue efficiently (Chapter 25). Objectives: Learn about binary trees Learn how to represent and handle a binary tree using the TreeNode class Learn about binary search trees Review sets and maps, and the classes that implement them 23- The AP CS course description states that students must be familiar with the and Map interfaces and and TreeMap classes, as well as with manipulating “do-it-yourself” binary trees based on the College Board’s TreeNode class. Some Applications of Trees Data retrieval (search) Priority queues Decision systems Hierarchies Games 23- The key property of trees for data retrieval and decision systems is that a shallow tree can hold lots of data. In strategy games, this property works against us and becomes a major stumbling block: if we consider all the possible responses to a given move, then all the responses to those responses, etc., the tree of possible game paths grows so fast that it is not feasible to plan ahead beyond a few moves. Binary Tree Terms Root Leaves (nodes with no children) Left child Right child Number of levels (equals 5 here) node node’s right subtree 23- Some people define the depth of a tree as the total number of levels in the tree. Other people define depth as the length of the longest path from the root to a leaf (which is one less than the number of levels). Binary Tree Properties A shallow tree can hold many nodes. For example, a tree with 20 levels can have 220 - 1 (approximately 1,000,000) nodes. At each node a decision can be made on where to proceed, left or right (used in binary search trees). The path to the bottom is relatively short as compared to the total number of .
