AG. DS binary tree -- hierarchical traversal

Title Description

Hierarchical ergodic binary tree , It starts from the root node , In order of hierarchy “ From top to bottom , From left to right ” Access the nodes in the tree .

The construction method is “ The first sequence traversal + Empty trees use 0 Express ” Methods

requirement ： Using queue objects to implement , The function framework is as follows ：

Input

Enter an integer in the first line t, Express t Test data

From the second line, enter the result of the prior traversal of the binary tree , Empty tree character ‘0’ Express , Input t That's ok

Output

Output the hierarchical traversal results of each binary tree line by line

The sample input

2
AB0C00D00
ABCD00E000FG00H0I00

Sample output

ABDC
ABFCGHDEI

Code

#include <bits/stdc++.h>
using namespace std;
string s;
int t;
struct NODE{
	char data;
	NODE *l,*r;
	NODE(){
		l=NULL;
		r=NULL;
	}
};

int id=0;
void build(NODE *&node){
	if(id<s.length()){
		if(s[id]=='0'){
		node=NULL;
		id++;
		return;
	}
	node=new NODE;
	node->data=s[id];
	id++;
	build(node->l);
	build(node->r);
	}
	
}

queue<NODE*> q;
void display(NODE *node){
	//
	q.push(node);
	while(!q.empty()){
		NODE *now=q.front();
		q.pop();
		cout<<now->data;
		if(now->l) q.push(now->l);
		if(now->r) q.push(now->r); 
	}
	cout<<endl;
}

int main(){
	cin>>t;
	while(t--){
		while(!q.empty()){
			q.pop();
		}
		id=0;
		s.clear();
		cin>>s;
		NODE *head=new NODE;
		build(head);
		display(head);
	}
	return 0;
}