2

Нужно проверить есть ли элемент Х в бинарном дереве. Моя функция Find работает рандомно, то находит то не находит (хотя он есть). В чем ошибка?

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cstdio>
using namespace  std;

struct BinaryTree {
  int Data; 
  BinaryTree * Left; 
  BinaryTree * Right; 
};

void Make_BinaryTree(BinaryTree** Node, int n){
  BinaryTree** ptr; 
  srand(time(NULL)*1000);
  while (n > 0) {
    ptr = Node;
    while (*ptr != NULL) {
      if ((double) rand()/RAND_MAX < 0.5)
        ptr = &((*ptr)->Left);
      else ptr = &((*ptr)->Right);
    }
    (*ptr) = new BinaryTree();
    cout << "Введите значение ";
    cin >> (*ptr)->Data;
    n--;
  } 
}
//прямой обход
void PreOrder_BinaryTree(BinaryTree* Node)  {
  if (Node != NULL) {
    printf ("%3ld",Node->Data);PreOrder_BinaryTree(Node->Left);
    PreOrder_BinaryTree(Node->Right);
  } 
}

void Find(BinaryTree* Node, int x) {
  if (Node==NULL) {
    cout<<x<<" - не найден"<<endl;
    return;
  }
  else if (Node->Data==x) {
    cout<<x<<" - найден"<<endl;
    return;
  }
  else if (Node->Data > x)
    Find(Node->Right, x);
  else
    Find(Node->Left, x);
}

void Delete_BinaryTree(BinaryTree* Node) {
  if (Node != NULL) {
    Delete_BinaryTree(Node->Left);
    Delete_BinaryTree(Node->Right);
    delete(Node);
  } 
}

int main() {
  BinaryTree *BTree=NULL;
  Make_BinaryTree(&BTree, 5);
  PreOrder_BinaryTree(BTree); //вывод элементов
  cout<<endl;
  Find(BTree, 5); //вызов поиска
  Delete_BinaryTree(BTree);
return 0;
}

4
  • Правила хорошего тона предполагают, что вы предоставите минимально-воспроизводимый пример, а не случайное заполнение дерева. У вас может что-то не работать, а у другого человек будет работать, если заполнение случайное. Кто знает, может вы неверно заполняете, не по правилам дерева поиска? Ведь не каждое бинарное дерево является деревом поиска.
    – Zealint
    16 дек 2019 в 5:38
  • Тест 1) 7, 5, 10, 3, 8 //5 - найден Тест 2) 7, 5, 10, 3, 8 //5 - не найден Тест 3) 15, 8, 20, 5, 10 //5- не найден Тест 4) 15, 20, 8, 5, 10 //5- найден Тест 5) 15, 8, 20, 5, 10 //5- найден Тест 6) 5, 2, 7, 1, 8 //5-найден Тест 7) 5, 2, 7, 1, 8 //5-найден
    – Илья
    16 дек 2019 в 5:48
  • потому что ваш код не может выполнить никакого осмысленного действия_сплошное UB. Поищите по интернету примеры кодов с бинарным деревом и изучайте что к чему. 16 дек 2019 в 5:53
  • 2
    @Илья , этот тест ничего не говорит, потому что у вас функция заполнения дерева пихает числа СЛУЧАЙНО в разные места дерева. Вы можете НЕ получить дерево поиска, а потому и поиск не будет работать. А надо чтобы получилось дерево поиска, когда левые элементы всегда меньше правых для каждого узла. Каким образом вы это обеспечиваете?
    – Zealint
    16 дек 2019 в 5:55

1 ответ 1

3

Проблема в функции Make_BinaryTree. Вы сначала определяете ветку, куда будет помещено значение, а потом его вводите. Нужно сначала ввести, а потом на основе введеного значения определить куда его поместить. Также нужно учитывать возможность ввода дубликатов. Функция Find делает предположение, что все значения в дереве отсортированы, чего Make_BinaryTree не обещает.

1
  • Взял код из методички. Не разобрался. Думал что все бинарные деревья уже отсортированы.
    – Илья
    16 дек 2019 в 6:00

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.