Работа с бинарным деревом

198
21 марта 2018, 05:31
    #include <iostream>
#include <cstdlib>
#include <ctime>
#include <queue>
#include <string>
#include <stdio.h>
using namespace std;
typedef int T;
queue <int> myqueue;
typedef struct Node {
  int data;
  Node *LeftBranch;
  Node *RightBranch;
  Node *Parent;
} Node;
Node* getFreeNode(T value, Node *Parent);
void addToTree(Node **head, int value);
void printTree(Node *Root, const char *dir, int level);
int min(Node *Root);
int find(Node *Root);
Node *deleteNode(Node *Root, int key);
void delete2(Node *Root);
bool isPrime(int n);
int main(int argc, char const *argv[]) {
  Node *Root = NULL;
  int* arr = new int[14];
  srand(time(NULL));
  for (int i = 0; i < 14; i++) {
    arr[i] = rand() % 198 - 99;
  }
  for (int i = 0; arr[i]; i++) {
    addToTree(&Root, arr[i]);
  }
    printTree(Root, "Root", 0);
    cout << "Min: " <<min(Root);
    cout << endl;

    find(Root);
    cout << endl;
    delete2(Root);
    printTree(Root, "Root", 0);
    cout << "finish";
  return 0;
}

Node* getFreeNode(T value, Node *Parent) {
  Node *tmp = (Node*) malloc(sizeof(Node));
  tmp->LeftBranch = tmp->RightBranch = NULL;
  tmp->data = value;
  tmp->Parent = Parent;
  return tmp;
}
void addToTree(Node **head, int value) {
  Node *tmp = NULL;
  Node *ins = NULL;
  if (*head == NULL) {
    *head = getFreeNode(value, NULL);
    return;
  }
  tmp = *head;
  while (tmp) {
    if (value > tmp->data) {
      if (tmp->RightBranch) {
        tmp = tmp->RightBranch;
        continue;
      }
      else {
        tmp->RightBranch = getFreeNode(value, tmp);
        return;
      }
    }
    else if ( value < tmp->data) {
        if (tmp->LeftBranch) {
          tmp = tmp->LeftBranch;
          continue;
        }
        else {
          tmp->LeftBranch = getFreeNode(value, tmp);
          return;
        }
      }
    }
  }

void printTree(Node *Root, const char *dir, int level) {
    if (Root) {
        printf("lvl %d %s = %d\n", level, dir, Root->data);
        printTree(Root->LeftBranch, "left", level + 1);
        printTree(Root->RightBranch, "right", level + 1);
    }
}

int min(Node *Root) {
 while (Root->LeftBranch) {
   Root = Root->LeftBranch;
 }
 int min = Root->data;
 return min;
}

int find(Node *Root) {
  if (Root == NULL) {
     return 0;
  }
  if (isPrime(Root->data)) {
    myqueue.push(Root->data);
  }
  find(Root->LeftBranch);
  find(Root->RightBranch);
}
Node *minimum(Node *Root) {
    while (Root->LeftBranch) {
        Root = Root->LeftBranch;
    }
    return Root;
}

Node *deleteNode(Node *Root, int key) {
  if (Root == NULL) {
      return Root;
  }
  else {
     if (key < Root->data) {
        Root->LeftBranch = deleteNode(Root->LeftBranch, key);
      }
      else if(key > Root->data) {
        Root->RightBranch = deleteNode(Root->RightBranch, key);
      }
      else if (Root->LeftBranch != NULL && Root->RightBranch != NULL) {
        Root->data = minimum(Root->RightBranch)->data;
        Root->RightBranch = deleteNode(Root->RightBranch, Root->data);
      }
      else {
        if (Root->LeftBranch != NULL) {
          Root = Root->LeftBranch;
        }
        else {
          Root = Root->RightBranch;
        }
      }
    }
    return Root;
  }

void delete2(Node *Root) {
  cout << "My queue equal: ";
  while(!myqueue.empty()) {
    cout << myqueue.front() << " ";
    deleteNode(Root, myqueue.front());
    myqueue.pop();
  }
}
bool isPrime(int n) {
  for (int i = 2; i <= n; i++) {
    if (n % i == 0) {
      return false;
    }
  }
  return true;
}

Дано бинарное дерево,рандомно было записано данные. Далее необходимо удалить все простые числа. В функции find() происходит запись в очередь. После в функции delete2() удаление. Проблема: в очередь попадають не те данные что нужно. Из-за етого происходит не коректное удаление Вопрос: помогите написать правильную реализацию find()

Answer 1

BUG1 : Проверка простоты числа: проверять на деление нужно от 2 до sqrt(n). BUG2 : addToTree() при добавлении числа , которое уже есть в дереве будет глухой висяк. BUG3 : min() при пустом дереве будет крушение программы вообще. BUG4 : delete2(Node*) : новый указатель корня дерева возвращается из deleteNode, а сам результат нового корня игнорируется.

Answer 2

Вы неверно реализовали алгоритм проверки простого числа в isPrime(int n)

#include <math.h>
bool isPrime(int n)
{
    for(int i = 2; i <= sqrt(n); i++)
    {
        if(n % i == 0)
            return false;
    }
    return true;
}
Answer 3
bool isPrime(unsigned n)
{
    unsigned sn = sqrt(n) + 1;
    if(n % 2 == 0) return false;
    for(int i = 3; i < sn; i += 2)
    {
        if(n % i == 0)
            return false;
    }
    return true;
}

Это быстрее, но можно улучшить

READ ALSO
can&#39;t find linker symbol for virtual table for `ClassName`

can't find linker symbol for virtual table for `ClassName`

Есть класс ClassName который определен в динамической библиотеке, и который используется в исполняемом файлеВо время выполнения возникает ошибка

137
Ошибка при освобождении памяти

Ошибка при освобождении памяти

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

175
Ввод элементов стека через консоль

Ввод элементов стека через консоль

Как реализовать ввод элементов стека не статичными данными, а с помощью ввода через консоль? Ну, те

187