Блог

Главная - Вопросы по программированию - Получение минимального значения из двоичного дерева поиска

Получение минимального значения из двоичного дерева поиска

#c #binary-search-tree

#c #binary-search-tree

Вопрос:

Я пытаюсь найти минимальное значение из двоичного дерева поиска,

 struct Node {
    int value;     
    Node *smaller; 
    Node *greater; 

    explicit Node(int value = 0, Node *smaller = nullptr, Node *greater = nullptr)
            : value(value)
            , smaller(smaller)
            , greater(greater)
    {
    }
};


struct BinarySearchTree {
    Node *root; // koren stromu

    explicit BinarySearchTree(Node *root = nullptr)
            : root(root)
    {
    }
};

class ValueNotExistsException : public std::exception {
};

вот как мой по британскому летнему времени определяется сейчас мне нужно найти минимальное значение:

 int min(const BinarySearchTree *tree) {
    /* code goes here */ 
}

Мне нужно использовать точную функцию. Я пробовал это с реализацией узла, подобной этой:

 struct BinarySearchTree* current = tree;  
  
while (current->smaller!= NULL)  
{  
    current = current->smaller;  
}  
return(current->value);

Работает current->value не так, как ожидалось. Моя проблема в том, что когда я объявляю свой текущий, он говорит:

Cannot initialize a variable of type struct BinarySearchTree * with an lvalue of type const BinarySearchTree *

Комментарии:

1. Что означает «это не работает четко»?

2. BinarySearchTree не имеет имени элемента smaller . Теперь, какой тип имеет имя члена smaller ?

3. «это не работает четко» — это не описание проблемы. При публикации вопроса опишите конкретную проблему, т.Е. Что именно происходит и почему это неправильно, и укажите все ошибки полностью.

4. хорошо, я отредактировал его, извините

5. Посмотрите на дерево const BinarySearchTree *tree , посмотрите на текущее BinarySearchTree *current . Вы видите разницу?

Ответ №1:

  • Вы должны вернуть value вместо smaller .
  • Вы должны извлечь root из BinarySearchTree .
  • Неверно указано место * in struct *BinarySearchTree current = tree; .
 int min(const BinarySearchTree *tree) {

    struct Node* current = tree->root;

    while (current->smaller!= NULL)
    {
        current = current->smaller;
    }
    return(current->value);

}

Комментарии:

1. struct *BinarySearchTree для меня это не похоже на C .

2. спасибо, это кажется хорошим, также как мне реализовать / выбросить это исключение ValueNotExistsException, если это значение не существует, вот так? возврат (текущий-> значение ? current->value: выбросить ValueNotExistsException() );

3. @MICHAEL — Какое значение вы имеете в виду? А по британскому летнему времени есть хотя бы один узел, так что всегда будет минимум.

4. я имею в виду, если дерево пустое

5. То, что вы должны были бы проверять, — это то, что переданное tree значение равно nullptr или tree->root равно nullptr. Он даже не должен попадать в while цикл или присваивать что-либо current , если какое-либо из этих значений есть nullptr .

Метки: