Двоичные поисковые деревья

Question

У меня есть вопрос относительно реализации дерева двоичного поиска в C ++. Вот вопрос ниже

Реализация простого (не шаблонного) BST, который хранит целые числа. Укажите следующие операции: вставка, удаление, обход inOrder, обход preOrder, обход postOrder.

Используйте рекурсивные процедуры для работы с деревом.

Обработка узла просто включает распечатку содержимого узла, которое в данном случае является целым числом, хранящимся в узле.

Данные должны поступать из тестовых файлов. Основная программа должна открыть файл данных и вставить в дерево и продемонстрировать другие операции с деревом.

Смысл этого упражнения - продемонстрировать, что вы понимаете BST. Нет необходимости переборщить с ним и начать операции, о которых не просили.

Я только что создал файл заголовка. Может ли кто-нибудь взглянуть и посоветовать, если я иду в правильном направлении?

using namespace std;
#ifndef BSTNODE_H
#define BSTNODE_H
class BSTNode
{
    private:
    //Defines the 'node' structure
    struct tree_node 
    {
     tree_node *left;   // left subtree has smaller elements
     tree_node *right;  // right subtree has larger elements
     int m_data;
    };
    //root * r;
    public:
        //The Constructor
        BSTNode();
        //The Destructor
       ~BSTNode();
       //Inserts a value into a BST, public function
        void insert(const m_data & d);
        //Removes a value from a BST, public function
        void remove(const m_data & d);
        //isEmpty function, public function
        bool isEmpty();
        BSTNode getData();
        void inOrder(const m_data & d);
        void preOrder(const m_data & d);
        void postOrder(const m_data & d);
};
#endif

Далее мне нужно создать файл BSTNode.cpp. Благодарим Вас за ответ по электронной почте jediknight80n@hotmail.com. Заранее благодарим.

Answer 1

   //Inserts a value into a BST, public function
    void insert(const m_data & d);
    //Removes a value from a BST, public function
    void remove(const m_data & d);
    //isEmpty function, public function
    bool isEmpty();
    BSTNode getData();
    void inOrder(const m_data & d);
    void preOrder(const m_data & d);
    void postOrder(const m_data & d);

m_data является членом, а не типом. Вы должны использовать int здесь. Кроме того, поскольку ваш узел - tree_node, внешний класс, вероятно, должен представлять дерево в целом (т. Е. BSTree, а не BSTNode).

Также 'использование пространства имен std;' зло в заголовках, так как оно навязывает его всему, что включает в себя заголовок без возможности отказаться. Если вы собираетесь использовать его, я бы порекомендовал сохранить его в файлах .cpp.

Answer 2

Вы, кажется, забыли typedef тип m_data, который вы используете в различных методах, и я не понимаю, почему вам нужна отдельная структура tree_node (а не использование самого класса? ) ни почему getData должен возвращать BSTNode, а не int.

Answer 3

Что-то тривиальное:

tree_node *left;   // left subtree has smaller elements

В общем, левое поддерево также содержит равные элементы.

Answer 4

Поскольку вы используете C ++, вы можете рассмотреть возможность использования некоторых стандартных библиотек вместо того, чтобы пытаться реализовать все это самостоятельно? Библиотеки STL поставляются с красно-черным деревом, которое может лучше подойти вашему приложению. Бинарные деревья могут становиться односторонними или вырожденными в список ссылок.

PS: Конечно, это предполагает, что вы не выполняете домашнее задание.

Answer 5

• использование левого и правого указателей типа struct в вашем примере ограничит гибкость - предположим, что я беру ваш BST и иду к левому потомку корня, а затем хочу вызвать операции на этом новом поддереве. Я не могу, так как указатели имеют тип struct. Я бы предпочел использовать оба указателя типа BSTNode.

  BSTNode *left;

  BSTNode *right;

  Это также решит вашу проблему с корнем (явный указатель на корень не требуется), поскольку указатель, который вы используете для ссылки на свой объект в main, в любом случае будет указывать на root.

• Функции обхода не должны требовать каких-либо аргументов, когда они будут по существу проходить по всему дереву и печатать все элементы данных вместе. Элемент данных может быть передан другой функции-члену поиска для поиска его позиции, как уже было указано TrueStar.

• Я также предлагаю несколько закрытых функций-членов, чтобы уменьшить сложность ваших открытых функций-членов (DeleteNodeCaseB(int data) будет вызывать DeleteNodeCaseA(int data) изнутри и снова) -

  BSTNode * setleft(int data);

  BSTNode * setright(int data);

  void DeleteNodeCaseA(int data) / * ни одного, ни левого и правого ребенка не существует * /

  void DeleteNodeCaseB(int data) / * имеет левого и правого ребенка * /

Answer 6

Я бы тоже добавил метод поиска.

bool search(int whatIlookfor);

или даже лучше

tree_node* search(int whatIlookfor);

Кроме того, храните tree_node *root в безопасном месте.

Answer 7

Другая проблема заключается в том, что указанный класс объявляет вложенный тип и методы, но не содержит данных-членов.

---

Вы можете объявить функцию обхода, используя итераторы: например, метод предварительного заказа возвращает целое число, которое можно разыменовать узлу или увеличить, чтобы указать на следующий узел в последовательности предварительного заказа.

Или вы можете объявить функцию обхода с помощью обратных вызовов: т.е. вызывающий объект передает экземпляр обратного вызова методу предварительного заказа, метод предварительного заказа проходит по дереву и вызывает метод обратного вызова для каждого узла: метод обратного вызова будет принимать узел (или более конкретно, данные узла) в качестве параметра и может возвращать логическое значение, которое позволило бы обратному вызову указать, что он хочет прервать обход.

Answer 8

Пара вещей - как уже отмечали другие, вам придется использовать

void insert(const int & d);
//Removes a value from a BST, public function
void remove(const int & d);
//isEmpty function, public function
bool isEmpty();
BSTNode getData();
void inOrder(const int & d);
void preOrder(const int & d);
void postOrder(const int & d);

Другое дело, что вы закомментировали свой корневой узел. Хотя вы определили это неправильно, вам придется включить корневой класс в класс. Правильное определение будет

tree_node *root;

Также, как было указано ранее, удалите

с использованием пространства имен std;

из заголовочного файла и поместите его в файл реализации.

Это все, что я сейчас вижу.

Answer 9

Это классический вопрос о BST - любая хорошая книга по структурам данных даст вам весь код. Следующая страница содержит примеры кода для C ++ http://cslibrary.stanford.edu/110/BinaryTrees.html.

Функции обхода не должны быть частью самого класса BST, в действительности BSTNode должен предоставлять указатели левого / правого узла - и вызывающее приложение должно вызывать его особым образом. Или используйте функцию обратного вызова и предоставьте код обхода в вашем классе, таким образом, это будет намного чище.