Бинарный поиск без предварительной сортировки

// TREENODE.H:      Определение класса TreeNode
#ifndef TREENODE_H
#define TREENODE_H
 
template<class NODETYPE>
class TreeNode
{
    friend class Tree<NODETYPE>;
 
public:
    TreeNode(const NODETYPE &);     // конструктор
    NODETYPE getData() const;       // возвращение данных
 
private:
    TreeNode * leftPtr;             // указатель на левое поддерево
    NODETYPE data;
    TreeNode *rightPtr;             // указатель на правое поддерево
};
 
// Конструктор
template<class NODETYPE>
TreeNode<NODETYPE>::TreeNode(const NODETYPE &d)
{
    data = d;
    leftPtr = rightPtr = 0;
}
 
// Возвращение копии значений данных
template<class NODETYPE>
NODETYPE TreeNode<NODETYPE>::getData() const
{
    return data;
}
 
#endif
 
// TREE.H:          Определение шаблона класса Tree
#ifndef TREE_H
#define TREE_H
 
#include <iostream.h>
#include <assert.h>
#include "treenode.h"
 
template<class NODETYPE>
class Tree
{
public:
    Tree();
    ~Tree();
    void insertNode(const NODETYPE &);
    void preOrderTraversal() const;
    void inOrderTraversal() const;
    void postOrderTraversal() const;
 
private:
    TreeNode<NODETYPE> *rootPtr;
 
    // функции утилиты
    void insertNodeHelper(TreeNode<NODETYPE> **, const NODETYPE &);
    void preOrderHelper(TreeNode<NODETYPE> *) const;
    void inOrderHelper(TreeNode<NODETYPE> *) const;
    void postOrderHelper(TreeNode<NODETYPE> *) const;
    void deconstructorHelper(TreeNode<NODETYPE> *) const;
};
 
template<class NODETYPE>
Tree<NODETYPE>::Tree()
{
    rootPtr = 0;
}
 
template<class NODETYPE>
Tree<NODETYPE>::~Tree()
{
    deconstructorHelper(rootPtr);
}
 
template<class NODETYPE>
void Tree<NODETYPE>::insertNode(const NODETYPE &value)
{
    insertNodeHelper(&rootPtr, value);
}
 
// Эта функция принимает указатель на указатель, так что указатель может быть
// модифицирован
template<class NODETYPE>
void Tree<NODETYPE>::insertNodeHelper(TreeNode<NODETYPE> **ptr,
    const NODETYPE &value)
{
    if (*ptr == 0)                  // пустое дерево
    {
        *ptr = new TreeNode<NODETYPE>(value);
        assert(*ptr != 0);
    }
    else                            // дерево не пустое
    {
        if (value < (*ptr)->data)
            insertNodeHelper(&((*ptr)->leftPtr), value);
        else
            insertNodeHelper(&((*ptr)->rightPtr), value);
    }
}
 
template<class NODETYPE>
void Tree<NODETYPE>::preOrderTraversal() const
{
    preOrderHelper(rootPtr);
    cout << endl;
}
 
template<class NODETYPE>
void Tree<NODETYPE>::preOrderHelper(TreeNode<NODETYPE> *ptr) const
{
    if (ptr != 0)
    {
        cout << ptr->data << ' ';
        preOrderHelper(ptr->leftPtr);
        preOrderHelper(ptr->rightPtr);
    }
}
 
template<class NODETYPE>
void Tree<NODETYPE>::inOrderTraversal() const
{
    inOrderHelper(rootPtr);
    cout << endl;
}
 
template<class NODETYPE>
void Tree<NODETYPE>::inOrderHelper(TreeNode<NODETYPE> *ptr) const
{
    if (ptr != 0)
    {
        inOrderHelper(ptr->leftPtr);
        cout << ptr->data << ' ';
        inOrderHelper(ptr->rightPtr);
    }
}
 
template<class NODETYPE>
void Tree<NODETYPE>::postOrderTraversal() const
{
    postOrderHelper(rootPtr);
    cout << endl;
}
 
template<class NODETYPE>
void Tree<NODETYPE>::postOrderHelper(TreeNode<NODETYPE> *ptr) const
{
    if (ptr != 0)
    {
        postOrderHelper(ptr->leftPtr);
        postOrderHelper(ptr->rightPtr);
        cout << ptr->data << ' ';
    }
}
 
template<class NODETYPE>
void Tree<NODETYPE>::deconstructorHelper(TreeNode<NODETYPE> *ptr) const
{
    if (ptr != 0)
    {
        deconstructorHelper(ptr->leftPtr);
        deconstructorHelper(ptr->rightPtr);
        delete ptr;
    }
}
 
#endif
 
// Упражнение 15.16
//
 
#include <iostream.h>
#include <iomanip.h>
#include "tree.h"
 
int main()
{
    Tree<int> intTree;
    int intVal;
 
    cout << endl << "Введите 10 целых чисел: " << endl;
 
    for (int i = 0; i < 10; i++)
    {
        cin >> intVal;
        intTree.insertNode(intVal);
    }
 
    cout << endl << "Обход в ширину" << endl;
    intTree.preOrderTraversal();
    cout << "Последовательный обход" << endl;
    intTree.inOrderTraversal();
    cout << "Обратный обход" << endl;
    intTree.postOrderTraversal();
 
    Tree<float> floatTree;
    float floatVal;
 
    cout << endl << "Введите 10 чисел с плавающей точкой:" << endl
        << setiosflags(ios::fixed | ios::showpoint) << setprecision(1);
 
    for (int i = 0; i < 10; i++)
    {
        cin >> floatVal;
        floatTree.insertNode(floatVal);
    }
 
    cout << endl << "Обход в ширину" << endl;
    floatTree.preOrderTraversal();
    cout << "Последовательный обход" << endl;
    floatTree.inOrderTraversal();
    cout << "Обратный обход" << endl;
    floatTree.postOrderTraversal();
 
    return 0;
}