Binary Tree - Data Structures Visualization
Binary Tree
Binary trees are one of the fundamental data storage structures used in programming.Why Use Binary Trees
Usually, because it combines the advantages of two other structures: an ordered array and a linked list. You can search a tree quickly, as you can an ordered array, and you can also insert and delete items quickly, as you can with a linked list.It would be nice if there were a data structure with the quick insertion and deletion of a linked list, and also the quick searching of an ordered array. Trees provide both these characteristics, and are also one of the most interesting data structures.
Definition
If every node in a tree can have at most two children, the tree is called a Binary Tree.The two children of each node in a binary tree are called the "left child" and the "right child", corresponding to their position when you draw a picture of a tree.
A node in a binary tree doesn't necessarily have the maximum of two children; it may have only a left child, or only a right child, or it can have no children at all (in which case it's a leaf).
The kind of binary tree we'll be dealing with is technically a binary search tree.
The defining characteristic of a binary search tree is this: a node's left child must have a key less than its parent, and a node's right child must have a key greater than or equal to its parent
How Do Binary Trees Work ?
Let's see how to carry out the common binary-tree operations of finding a node with a given key, inserting a new node, traversing the tree, and deleting a node.For each of these operations we'll first show to use the Tree-Applet to carry it out; then we'll look at the corresponding Java code.
The Binary Tree Applet
The Binary Tree Applet (alternative)
Note: you can run it from any computer with appletviewer 1.2 by typing: appletviewer http://lsdis.cs.uga.edu/~aleman/mams/csci6900/hci/partc/bintree/prototype.php
Representing the Tree in Java Code
The most common approach to represent a tree in the computer's memory is to store the nodes at unrelated locations in memory and connect them using references in each node that points to its children.The Node Class
First, we need a class of node objects. These objects contain the data representing the objects being stored and also references to each of the node's two children. Here's how that looks:
class Node
{
int key;
Object otherInfo;
Node leftChild;
Node rightChild;
}
The BinaryTree ClassWe'll also need a class from which to instantiate the tree itself; the object that holds all the nodes. We'll call this class BinaryTree. It has only one field: a Node variable that holds the root. It doesn't need fields for the other nodes because they are all accessed from the root.
The BinaryTree class has a number of methods: some for finding, inserting, and deleting nodes, several for different kinds of traverses, and one to display the tree. Here's a skeleton version:
class BinaryTree
{
private Node root;
public void find(int key)
{
}
public void insert(int key, Object otherInfo)
{
}
public void delete(int key)
{
}
}
Java Code for Finding a Node
Here's the code for the find() method of the BinaryTree class:
public Node find(int key) // find node with given key
{ // (assumes non-empty tree)
Node current = root; // start at root
while(current.iData != key) // while no match,
{
if(key < current.iData) // go left?
current = current.leftChild;
else // or go right?
current = current.rightChild;
if(current == null) // if no child,
return null; // didn't find it
}
return current; // found it
} // end find()
EfficiencyHow long it takes to find a node depends on how many levels down it is situated.
If the tree is full then it is O(log N)
Java Code for Inserting a Node
The insert() method starts by creating the new node, using the data supplied as arguments.Next, insert() must determine where to insert the new node. This is done using roughly the same code as finding a node, described in the section on find(). The difference is that when you're simply trying to find a node and you encounter a null (non-existing) node, you know the node you're looking for doesn't exist so you can return immediately. When you're trying to insert a node you insert it before returning.
Here's the code for the insert() method of the BinaryTree class:
public void insert(int id, double dd)
{
Node newNode = new Node(); // make new node
newNode.iData = id; // insert data
newNode.dData = dd;
if(root==null) // no node in root
root = newNode;
else // root occupied
{
Node current = root; // start at root
Node parent;
while(true) // (exits internally)
{
parent = current;
if(id < current.iData) // go left?
{
current = current.leftChild;
if(current == null) // if end of the line,
{ // insert on left
parent.leftChild = newNode;
return;
}
} // end if go left
else // or go right?
{
current = current.rightChild;
if(current == null) // if end of the line
{ // insert on right
parent.rightChild = newNode;
return;
}
} // end else go right
} // end while
} // end else not root
} // end insert()
Java Code for Traversing
The actual code for inorder traversal is so simple, the method inOrder(), performs the three steps: call itself to traverse the node's subtree, visit the node, call itself to traverse the node's right subtree.Like any recursive function, there must be a base case: the condition that causes the method to return immediately, without calling itself. In inOrder() this happens when the node passed as an argument is null.
Here's the code for the inOrder() method:
private void preOrder(Node localRoot)
{
if(localRoot != null)
{
localRoot.displayNode();
preOrder(localRoot.leftChild);
preOrder(localRoot.rightChild);
}
}
For the case of preOrder() method the sequence is1. Visit the node
2. Call itself to traverse the node's left subtree
3. Call itself to traverse the node's right subtree
For the case of preOrder() method the sequence is
1. Call itself to traverse the node's left subtree
2. Call itself to traverse the node's right subtree
3. Visit the node
Java Code for Deleting a Node
Deleting a node is the most complicated common operation required for binary search trees.You start by finding the node you want to delete. Once you've found the node, there are three cases to consider.
1. The node to be deleted is a leaf
2. The node to be deleted has one child
3. The node to be deleted has two children
Here's the code for the inOrder() method:
public boolean delete(int key) // delete node with given key
{ // (assumes non-empty list)
Node current = root;
Node parent = root;
boolean isLeftChild = true;
while(current.iData != key) // search for node
{
parent = current;
if(key < current.iData) // go left?
{
isLeftChild = true;
current = current.leftChild;
}
else // or go right?
{
isLeftChild = false;
current = current.rightChild;
}
if(current == null) // end of the line,
return false; // didn't find it
} // end while
// found node to delete
// if no children, simply delete it
if(current.leftChild==null &&
current.rightChild==null)
{
if(current == root) // if root,
root = null; // tree is empty
else if(isLeftChild)
parent.leftChild = null; // disconnect
else // from parent
parent.rightChild = null;
}
// if no right child, replace with left subtree
else if(current.rightChild==null)
if(current == root)
root = current.leftChild;
else if(isLeftChild)
parent.leftChild = current.leftChild;
else
parent.rightChild = current.leftChild;
// if no left child, replace with right subtree
else if(current.leftChild==null)
if(current == root)
root = current.rightChild;
else if(isLeftChild)
parent.leftChild = current.rightChild;
else
parent.rightChild = current.rightChild;
else // two children, so replace with inorder successor
{
// get successor of node to delete (current)
Node successor = getSuccessor(current);
// connect parent of current to successor instead
if(current == root)
root = successor;
else if(isLeftChild)
parent.leftChild = successor;
else
parent.rightChild = successor;
// connect successor to current's left child
successor.leftChild = current.leftChild;
} // end else two children
// (successor cannot have a left child)
return true; // success
} // end delete()