CIS 250 - Binary trees

Prelude

There is a very good online reference for the C++ standard template library available at http://cplusplus.com/reference/stl/. We will look at the demonstration program TestContainers.cpp to see how some of the data structures we have been looking at can be used.

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
• create a templated binary search tree class
• use the BST class that we have created
• discuss any questions on current and/or future assignments

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

Pseudocode for a binary tree class is posted and will be updated if we make significant changes. We can use this in class as a starting point for writing our own binary tree implementation.

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

• Wikipedia article on binary trees
• Wikipedia article on binary search trees
• Wikipedia article on binary heaps

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]

Templated Binary Search Tree Class

We will develop a templated binary search tree class in C++ during class and it will be posted to these notes after we have finished it. We will also test it to demonstrate how it works.