Редактирование двоичного дерева поиска

Question

Я работаю над графической системой меню SFML BST. У меня есть тестовые файлы. Некоторые из них дают ожидаемый результат, а другие - нет. Я пытаюсь разобраться на пару дней, и я не могу понять, почему. Кажется, что числа вводят в дерево правильно, но входы, которые имеют повторяющиеся числа, как представляется, нарушают структуру обхода дерева, поскольку не все узлы будут выведены. См. Мой код и примеры ниже.

У меня есть стойка и т. Д. В моем файле .h, который, я уверен, отлично работает.

Может ли кто-нибудь сказать мне, почему некоторые из них не пересекают все узлы?

Вход: 1,3,5,6,7,8,9,10 Выход: График выглядит так, как ожидалось, и обход выглядит как ожидаемый.

Вход: 3,4,99,3,10,11,10 Выход 3,3,10,10 (не ожидается)

Вход: 10,3,10,24,3,20 Выход: 3,3,10,10,24

//Binary Search Tree Program 
#include "BinarySearchTree.h" 

using namespace std; 

sf::CircleShape shape(50); 

BinarySearchTree::BinarySearchTree() 
{ 
    root = NULL; 

    if (!font.loadFromFile("font.ttf")) 
     cout << "Error loading font!"; 
} 


void BinarySearchTree::loadFile(int num) { 
    data.clear(); 
    string s = to_string(num); 
    string text; 
    string temp; // Added this line 
    ifstream file; 
    file.open("files/file" + s + ".txt"); 

    while (!file.eof()) 
    { 
     getline(file, temp); 
     text.append(temp); // Added this line 
    } 

    std::istringstream ss(text); 
    std::string token; 
    while (std::getline(ss, token, ',')) { 
     std::cout << token << ','; 
     std::string myString = token; 
     int value = atoi(myString.c_str()); //value = 45 
     data.push_back(value); 
    } 
} 

void BinarySearchTree::passToinsert() 
{ 
    for (std::vector<int>::iterator it = data.begin(); it != data.end(); ++it) { 
     insert(*it); 
     //cout << *it; 
    } 
} 


void BinarySearchTree::insert(int d) 
{ 
    tree_node* t = new tree_node; 
    tree_node* parent; 
    t->data = d; 
    t->left = NULL; 
    t->right = NULL; 
    parent = NULL; 

    // is this a new tree? 
    if (isEmpty()) root = t; 
    else 
    { 
     //Note: ALL insertions are as leaf nodes 
     tree_node* curr; 
     curr = root; 
     // Find the Node's parent 
     while (curr) 
     { 
      parent = curr; 
      if (t->data > curr->data) curr = curr->right; 
      else curr = curr->left; 
     } 

     if (t->data < parent->data) { 
      parent->left = t; 
      cout << "L-" << t->data<<endl; 
     } 
     else { 
      parent->right = t; 
      cout << "R-" << t->data << endl; 

     } 
    } 
} 


void BinarySearchTree::print_inorder() 
{ 
    inorder(root); 
} 

void BinarySearchTree::inorder(tree_node* p) 
{ 
    if (p != NULL) 
    { 
     if (p->left) inorder(p->left); 
     cout << " " << p->data << " "; 
     if (p->right) inorder(p->right); 
    } 
    else return; 
} 

void BinarySearchTree::print_postorder() 
{ 
    postorder(root, 100,0,0,0,0); 
} 


void BinarySearchTree::postorder(tree_node* p, int indent, int leftNodeCount, int rightNodeCount, int left, int right) 
{ 

    if (p != NULL) { 

     if (left = 1) { 
      std::string s = std::to_string(p->data); 

      nodes[nodeCount].setFont(font); 
      nodes[nodeCount].setFillColor(sf::Color::White); 
      nodes[nodeCount].setString(s); 
      nodes[nodeCount].setPosition(sf::Vector2f(indent, 80 + (leftNodeCount * 80))); 
      nodeCount++; 
      leftNodeCount++; 
     } 
     else if (right = 1) { 
      std::string s = std::to_string(p->data); 

      nodes[nodeCount].setFont(font); 
      nodes[nodeCount].setFillColor(sf::Color::White); 
      nodes[nodeCount].setString(s); 
      nodes[nodeCount].setPosition(sf::Vector2f(indent, 80 + (rightNodeCount * 80))); 
      nodeCount++; 
      rightNodeCount++; 
     } 
     else { 
      std::string s = std::to_string(p->data); 

      nodes[nodeCount].setFont(font); 
      nodes[nodeCount].setFillColor(sf::Color::White); 
      nodes[nodeCount].setString(s); 
      nodes[nodeCount].setPosition(sf::Vector2f(indent, 80 + (nodeCount * 80))); 
      nodeCount++; 
     } 


     if (p->right) { 
      postorder(p->right, indent + 80, leftNodeCount, rightNodeCount,left=0,right=1); 
     } 
     if (p->left) { 
      postorder(p->left, indent - 80, leftNodeCount, rightNodeCount, left = 1, right = 0); 
     } 
    } 
} 

//Draw sub menu heading text and options to screen 
void BinarySearchTree::drawNodes(sf::RenderWindow &window) 
{ 
    window.clear(); 

    for (int i = 0; i < 10; i++) 
    { 
     window.draw(nodes[i]); 
    } 

    window.display(); 
} 

Answer 1

На самом деле цифры не вставляются в дерево правильно. Основная проблема заключается в функции insert()class BinarySearchTree.

В то время как петли while (curr), переключение между левым и правым управляется при условии, если-if (t->data > curr->data), при условии, что случай t->data == curr->data подключен к левой стороне.

После цикла while переключатель между левым и правым управляется if-условием if (t->data < parent->data), предполагая, что кейс t->data == parent->data подключен к правой стороне. И не на левую сторону !!!

Решение - просто замените условие выключателя внутри цикла while, как показано ниже.

if (t->data < curr->data) { 
    curr = curr->left; 
} 
else { 
    curr = curr->right; 
} 

Вместо:

if (t->data > curr->data) curr = curr->right; 
else curr = curr->left;