ACSL Handout: Data Structures 
Interactive Data Structure Visualizations is an incredible
web site that adds visualization to various data structures.
Under "Binary Trees", click on Transversals.
Read about the different ways that you can traverse a binary tree.
Preorder (Prefix): A preorder binary tree traversal uses the
order DLR, data--extracting the data, left and then right.
Inorder (Infix): A inorder binary tree traversal uses the
order LDR, left, data--extracting the data, and then right.
Postorder (Postfix): A postorder binary tree traversal uses
the order LRD, first left, then right, then data--extracting the data.
Clicking on the "Explanation" button in the lower left corner of the web page
displays the source code in the Ada computer programming language of the
different traversals of a binary tree. (See below for Java source code.)
Click the "Start Visualization" button to play an Ada applet where
you can examine how to search for a node in a binary tree by using one
of several diffent search patterns == search the tree in one of several
different "orders".
A binary search tree is a binary tree each of whose nodes contains a value
that is greater than all the values in the nodes in its left subtree and
less than all the values in the nodes in its right subtree. It is knowledge
that the tree was built in this sequence that makes it possible to use a
binary search to find a specific node in the tree.
You cannot close the applet by clicking
the "X" close button in the top right corner. Instead, you must
click the "Stop Visualization" button
in the bottom right corner of the web page itself.
Under "Binary Trees", clock on Search Trees.
Read about the advantages of a Binary Search Tree.
Click the "Start Visualization" button to play an Ada applet where you
can examine the three Fundamental Operations of a
Binary Search Tree.
Insert
Delete
Find
Clicking on the "Explanation" button in the lower left corner of the web page
displays the source in the Ada computer programming language of the fundamental
operations of a binary search tree. (See below for Java source code.)
You cannot close the applet by clicking
the "X" close button in the top right corner. Instead, you must
click the "Stop Visualization" button
in the bottom right corner of the web page itself.
Java Source Code for a non-recursive binary search tree
(Horstmann's Big Java, 2nd Ed, pp 803-807)
In a trilogy of extraordinary books (third not yet published), Robert Sedgewick has
written what many believe to be the definititve treatment of algorithms.
Volume I in four parts of that trilogy was originally published using the Pascal
programming language and later C++ and Java. That volume covered fundamental concepts,
data structures, sorting algorithms, and searching algorithms. Then came Volume II
covering graphs and graph algorithms available in three languages: Pascal, C++ and Java.
The third volume has not yet been published in any language, but reportedly will cover
strings, computational geometry and advanced algorithms and applications.
Algorithms for working with Binary Search Trees are comprehensively addressed in Sedgewick's
Algorithms in Java, 3rd Edition, Volume I, pages 531-554)
Robert Sedgewick and Kevin Wayne together published what may well be the best introductory
computer science book yet written:
Introduction to Programming in Java. An excerpt from an early draft
of that book that was posted on Sedgewick's web site discussed
the binary search tree as a recursive structure. (pp 619-631)
|
