Comment on page

/*
Assuming struct definition:
template<class T>
class Node
{
public:
explicit Node(T a) :
value{ a },
next{ nullptr },
left{ nullptr },
right{ nullptr } {}
T value;
Node *left;
Node *right;
Node *next;
};
*/
/*
The Algorithm:
- Implementing a regular BFS is sufficient in printing out a level order
traveral in a tree. Our goal here is to distinguish when a new line is
meet.
- We can infer a new line in the tree with a nullptr, when will denote
the end of a linked list.
- We note a new line in the instance that we've just uncovered a newline
and that the next element in the queue is not a new line. Consider the
tree:
4
2 6
1 3 5 7
- In a level order traversal, we either can add a maximum of 2 nodes in the
queue for a binary tree. As the base case, we push in the root and then
the nullptr.
- Then, 2 additional nodes are inserted. The next element in the queue will
be a nullptr. Which will denote the insertion of an additional nullptr.
- Before we can insert another nullptr, we 2 and 6 are both in the queue and will
insert 4 elements before the next incoming nullptr.
Consider a more complex example:
4
8 3
4 6
8 3
- In the first enqueue after the root are 3 elements. 8, 3, and a nullptr.
- 8 will have the opportunity to enqueue 4, just one element.
- After 8 gets popped off 3 is next and enqueues 6.
- Now our queue is: nullptr, 4,6
- nullptr enqueues another nullptr, and our queue becomes 4,6,nullptr.
- Notice that the queue will always respond with the number of children
that were inserted of each parent node. A nullptr will only be expressed when
the previous parent sufficiently had the opportunity to place its children
into the queue.
*/
template<typename T>
class B_tree
{
public:
{
if (!root) return;
queue<Node<T>*> q;
q.push(root);
q.push(nullptr);
while (!q.empty()) {
Node<T> *temp = q.front();
q.pop();
if (temp) {
temp->next = q.front();
if (temp->left)
q.push(temp->left);
if (temp->right)
q.push(temp->right);
}
else {
if (!q.empty() && q.front())
q.push(nullptr);
}
}
}
static void print_level_order(Node<T> *root)
{
if (root) {
Node<T> *iter = root;
while (iter) {
cout << iter->value << ' ';
iter = iter->next;
}
cout << endl;
if (root->left) {
print_level_order(root->left);
}
else if (root->right) {
print_level_order(root->right);
}
}
}
private:
};
/*
Testing: