bintree.cpp

ALGAE是一个快速创建算法演示的框架。目前支持的算法实现语言包括java和c

#include <time.h>
#include <algae/config.h>
#include <iostream>
#include <cstdlib>
#include <sstream>

#include <string>

#include <algae/algae.h>

#include "bintree.h"

using namespace std;


template class Tree_Node<int>;
template class Binary_Search_Tree<int>;



void promptForInput(const char* prompt, int& input)
{
  string reply;
  bool OK = false;
  while (!OK)
    {
     algae->promptForInput (prompt, reply);
#ifdef _MSC_VER
	 char* replystr = (char*)reply.c_str();
#else
	 const char* replystr = (char*)reply.c_str();
#endif
     istringstream in (replystr);
     OK = !!(in >> input);
    }
}

unsigned rnd (unsigned limit)
{
  return (rand() >> 2) % limit;
}


bool used[100] = {false};

int markUsed (int i)
{
  if ((i >= 0) && (i < 100))
    used[i] = true;
  return i;
}


int markUnused (int i)
{
  if ((i >= 0) && (i < 100))
    used[i] = false;
  return i;
}


int getUniqueRandomValue()
{
  int r = rnd(100);
  while (used[r])
    r = rnd(100);
  markUsed(r);
  return r;
}

Binary_Search_Tree<int>* tree;


void bstInsert()
{
  int v;
  promptForInput("Value to insert", v);
  tree->Insert (markUsed(v));
}

void bstSeqInsert()
{
  int v, d, N;
  promptForInput("Starting value", v);
  promptForInput("Increment", d);
  promptForInput("Number of values", N);
  for (int i1 = 0; i1 < N; i1++)
    tree->Insert(markUsed(v+i1*d));
}

void bstRandomInsert()
{
  int N;
  promptForInput("Number of values", N);
  for (int i1 = 0; i1 < N; i1++)
    tree->Insert(markUsed(getUniqueRandomValue()));
}


void bstDelete()
{
  int v;
  promptForInput("Value to remove", v);
  tree->Remove (markUnused(v));
  Visible::unHighlightAll();
}


void bstFind()
{
  int v;
  cout << "Value to find" << endl;
  cin >> v;
  cout << "Entered: " << v << endl;
  //	  promptForInput("Value to find", v);
  tree->Find (v);
  Visible::unHighlightAll();
}



void bstPreTraverse()
{
  tree->preOrder();
  cout << endl;
}

void bstInTraverse()
{
  tree->inOrder();
  cout << endl;
}


void bstPostTraverse()
{
  tree->postOrder();
  cout << endl;
}

void bstLevelTraverse()
{
  tree->levelOrder();
  cout << endl;
}

void bstClear()
{
  tree->Make_Empty();
}


AlgAE* algae;


int main (int nargs, char** args)
{
  time_t dummy;
  srand (time(&dummy));
  
  algae = new AlgAE(nargs, args);
  
  algae->menuItem("Insert", bstInsert);
  algae->menuItem("Sequential Inserts", bstSeqInsert);
  algae->menuItem("Random Inserts", bstRandomInsert);
  algae->menuItem("Delete", bstDelete);
  algae->menuItem("Find", bstFind);
  algae->menuItem("Pre-Order Traverse", bstPreTraverse);
  algae->menuItem("In-Order Traverse", bstInTraverse);
  algae->menuItem("Post-Order Traverse", bstPostTraverse);
  algae->menuItem("Level-Order Traverse", bstLevelTraverse);
  algae->menuItem("Clear", bstClear);

  tree = new Binary_Search_Tree<int>();
  tree->show();
  
  algae->run ("Binary Search Tree",
	      "Binary search code adapted for AlgAE animation by\n"
	      "  Steven J. Zeil, Old Dominion University"
	      );
  
  delete algae;
  
  return 0;
}