Please help with the breadth-width tree traversal algorithm in C++
Here is the code:
# include & lt; vector & gt;
#include & lt; iostream & gt;
#include & lt; queue & gt;
#define PRE 0
#define IN 1
#define POST 2
template & lt; class T & gt;
class tree
{
public:
tree ();
~ tree ();
void push (T inf);
std :: vector & lt; T & gt; DFS (int flag);
std :: vector & lt; T & gt; BFS ();
int get_size ();
private:
struct node
{
node * left;
node * right;
T inf;
node (T inf);
};
int size;
node * root;
void push (T inf, node * current);
void DFS (node * current, std :: vector & lt; T & gt; & amp; buffer, int flag);
};
template & lt; class T & gt;
tree & lt; T & gt; :: node :: node (T inf)
{
left = nullptr;
right = nullptr;
this - & gt; inf = inf;
}
template & lt; class T & gt;
tree & lt; T & gt; :: tree ()
{
size = 0;
root = nullptr;
}
template & lt; class T & gt;
tree & lt; T & gt; :: ~ tree ()
{
}
template & lt; class T & gt;
int tree & lt; T & gt; :: get_size ()
{
return size;
}
template & lt; class T & gt;
void tree & lt; T & gt; :: push (T inf)
{
if (root == nullptr)
{
root = new node (inf);
size ++;
}
else
{
if (inf & lt; = root- & gt; inf)
{
if (root- & gt; left! = nullptr)
push (inf, root- & gt; left);
else
{
root- & gt; left = new node (inf);
size ++;
}
}
else
{
if (root- & gt; right! = nullptr)
push (inf, root- & gt; right);
else
{
root- & gt; right = new node (inf);
size ++;
}
}
}
}
template & lt; class T & gt;
void tree & lt; T & gt; :: push (T inf, node * current)
{
if (inf & lt; = current- & gt; inf)
{
if (current- & gt; left! = nullptr)
push (inf, current- & gt; left);
else
{
current- & gt; left = new node (inf);
size ++;
}
}
else
{
if (current- & gt; right! = nullptr)
push (inf, current- & gt; right);
else
{
current- & gt; right = new node (inf);
size ++;
}
}
}
template & lt; class T & gt;
std :: vector & lt; T & gt; tree & lt; T & gt; :: DFS (int flag)
{
std :: vector & lt; T & gt; buffer;
buffer.reserve (size);
if (root == nullptr)
throw std :: invalid_argument ("error - void tree \ n");
if (flag == 0)
buffer.push_back (root- & gt; inf);
DFS (root- & gt; left, buffer, flag);
if (flag == 1)
buffer.push_back (root- & gt; inf);
DFS (root- & gt; right, buffer, flag);
if (flag == 2)
buffer.push_back (root- & gt; inf);
return buffer;
}
template & lt; class T & gt;
void tree & lt; T & gt; :: DFS (node * current, std :: vector & lt; T & gt; & amp; buffer, int flag)
{
if (current == nullptr)
return;
if (flag == 0)
buffer.push_back (current- & gt; inf);
DFS (current- & gt; left, buffer, flag);
if (flag == 1)
buffer.push_back (current- & gt; inf);
DFS (current- & gt; right, buffer, flag);
if (flag == 2)
buffer.push_back (current- & gt; inf);
}
template & lt; class T & gt;
std :: vector & lt; T & gt; tree & lt; T & gt; :: BFS ()
{
std :: queue & lt; T & gt; temp;
}
Answer 1
figured it out
template & lt; class T & gt;
std :: vector & lt; T & gt; tree & lt; T & gt; :: BFS ()
{
std :: vector & lt; T & gt; buffer;
buffer.reserve (size);
std :: queue & lt; node & gt; vertex;
vertex.push (* root);
while (! vertex.empty ())
{
node current = vertex.front ();
vertex.pop ();
buffer.push_back (current.inf);
if (current.left! = nullptr)
vertex.push (* current.left);
if (current.right! = nullptr)
vertex.push (* current.right);
}
return buffer;
}