CIS 260 - Binary trees

Overview

Binary trees are an important and basic data structure used throughout computer science. They are also the basis of many algorithms and therefore find common use in a wide variety of programs. One of their most important uses is to maintain data in a specific order while allowing very fast insertion, deletion, modification, and access to that data.

Objectives

Binary Trees

Binary trees are an efficient way of storing arbitrary amounts of data that has to be searched frequently or kept in sorted order even though there are many changes being made. Today we will discuss binary trees in general and look at pseudocode for implementing a binary search tree data structure. In this case, we will make the class more useful by utilizing Java generics from the very beginning so that we end up with a generalized binary tree class that handles any non-primitive data type. Primitive data types will be easily handled using this data structure by encapsulating each primitive data type in its respective wrapper class.

We will discuss how items are inserted into and removed from a binary search tree. We will also discuss how to search for an item in the tree and look at different ways of traversing a binary tree (preorder, inorder, postorder).

Terminology

Resources

complete binary tree diagram

Binary tree properties and traversal

Sample code for binary trees