DS二叉树--层次遍历

时间:2024-06-10 09:07:38

题目描述

层次遍历二叉树,是从根结点开始遍历,按层次次序“自上而下,从左至右”访问树中的各结点。

建树方法采用“先序遍历+空树用0表示”的方法

要求:采用队列对象实现,函数框架如下:

DS二叉树--层次遍历

输入

第一行输入一个整数t,表示有t个测试数据

第二行起输入二叉树先序遍历的结果,空树用字符‘0’表示,输入t行

输出

逐行输出每个二叉树的层次遍历结果

样例输入

2
AB0C00D00
ABCD00E000FG00H0I00

样例输出

ABDC
ABFCGHDEI
#include<iostream>
#include<string>
#include<queue>
using namespace std;
class BitreeNode
{
public:
char data;
BitreeNode *LeftChild, *RightChild;
BitreeNode() :LeftChild(NULL), RightChild(NULL) {}
~BitreeNode() {}
};
class Bitree
{
private:
BitreeNode *Root;
int pos, sum;
string strTree;
void LevelOrder(BitreeNode *t)
{
queue<BitreeNode*> tq;
BitreeNode *p = t;
int x = ;
while (x < sum)
{
if (p)
tq.push(p);
while (!tq.empty())
{
p = tq.front();
tq.pop();
cout << p->data;
x++;
if (p->LeftChild)
tq.push(p->LeftChild);
if (p->RightChild)
tq.push(p->RightChild);
}
}
}
BitreeNode *CreateBitree()
{
BitreeNode *T;
char ch;
ch = strTree[pos++];
if (ch == '')
T = NULL;
else
{
sum++;
T = new BitreeNode();
T->data = ch;
T->LeftChild = CreateBitree();
T->RightChild = CreateBitree();
}
return T;
}
public:
Bitree() {}
~Bitree(){}
void CreateBitree(string TreeArray)
{
pos = ;
sum = ;
strTree.assign(TreeArray);
Root = CreateBitree();
}
void LevelOrder()
{
LevelOrder(Root);
}
}; int main()
{
int t;
cin >> t;
while (t--)
{
string str;
cin >> str;
Bitree *Tree;
Tree = new Bitree();
Tree->CreateBitree(str);
Tree->LevelOrder();
cout << endl;
}
return ;
}