john7rv

データをツリー状に構成して素早くデータを見つけるアルゴリズムです
再帰が使われます

main.cpp

#include <iostream>
#include <bits/stdc++.h>
#include <cmath>

using namespace std;

struct BNode
{
  int data;
  BNode *left;
  BNode *right;
};
typedef struct BNode Node;

Node *makeNode(int data)
{
  Node *n = new Node;
  n->data = data;
  n->left = NULL;
  n->right = NULL;
  return n;
}

Node* insertData(Node *n, int data)
{
  if (!n)
  {
    return makeNode(data);
  }
  else
  {
    if (data <= n->data)
    {
      n->left = insertData(n->left, data);
    }
    else
    {
      n->right = insertData(n->right, data);
    }
  }
  return n;
}

Node* firstCreateRoot()
{
  Node *root = makeNode(0);
  return root;
}

void printAll(Node *n)
{
  if (n)
  {
    printAll(n->left);
    cout << "data is " << n->data <<endl;
    printAll(n->right);
  }
}

int searchMin(Node *n)
{
  if (n)
  {
    while(n->left)
    {
      n = n->left;
    }
    return n->data;
  }
  else
  {
    return 0;
  }
}

int searchMax(Node *n)
{
  if (n)
  {
    while(n->right)
    {
      n = n->right;
    }
    return n->data;
  }
  else
  {
    return 0;
  }
}

void searchNearRec(Node *n, int num, int &currentMinSaNum, int &nearNum)
{
  if (!n) return;
  if (n->data == num)
  {
    nearNum = num;
    return;
  }

  int sa = abs(n->data - num);

  if (currentMinSaNum > sa)
  {
    currentMinSaNum = sa;
    nearNum = n->data;
  }

  if (num < n->data)
  {
    searchNearRec(n->left, num, currentMinSaNum, nearNum);
  }
  else
  {
    searchNearRec(n->right, num, currentMinSaNum, nearNum);
  }

}

int searchNear(Node *n, int num)
{
  int currentMinSaNum = INT_MAX;
  int nearNum = -1;
  searchNearRec(n, num, currentMinSaNum, nearNum);
  return nearNum;
}

int main()
{
  Node *root = firstCreateRoot();
  insertData(root, 1);
  insertData(root, 2);
  insertData(root, 3);
  insertData(root, -1);
  insertData(root, -2);
  insertData(root, -3);
  insertData(root, 10);
  insertData(root, -2);
  insertData(root, 20);
  insertData(root, -25);
  printAll(root);
  cout << "min is " << searchMin(root) << endl;
  cout << "max is " << searchMax(root) << endl;
  cout << "near is " << searchNear(root,-28) <<endl;
};