Breadth First Traversal With Binary Search Tree C++
Solution 1
It will be very hard to get the spacing correctly as a key may have multiple digits and this should affect the spacing for all levels above the given node.
As for how to add NULL
- simply add else clauses for your ifs where you print a NULL:
if (root) {
q.push(root);
cout << root->data << " ";
} else {
cout << "NULL ";
}
while (!q.empty()) {
const node * const temp_node = q.front();
q.pop();
if (temp_node->left) {
q.push(temp_node->left);
cout << temp_node->left->data << " ";
} else {
cout << "NULL ";
}
if (temp_node->right) {
q.push(temp_node->right);
cout << temp_node->right->data << " ";
} else {
cout << "NULL ";
}
}
Solution 2
void TreeBreadthFirst(Node* treeRoot)
{
Queue *queue = new Queue();
if (treeRoot == NULL) return;
queue->insert(treeRoot);
while (!queue->IsEmpty())
{
Node * traverse = queue->dequeue();
cout<< traverse->data << “ “ ;
if (traverse->left != NULL)
queue->insert( traverse->left);
if (traverse->right != NULL)
queue->insert(traverse->right);
}
delete queue;
}
Solution 3
I've made a program in c. This code will display somewhat like a tree.
struct node{
int val;
struct node *l,*r;
};
typedef struct node node;
int findDepth(node *t){
if(!t) return 0;
int l,r;
l=findDepth(t->l);
r=findDepth(t->r);
return l>r?l+1:r+1;
}
void disp(node *t){
if(!t)
return;
int l,r,i=0;
node *a[100],*p;
int front=0,rear=-1,d[100],dep,cur,h;
a[++rear]=t;
d[rear]=0;
cur=-1;
h=findDepth(t);
printf("\nDepth : %d \n",h-1);
while(rear>=front){
dep = d[front];
p=a[front++];
if(dep>cur){
cur=dep;
printf("\n");
for(i=0;i<h-cur;i++) printf("\t");
}
if(p){
printf("%d\t\t",p->val);
a[++rear]=p->l;
d[rear]=dep+1;
a[++rear]=p->r;
d[rear]=dep+1;
}
else printf ("-\t\t");
}
}
Conor
Updated on April 05, 2020Comments
-
Conor about 4 years
Maybe fast/simple Question. I have a a Binary Tree Implemented already, Then I was hoping to convert binary search tree into an array or at least print it out as if in an array. Where I am having trouble with is how to get the NULL/flags in there '\0'.
for example lets say I have a tree like:
10 / \ 6 12 / \ \ 1 8 15 \ 4
And I want it to print how its supposed to print. Like:
[10,6,12,1,8,\0,15,\0,4,\0,\0,\0,\0,\0,\0] ^Something Like this^ I don't know if I counted the NULL correctly.
Or Another Option on how i want to go about showing Visually my Tree is how to get the spacing correctly outputted like with the '/' and '\' pointing to the keys from the parents:
10 / \ 6 12 / \ \ 1 8 15 \ 4
Here is something that I tried elaborating on code wise but im stuck:
void BreadthFirstTravseral(struct node* root) { queue<node*> q; if (!root) { return; } for (q.push(root); !q.empty(); q.pop()) { const node * const temp_node = q.front(); cout<<temp_node->data << " "; if (temp_node->left) { q.push(temp_node->left); } if (temp_node->right) { q.push(temp_node->right); } } }
Any Kind of Help or Link and or advice and or example code would be very much appreciated.