Chapter 24 - 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. | Binary Trees Copyright © 2015 by Maria Litvin, Gary Litvin, and Skylight Publishing. All rights reserved. Java Methods Object-Oriented Programming and Data Structures Maria Litvin ● Gary Litvin 3rd AP edition 24- A heap is another type of a binary tree. It is used for implementing a priority queue efficiently (Chapter 26). 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 24- And review recursion. Some Applications of Trees Data retrieval (search) Priority queues Decision systems Hierarchies Games 24- 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 . | Binary Trees Copyright © 2015 by Maria Litvin, Gary Litvin, and Skylight Publishing. All rights reserved. Java Methods Object-Oriented Programming and Data Structures Maria Litvin ● Gary Litvin 3rd AP edition 24- A heap is another type of a binary tree. It is used for implementing a priority queue efficiently (Chapter 26). 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 24- And review recursion. Some Applications of Trees Data retrieval (search) Priority queues Decision systems Hierarchies Games 24- 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 24- 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 binary 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 nodes. 24- Again, this is the key property: a shallow tree can hold lots of data. A binary tree with 30 levels can have over 1,000,000,000 nodes. The TreeNode Class Represents a node of a binary tree Is similar to .
