Monash University > CSSE > CSE1303 > Part A > Lectures > Lecture A13 notes

CSE1303 Computer Science
Semester 2 2003
Part A
Lecture A13 notes: Information Retrieval - Binary Search Trees

In this lecture

• Kruse 9
• Standish 9
• Langsam 5
• Deitel & Deitel 12.7

• It is a Binary Tree with the following properties:
  1. Every node entry contains an unique key.
  2. For every node, the keys in its left subtree are less than its key.
  3. For every node, the keys in its right subtree are greater than its key.

• Insert a list of items into a Binary Search Tree.
• Takes in the average case O(n log(n)) time, and in the worst case O(n²) time.

Code for this lecture

/* tree.h */
#ifndef TREEH
#define TREEH

struct TreeNodeRec
{
 float                  key;
 struct TreeNodeRec*    leftPtr;
 struct TreeNodeRec*    rightPtr;
};

typedef struct TreeNodeRec    TreeNode;

TreeNode* makeTreeNode(float value);
TreeNode* insert(TreeNode* nodePtr, float item);
TreeNode* search(TreeNode* nodePtr, float item);
void printInorder(const TreeNode* nodePtr);
void printPreorder(const TreeNode* nodePtr);
void printPostorder(const TreeNode* nodePtr);
void killTree(TreeNode* rootPtr);

#endif

/* tree.c */
#include <stdio.h>
#include <stdlib.h>
#include "tree.h"

/* Make a new Tree node which contains value. */
TreeNode* makeTreeNode(float value)
{
  TreeNode* newNodePtr = NULL;

  newNodePtr = (TreeNode*)malloc(sizeof(TreeNode));
  if (newNodePtr == NULL)
  {
     fprintf(stderr, "Out of memory\n");
     exit(1);
  }
  else
  {
     newNodePtr->key = value;
     newNodePtr->leftPtr = NULL;
     newNodePtr->rightPtr = NULL;
  }
  return newNodePtr;
}

/*  Insert an item into a Binary Search Tree.  */
TreeNode* insert(TreeNode* nodePtr, float item)
{
 if (nodePtr == NULL)
 {
    nodePtr = makeTreeNode(item);
 }
 else if (item < nodePtr->key)
 {
    nodePtr->leftPtr = insert(nodePtr->leftPtr, item);
 }
 else if (item > nodePtr->key)
 {
    nodePtr->rightPtr = insert(nodePtr->rightPtr, item);
 }
 return nodePtr;
}

/*  This function traverses a Tree inorder and print out each node.  */
void printInorder(const TreeNode* nodePtr)
{
  if (nodePtr != NULL)
  {
     printInorder(nodePtr->leftPtr);
     printf("%f\n", nodePtr->key);
     printInorder(nodePtr->rightPtr);
  }
}

/*  Search for an item in a Binary Search Tree.
 *  If found return a pointer to the node, else
 *  return NULL.  */

TreeNode* search(TreeNode* nodePtr, float item)
{
 if (nodePtr != NULL)
 {
   if (item < nodePtr->key)
   {
      nodePtr = search(nodePtr->leftPtr, item);
   }
   else if (item > nodePtr->key)
   {
      nodePtr = search(nodePtr->rightPtr, item);
   }
 }
 return nodePtr;
}

#include <stdio.h>
#include "tree.h"

int main()
{
 float item;
 TreeNode* rootPtr = NULL;

 printf("Enter items\n");
 while (scanf("%f", &item) != EOF)
 {
    rootPtr = insert(rootPtr, item);
 }

 printInorder(rootPtr);
 killTree(rootPtr);
}

[ Top | Home ]
Last Updated: Thursday 26 June 2003 11:05:02