kdmain.cpp

经典c++程序的实现

#include "book.h"

typedef int ELEM;

#define dkey(X, L) (X)

bool InCircle(int v, int D, int k) {}
void printout(int v) {}


class KDNode {                // Binary tree node class
public:
  ELEM value;                 // The node's value
  KDNode* left;               // Pointer to left child
  KDNode* right;              // Pointer to right child
  BinNode() { }
};

class KD {
private:
  KDNode* root;
public:
  KDNode* KDfindhelp(KDNode*, ELEM, int, int) const;
  KDNode* KDfindmin(KDNode*, int, int, int);
  void KDRegionSearch(KDNode*, ELEM, int, int, int);
};
  
KDNode* KD::KDfindhelp(KDNode* rt, ELEM val, int lev, int K) const {
  // lev: current level (mod K);  K: number of dimensions
  // dkey(val, i) returns the key value of val for dimension i
  if (rt == NULL) return NULL;            // Empty tree
  else if (val == rt->value) return rt;   // Found it
  else if (dkey(val, lev) < dkey(rt->value, lev))
    return KDfindhelp(rt->left, val, (lev+1) % K, K);
  else
    return KDfindhelp(rt->right, val, (lev+1) % K, K);
}

void KDRegionSearch(KDNode* rt, ELEM val, int D, int level, int K) {
  // val: search key; D: search radius;
  // level: current level (mod K);  K: number of dimensions
  // Check if record at rt is in circle
  if (InCircle(key(val), D, key(rt->value)))
    printout(rt->value);  // Do whatever appropriate with node
  if (dkey(rt->value,level) > (dkey(val,level) - D)) // Search left
    KDRegionSearch(rt->left, val, D, (level+1) % K, K);
  if (dkey(rt->value,level) < (dkey(val,level) + D)) // Search right
    KDRegionSearch(rt->right, val, D, (level+1) % K, K);
}

KDNode* KD::KDfindmin(KDNode* rt, int discrim, int level, int K) {
  // discrim: discriminator key used for minimum search;
  // level: current level (mod K);  K: number of levels in key
  KDNode *temp1, *temp2;
  if (rt == NULL) return NULL;
  temp1 = KDfindmin(rt->left, discrim, (level+1)%K, K);
  if (discrim != level) { // Min value could be on either side
    temp2 = KDfindmin(rt->right, discrim, (level+1)%K, K);
    if ((temp1 == NULL) || ((temp2 != NULL) &&
         (dkey(temp2->value,discrim) < dkey(temp1->value,discrim))))
      temp1 = temp2; // Right side has smaller key value
  } // Now, temp1 has the smallest value in children (if any)
  if ((temp1 == NULL) ||
      (dkey(rt->value,discrim) < dkey(temp1->value,discrim)))
    return rt;
  else return temp1;
}

int main(int argc, char** argv) {
  return(0);
}