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
- define what a binary tree is
- define what a binary search tree (BST) is
- define what a binary heap is
- define pre-order traversal of a binary tree
- define post-order traversal of a binary tree
- define in-order traversal of a binary tree
- describe how nodes can be found in a binary search tree
- describe how nodes can be inserted into a binary search tree
- describe how nodes can be deleted from a binary search tree
- define common terms related to the use of binary trees
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
- binary tree: a tree data structure in which each node may have no children,
one child, or two children
- binary search tree: a binary tree where a left child, if it exists, is less
than or equal to the parent node, and the right child, if it exists, is
greater than the parent node
- binary heap: a binary tree which is complete, and in which every parent node
is greater than or equal to any child nodes it has (a maxheap), or every parent
node is less than or equal to any child nodes it has (a minheap); the entire
tree structure must follow either the minheap or the maxheap rule
- root node: the node at the top of the tree; the node which is not a child of any
other node; there is at most one root node in a binary tree (an empty tree would
have no nodes, thus no root node)
- depth: the length of the path from the root node to the current node; used
when referring to the depth of a node; the root node has depth 0
- height: the height of a tree is the longest path length in the tree; a tree with
only a root node has height 0
- leaf node: a node with no children
- siblings: siblings are nodes that share a common parent; a node in a binary tree
can have at most one sibling
- ancestor: any node that is on the path from the root node to the current node,
excluding the current node
- descendant: any node that is a child of, or child of a child, etc. of the current
node; child nodes would include all nodes of the subtree starting at the current
node with the exception of the current node itself
- subtree: the subset of the binary tree which starts at the current node and includes
all children, children of children, etc.
- size: the size of a binary tree is the number of nodes it contains
- directed edge: binary trees can be viewed as graphs, in which case each edge between
parent and child can be seen as a directed edge leading from the parent to the child
- in-degree: the number of edges leading in to a node; in a binary tree all nodes
except for the root node have in-degree 1; the root node has in-degree 0
- out-degree: the number of edges leading out of a node; in a binary tree all nodes
have out-degree equal to the number of children they have, therefore all nodes
have an out-degree of 0, 1, or 2; leaf nodes have out-degree 0
- level: a level is a subset of the nodes of a binary tree which share the same depth
- complete binary tree: a binary tree in which every level except for perhaps the last
level is complete, and in which the all of the children in the last level are filled
in completely from the left side
- balanced binary tree: a binary tree in which all leaf nodes can differ from each
other in depth by at most 1
Resources
Binary tree properties and traversal
- smallest element: in a BST go as far to the left as you can until some node
has no left child; the node you end up on is the smallest value
- largest element: in a BST go as far to the right as you can until some node
has no right child; the node you end up on is the largest value
- successor node: in a BST, the node which naturally follows the current node
can be found by finding the smallest element of the subtree rooted by the
right child of the current node; no right child means no successor
- in-order traversal: do an in-order traversal of the current node's left child
subtree, then visit the current node, and then do an in-order traversal of
the current node's right child subtree [for the diagram above, the in-order
traversal would give you: C, J, L, N, O, P]
- pre-order traversal: visit the current node, then do a pre-order traversal of
the current node's left child subtree, and then do a pre-order traversal of
the current node's right child subtree [for the diagram above, the pre-order
traversal would give you: N, J, C, L, P, O]
- post-order traversal: do a post-order traversal of the current node's left child
subtree, then do a post-order traversal of the current node's right child subtree,
and then visit the current node [for the diagram above, the in-order
traversal would give you: C, L, J, O, P, N]
Sample code for binary trees
- BST.java: implementation of a binary tree class using generics
- TestBST.java: test driver for binary tree class