I am trying to insert new nodes to binary search tree. I get no error, but if I run this program sometimes the tree displays correctly in cmd and sometimes nothing happens and the program doesn't crash, but the console is like waiting for something. I can't figure it out where the mistake is. Here is the code:

#include <iostream>
#include <string>

template <typename T>
class BinarySearchTree {
public:

    class Node {
    public:
        T data;
        Node* left;
        Node* right;
    };

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

    Node* getRoot() {
        return root;
    }

    Node* createNode(T data) {
        Node* newNode = new Node();
        newNode->data = data;
        newNode->left = nullptr;
        newNode->right = nullptr;
        return newNode;
    }

    Node* insert(Node*& root, T data) {
        Node* current = root;
        Node* prev = nullptr;

        while (current != nullptr) {
            prev = current;
            if (current->data < data)
                current = current->right;
            else if (current->data > data)
                current = current->left;
            else
                continue;
        }

        if (prev == nullptr)
            prev = createNode(data);
        else if (prev->data < data)
            prev->right = createNode(data);
        else if (prev->data > data)
            prev->left = createNode(data);
        else if (prev->data == data)
            prev->data = data;
        return prev;
    }

    class Trunk {
    public:
        Trunk* prev;
        std::string str;

        Trunk(Trunk* prev, std::string str) {
            this->prev = prev;
            this->str = str;
        }
    };

    void showTrunks(Trunk* p) {
        if (p == nullptr)
            return;

        showTrunks(p->prev);
        std::cout << p->str;
    }

    void printTree(Node* root, Trunk* prev, bool isLeft) {
        if (root == nullptr)
            return;

        std::string prev_str = "    ";
        Trunk* trunk = new Trunk(prev, prev_str);

        printTree(root->right, trunk, true);

        if (!prev)
            trunk->str = "---";
        else if (isLeft) {
            trunk->str = ".---";
            prev_str = "   |";
        }
        else {
            trunk->str = "`---";
            prev->str = prev_str;
        }

        showTrunks(trunk);
        std::cout << " " << root->data << std::endl;

        if (prev)
            prev->str = prev_str;

        trunk->str = "   |";

        printTree(root->left, trunk, false);
    }
};

struct Point {
    int x;
    int y;

    Point(int x, int y) {
        this->x = x;
        this->y = y;
    }

    Point() {
        x = 0;
        y = 0;
    }

    bool operator>(const Point& point) {
        if ((x   y) > (point.x   point.y))
            return true;
        return false;
    }

    bool operator<(const Point& point) {
        if ((x   y) < (point.x   point.y))
            return true;
        return false;
    }

    bool operator==(const Point& point) {
        if ((x   y) == (point.x   point.y))
            return true;
        return false;
    }

    bool operator!=(const Point& point) {
        if ((x   y) != (point.x   point.y))
            return true;
        return false;
    }
};

std::ostream& operator<<(std::ostream& COUT, Point& point) {
    COUT << "(" << point.x << ", " << point.y << ")";
    return COUT;
}

And here is the main function:

int main()
{
    srand(time(0));
    BinarySearchTree<Point>* tree = new BinarySearchTree<Point>();
    BinarySearchTree<Point>::Node* root = tree->getRoot();

    Point point;
    point.x = 100;
    point.y = 100;
    root = tree->insert(root, point);
    for (int i = 0; i < 10; i  ) {
        Point point;
        point.x = rand() % 100;
        point.y = rand() % 100;
        tree->insert(root, point);
    }
    tree->printTree(root, nullptr, false);

    return 0;
}

CodePudding user response：

During

    while (current != nullptr) {
        prev = current;
        if (current->data < data)
            current = current->right;
        else if (current->data > data)
            current = current->left;
        else
            continue;
    }

If current->data is equal to data, what will happen? You will continue the loop, with current unchanged. This will loop forever. That would explain your program hanging.

There is also no point in passing a reference in:

Node* insert(Node*& root, T data)

This would do just as well an be less of an eye sore:

Node* insert(Node* root, T data)