Binary Search Trees
Definitions, building, traversing
Definitions
¢ Tree:
A tree is a structure in which a parent can have any number of children
¢ Binary Tree
A a structure in which a parent can have at most two children
¢ Binary Search Tree
Binary tree such that for every parent node, a child to the right will have a larger value, while a child to the left will have a smaller value.
¢ Root node
The top node in the tree; the node whose value is 52 (see figure below).
¢ Parent node
A node which points to one or two nodes.
¢ Child node
The node being pointed to from a parent; every node in the tree is a child to another node, except for the root node.
¢ Leaf
A node which has no children. It has two NULL pointers.
¢ Level
The distance from the root, calculated by counting the shortest distance from the root to that node.
Examples: 29 is the value stored in a node at level 1, 62 is a value stored in a node at level 2, 17 is the value of a node stored at level 3, etc.
¢ Edge
An edge joins two nodes. In the above diagram each arrow represents an edge.
¢ Subtree
A subtree is the entire left branch or right branch of a node. For example, the left subtree of the node containing 52 has 4 nodes.
The right subtree of node containing 75 has only 1 node.
¢ Height
Longest distance, in terms of nodes, from root to a leaf
¢ Width
Longest distance, not necessarily including the root, from one node to another
Building a BST
struct
treeNode
{
int
data;
treeNode
*left, *right;
// struct constructor declaration
};
typedef
treeNode*
treePtr;
void insert (treePtr &temp, int id, int inv);
void mainMenu (treePtr &);
int main()
{
treePtr root;
root = NULL;
mainMenu (root);
return 0;
}
void mainMenu (treePtr &root)
{
char choice;
//code to read data from file: id number and inventory amount
//code to prompt for action - build, etc. Then calls insert if action is to build
}
void insert (treePtr &temp, int id, int inv)
{
if (NULL == temp)
temp = new treeNode (id, inv, NULL, NULL);
else
if (id < temp->id)
insert (temp->left, id, inv);
else
insert (temp->right, id, inv);
}
VLR
void preorder (treePtr temp)
{
if (temp != NULL)
{
cout << temp->data << endl;
preorder (temp->left);
preorder (temp->right);
}
}
LVR
void inorder (treePtr temp)
{
if (temp != NULL)
{
inorder (temp->left);
cout << temp->data << endl;
inorder (temp->right);
}
}
LRV
void postorder (treePtr temp)
{
if (temp != NULL)
{
postorder (temp->left);
postorder (temp->right);
cout << temp->data << endl;
}
}
private int countLeaves (TreeNode root)
{
if (root == null)
return 0;
else if ((root.getRight() == null) && (root.getLeft() == null))
return 1;
else
return countLeaves(root.getLeft()) + countLeaves (root.getRight());
}
private int height (TreeNode root)
{
if (root == null)
return 0;
else
return (max(1 + height(root.getLeft()), 1 + height(root.getRight())));
}
private int width (TreeNode root)
{
int temp;
if (root == null)
return 0;
temp = height(root.getLeft()) + 1 + height(root.getRight());
temp = max (temp, width(root.getLeft()));
return max (temp, width(root.getRight()));
}
T
private int countNodes (TreeNode root)
{
if (root == null)
return 0;
else
return countNodes(root.getLeft()) + 1 + countNodes(root.getRight());
}
public void clearTree()
{
myRoot = null;
}
private TreeNode insert (Comparable next, TreeNode root)
// pre : root points to a binary search tree
// post: next added to tree so as to preserve binary search tree
{
if (root == null)
root = new TreeNode (next, null, null);
else if(next.compareTo(root.getValue()) <= 0 )
root.setLeft(insert(next, root.getLeft()));
else
root.setRight(insert(next, root.getRight()));
return root;
}
public Object findMin()
// post: returns the minimum value in the tree (null if tree is empty)
{
if (myRoot == null)
return null;
else
return findMin(myRoot);
}
private Object findMin(TreeNode root)
// pre : root points to a nonempty binary search tree
// post: returns the minimum value stored in the tree
{
if (root.getLeft() == null)
return root.getValue();
else
return findMin(root.getLeft());
}