Messages

1

General / Avoid collision of nodes while representing Binary Tree in SFML

« on: December 24, 2019, 03:48:43 pm »

Hello, following is the code of the prgoram I have created in SFML (Please note, this is a Binary SEARCH Tree and also that I have only given the codes of Display and Insertion as others aren't required, so that to keep the code's length as small as possible. Moreover, the nodes won't show the values as I haven't done that yet. This is really a very basic code but does explain the problem)

#include <SFML/Graphics.hpp>
#include <queue>
#include <iostream>
using namespace std;
sf::RenderWindow window(sf::VideoMode(1070, 920), "SFML works!");
struct node
{
        int data;
        node *left, *right, *parent;
        sf::CircleShape shape;
        sf::RectangleShape leftone;
        sf::RectangleShape rightone;
}*root;
class Tree
{
public:
        Tree();
        void insert(int, node*, int, int, int, int);
        void Display(node*);
        void inOrder(node*);
        void PostOrder(node*);
        void PreOrder(node*);
        bool isEmpty();
        void Deletion(int);
        node* SearchNode(int, node*);
};
bool Tree::isEmpty()
{
        if (!root)
                return true;
        return false;
}
Tree::Tree() { root = NULL; }
void Tree::insert(int data, node* Node = root, int x = 250, int y = 50, int a = 260, int b = 85)
{
        node* new_node = new node;
        new_node->shape.setRadius(20);
        new_node->shape.setFillColor(sf::Color::Green);
        new_node->left = new_node->right = new_node->parent = NULL;
        new_node->data = data;
        new_node->shape.setPosition(sf::Vector2f(x, y));
        if (!root)
        {
                root = new_node;
                return;
        }
        if (data >= Node->data)
        {
                if (Node->right)
                        insert(data, Node->right, x + 50, y + 50, a + 50, b + 50);
                else
                {
                        Node->right = new_node;
                        new_node->parent = Node;
                        new_node->shape.setPosition(sf::Vector2f((x + 50), (y + 50)));
                        new_node->parent->rightone.setSize(sf::Vector2f(50, 5));
                        new_node->parent->rightone.setFillColor(sf::Color::Red);
                        new_node->parent->rightone.setRotation(230);
                        new_node->parent->rightone.setPosition(sf::Vector2f(a+50, b+40));
                }
        }
        else if (data < Node->data)
        {
                if (Node->left)
                        insert(data, Node->left, x - 50, y + 50, a - 50, b + 50);
                else
                {
                        Node->left = new_node;
                        new_node->parent = Node;
                        new_node->shape.setPosition(sf::Vector2f((x - 50), (y + 50)));
                        new_node->parent->leftone.setSize(sf::Vector2f(50, 5));
                        new_node->parent->leftone.setFillColor(sf::Color::Red);
                        new_node->parent->leftone.setRotation(130);
                        new_node->parent->leftone.setPosition(sf::Vector2f(a, b));
                }
        }
}
void Tree::Display(node* Root = root)
{
        if (!root)
        {
                cout << "Nothing to Display";
                return;
        }
        queue<node*> obj;
        obj.push(Root);
        while (!obj.empty())
        {
                node* temp = obj.front();
                window.draw(temp->shape);
                if (temp->left)
                        window.draw(temp->leftone);
                if (temp->right)
                        window.draw(temp->rightone);
                //cout << temp->data << " ";
                obj.pop();
                if (temp->left)
                        obj.push(temp->left);
                if (temp->right)
                        obj.push(temp->right);
        }
        window.display();
}

int main()
{
        int n;
        Tree obj;
        while (window.isOpen())
        {
                cout << "Enter Number to Insert: ";
                cin >> n;
                obj.insert(n);
                sf::Event event;
                obj.Display();
                while (window.pollEvent(event))
                {
                        if (event.type == sf::Event::Closed)
                                window.close();
                }

                window.clear();
        }

        return 0;
}

So, basically, I am taking an input on Console (I still can't figure out how to take integer input on SFML Window.. I am pretty new to SFML) and then creating a tree and using BFS method (Queue) to display the nodes of trees...
As you would be able to see (if you run the code), the nodes are being created successfully and their connections as well.
However, there is one big issue that I am facing.

Suppose these values are added to the tree,

50 -> Added as Root Node
75 -> Added to the right of Root Node
25 -> Added to the left of Root Node
37 -> Added to the right of 25
67 -> Added to the left of 75

So, it works well until addition of 37 (that also prints out exactly below the root node, though which is wrong) however, as soon as I enter the node 67, it gets added to the same position as 37 and hence, only one of them shows on window.
Now, I can alter their coordinates and expand them a bit but eventually, I will end up facing the same issue after addition of few more values.
How can I avoid it? Could you help please?

There's a BST Visualizer available online which provides a pretty good solution. (Please refer here if you want to: https://www.cs.usfca.edu/~galles/visualization/BST.html )
It decreases/increases the x coordinate of the left/right child of root whenever it detects this pattern of addition (Root->Left->Right... or Root->Right->Left) but I am failing to make a proper logic to implement this idea. Can you help in this regard, please? Or provide a different solution? Thank you!