source: abuse/tags/pd/imlib/tree.c @ 49

Last change on this file since 49 was 49, checked in by Sam Hocevar, 11 years ago
  • Imported original public domain release, for future reference.
  • Property svn:keywords set to Id
File size: 1.7 KB
Line 
1#include <stdio.h>
2#include <stdlib.h>
3
4class btnode
5{
6protected :
7  btnode *Left, *Right;
8public :
9          btnode *left()                   { return Left; }
10          btnode *right()                  { return Right; }
11          void    set_right(btnode *right) { Right=right; }
12          void    set_left (btnode *left)  { Left=left;   }
13  virtual int     compare  (btnode *node) = 0;
14  virtual char   *name     ()             = 0;
15} ;
16
17class btree
18{
19  void reprint(btnode *n);
20protected :
21  btnode *root;
22public :
23               btree() { root=NULL; }
24  virtual void insert(btnode *node);
25  virtual void remove(btnode *node);
26  void         print() { reprint(root); }
27} ;
28
29void btree::insert(btnode *node)
30{ btnode *parent,*finder;
31  int from_left;
32  node->set_right(NULL); node->set_left(NULL);
33  if (root)
34  { finder=root;
35    while (finder)
36    { parent=finder;
37      if (finder->compare(node)>0)
38      { from_left=1; finder=finder->left(); }
39      else
40      { from_left=0; finder=finder->right(); }
41    }
42    if (from_left)
43      parent->set_left(node);
44    else
45      parent->set_right(node);
46  } else root=node;
47}
48
49void btree::remove(btnode *node)
50{
51}
52
53void btree::reprint(btnode *n)
54{
55  if (n)
56  { reprint(n->left());
57    printf("%s\n",n->name());
58    reprint(n->right());
59  }
60}
61
62class btnumber : public btnode
63{
64  int num;
65public :
66  btnumber(int x) { num=x; }
67  virtual int     compare  (btnode *node)
68    { if (num<((btnumber *)node)->num) return -1;
69      else return (num> ((btnumber *)node)->num); }
70  virtual char   *name     ()
71    { static char st[20]; sprintf(st,"%d",num); return st;}
72} ;
73
74main()
75{
76  btree bt;
77  for (int i=0;i<20;i++)
78    bt.insert((btnode *) new btnumber(random(500)));
79  bt.print();
Note: See TracBrowser for help on using the repository browser.