STL Queue error

Kalcor (188)
So I used STL queue inorder to do bfs on a binary search tree before and after deleting a node and it works well before deleting the node but after it just prints some weird ass numbers, then I tried the same code but with my own queue implementation and it worked fine? here is both:

my queue:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
 
#include <bits/stdc++.h>


#define fl(i,n)    for(int i = 0; i < n; i++)

#define ll   long long
#define nl   endl
#define pb   push_back
#define mp   make_pair
#define PII  pair<int,int>

#define EPS  1e-9
#define INF  1e9


using namespace std;

struct node{
int data;
node *right;
node *left;
};


class Queue{
private:
    Queue* data;
    Queue *next;
public:
    void enqueue(Queue *&qhead, Queue *&qtail, Queue* x){
        Queue *temp = new Queue;
        temp->data = x;
        temp->next = nullptr;
        if(isEmpty(qhead)){
            qhead = temp;
            qtail = temp;
            return;
        }
        qtail->next = temp;
        qtail = temp;
    }

    void dequeue(Queue *&qhead, Queue *&qtail){
        if(isEmpty(qhead)) return;
        if(qhead == qtail){
            qhead = qtail = nullptr;
            return;
        }
        qhead = qhead->next;
    }

    Queue *peek(Queue *qhead){
        if(qhead == nullptr) return 0;
        return (qhead->data);
    }

    bool isEmpty(Queue *qhead){
        if(qhead == nullptr) return true;
        return false;
    }
};




node *Insert(node *root, int x){
if(root == nullptr){
    root = new node;
    root->data = x;
    root->left = nullptr;
    root->right = nullptr;
}
else if(x <= root->data){
    root->left = Insert(root->left, x);
}
else{
    root->right = Insert(root->right, x);
}
return root;
}



node *find_min_special(node *root){
if(root == nullptr) return nullptr;
else if(root->left == nullptr) return root;
return find_min_special(root->left);
}



node  *delete_node(node *root, int data){
if(root == nullptr) return root;
if(data < root->data) root->left = delete_node(root->left, data);
else if(data > root->data) root->right = delete_node(root->right, data);
else {
    //case 1 child or 0 children
    if(root->left == nullptr){
        node *temp = root->right;
        delete root;
        return temp;

    }
    else if(root->right == nullptr){
        node *temp = root->left;
        delete root;
        return temp;
    }
    node *temp = find_min_special(root->right);
    root->data = temp->data;
    root->right = delete_node(root->right, temp->data);//delete duplicate
}
return root;
}

void bfs(node *root){
Queue Q;
Queue *qhead = nullptr;
Queue *qtail = nullptr;

node *temp = root;
while(temp != nullptr){
    cout << temp->data << " ";
    if(temp->left != nullptr) Q.enqueue(qhead,qtail,(Queue*)temp->left);
    if(temp->right != nullptr) Q.enqueue(qhead,qtail,(Queue*)temp->right);

    temp = (node*)Q.peek(qhead);
    Q.dequeue(qhead,qtail);
}
cout << nl;
}




/*
        15
      /    \
    10     20
   /  \   /  \
  8    12 19 25
min(left most node), max(right most node), height = max(left height(1), right height(1))+1(back to root) = 2.
*/


int main()
{
    node *root = nullptr;

    root = Insert(root, 15);
    Insert(root, 10);
    Insert(root, 8);
    Insert(root, 12);
    Insert(root, 20);
    Insert(root, 19);
    Insert(root, 25);
    bfs(root);
    root = delete_node(root, 20);
    bfs(root);
    //cout << dfs_sum(root);
    //cout << dfs_inorder(root) << " " << leaves(root);
    //cout << Search(root, 25);
    //cout << find_min(root) << " " << height(root) << " " << find_max(root);



    return 0;
}



using stl queue:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
 
#include <bits/stdc++.h>


#define fl(i,n)    for(int i = 0; i < n; i++)

#define ll   long long
#define nl   endl
#define pb   push_back
#define mp   make_pair
#define PII  pair<int,int>

#define EPS  1e-9
#define INF  1e9


using namespace std;

struct node{
int data;
node *right;
node *left;
};




node *Insert(node *root, int x){
if(root == nullptr){
    root = new node;
    root->data = x;
    root->left = nullptr;
    root->right = nullptr;
}
else if(x <= root->data){
    root->left = Insert(root->left, x);
}
else{
    root->right = Insert(root->right, x);
}
return root;
}



node *find_min_special(node *root){
if(root == nullptr) return nullptr;
else if(root->left == nullptr) return root;
return find_min_special(root->left);
}



node  *delete_node(node *root, int data){
if(root == nullptr) return root;
if(data < root->data) root->left = delete_node(root->left, data);
else if(data > root->data) root->right = delete_node(root->right, data);
else {
    //case 1 child or 0 children
    if(root->left == nullptr){
        node *temp = root->right;
        delete root;
        return temp;

    }
    else if(root->right == nullptr){
        node *temp = root->left;
        delete root;
        return temp;
    }
    node *temp = find_min_special(root->right);
    root->data = temp->data;
    root->right = delete_node(root->right, temp->data);//delete duplicate
}
return root;
}

void bfs(node *root){
queue<node*> q;

node *temp = root;
while(temp != nullptr){
    cout << temp->data << " ";
    if(temp->left != nullptr) q.push(temp->left);
    if(temp->right != nullptr) q.push(temp->right);

    temp = q.front();
    q.pop();
}
cout << nl;
}




/*
        15
      /    \
    10     20
   /  \   /  \
  8    12 19 25
min(left most node), max(right most node), height = max(left height(1), right height(1))+1(back to root) = 2.
*/


int main()
{
    node *root = nullptr;

    root = Insert(root, 15);
    Insert(root, 10);
    Insert(root, 8);
    Insert(root, 12);
    Insert(root, 20);
    Insert(root, 19);
    Insert(root, 25);
    bfs(root);
    root = delete_node(root, 20);
    bfs(root);
    //cout << dfs_sum(root);
    //cout << dfs_inorder(root) << " " << leaves(root);
    //cout << Search(root, 25);
    //cout << find_min(root) << " " << height(root) << " " << find_max(root);



    return 0;
}


it gave a runtime error on ideone.com but in my compiler printed a weird number which i guarantee is an address to some memory so i guess both errors are the same.


so what made stl queue output a runtime error but my queue implementation worked?
Last edited on
Peter87 (11256)
Line 86-87: You need to make sure not to call front() or pop() if the queue is empty.
Kalcor (188)
Thank you @peter :)
Topic archived. No new replies allowed.