btree.c

压缩包里面的都是精致的基本C语言小程序

#include <stdio.h>
#include "mystdlib.h"
#include "commonInter.h"
#include "error.h"
#include "dot.h"
#include "queue.h"
#include "btree.h"

struct btree
{
  poly data;
  btree left;
  btree right;
};

static btree newBtree2 (poly data, btree left, btree right);

btree newBtree ()
{
  return NULL;
}

static btree newBtree2 (poly data, btree left, btree right)
{
  btree t = checkedMalloc (sizeof (*t));
  t->data = data;
  t->left = left;
  t->right = right;
  
  return t;
}

int btreeIsEmpty (btree t)
{
  if (t)
    return 1;
  else 
    return 0;
}

btree btreeSearch (btree t, poly data)
{
  if (!t)
    return NULL;

  int b = getVft ((t->data))->equals (t->data, data);
  
  if (b)
    return t;
  
  btree temp = btreeSearch (t->left, data);
  return (temp) ? (temp) : (btreeSearch (t->right, data));
}

btree btreeInsert (btree t, poly parent, poly child, char pos)
{
  if (!child)
    exception ("invalid child node\n");

  if (pos != 'l' && pos != 'r')
    exception ("invalid position, should be 'l' or 'r'\n");

  if (!t)
  {
    if (!parent)
    {
      return newBtree2 (child, NULL, NULL);
    }
    else
      exception ("parent should not be NULL");
  }
  else 
  {
    if (!parent)
      exception ("tree not empty, should not insert root\n");
    else
    {
      btree temp = btreeSearch (t, parent);
      if (!temp)
        exception ("node not found\n");
      else
      {
        if (pos=='l' && temp->left)
          exception ("invalid insert position 'l'\n");
       
        if (pos=='r' && temp->right)
          exception ("invalid insert position 'r'\n");

        if (pos=='l')
          temp->left = newBtree2 (child, temp->left, NULL);
        else
          temp->right = newBtree2 (child, temp->right, NULL);
      }
    }
  }
  return t;
}

void btreePreOrder (btree t, tyVisit visit)
{
  if (t)
  {
    visit (t->data);
    btreePreOrder (t->left, visit);
    btreePreOrder (t->right, visit);
  }
}

void btreeInOrder (btree t, tyVisit visit)
{
  if (t)
  {
    btreePreOrder (t->left, visit);
    visit (t->data);
    btreePreOrder (t->right, visit);
  }
}

void btreeLevelOrder (btree t, tyVisit visit)
{
  if (!t)
    return;

  queue q = newQueue ();
  
  enQueue (q, t);

  while (!(queueIsEmpty (q)))
  {
    btree temp = deQueue (q);
    strOutput2 ("now visiting:\n");
    visit (temp->data);

    if (temp->left)
    {
      enQueue (q, temp->left);
    }

    if (temp->right)
    {
      enQueue (q, temp->right);
    }
  }
}


void btreeToDot (char *fname, btree t)
{
  if (!t)
    return;

  dot d = newDot ();
  queue q = newQueue ();
  
  enQueue (q, t);

  while (!(queueIsEmpty (q)))
  {
    btree temp = deQueue (q);
    if (temp->left)
    {
      enQueue (q, temp->left);
      str strParent = getVft (temp->data)->toString (temp->data);
      str strChild = getVft (temp->left->data)->toString (temp->left->data);
      str strPos = newStr ("l");
      dotInsert (strParent, strChild, strPos, d);
    }

    if (temp->right)
    {
      enQueue (q, temp->right);
      str strParent = getVft (temp->data)->toString (temp->data);
      str strChild = getVft (temp->right->data)->toString (temp->right->data);
      str strPos = newStr ("r");
      dotInsert (strParent, strChild, strPos, d);
    }
  }
  
  dotToJpg (d, fname);
}