DS二叉树--层次遍历

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

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

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

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

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

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

样例输入
2
AB0C00D00
ABCD00E000FG00H0I00
样例输出
ABDC
ABFCGHDEI

#include<iostream>
#include<string>
#include<queue>
using namespace std;
int flag= 0;
 
class BiTreeNode{
    public:
        char data;
        BiTreeNode *LeftChild;
        BiTreeNode *RightChild;
        BiTreeNode():LeftChild(NULL), RightChild(NULL){
             
        }
        ~BiTreeNode(){
             
        }
};
 
class BiTree{
    private:
        BiTreeNode *Root;
        int pos;
        string strTree;
        BiTreeNode* CreateBiTree(){
            BiTreeNode *T;
            char ch;
            ch= strTree[pos++];
         
             
            if(ch== '0')
              T= NULL;
            else{
                flag++;//记录树的节点数
                T= new BiTreeNode();
                T->data= ch;
                T->LeftChild= CreateBiTree();
                T->RightChild= CreateBiTree();
            }
            return T;
        }
     
        void LevelOrder(BiTreeNode* t){
            queue<BiTreeNode*> tq;
            BiTreeNode* p= t;
             
            int k= 0;
            BiTreeNode* pos;
            while(k< flag){
                if(p){
                    cout<<p->data;
                    k++;
                    if(p->LeftChild)
                     tq.push(p->LeftChild);
                    if(p->RightChild)
                     tq.push(p->RightChild);
                      
                }
                if(!tq.empty()){
                    p= tq.front();
                    tq.pop();
                }
            }
 
        }
    public:
        BiTree(){
             
        }
        ~BiTree(){
             
        }
        void CreateTree(string TreeArray){
            pos= 0;
            flag= 0;
            strTree.assign(TreeArray);
            Root= CreateBiTree();
        }
        
        void LevelOrder(){
            LevelOrder(Root);
        }
};
 
int main(){
    int t;
    cin>>t;
     
    while(t--){
        string str;
        BiTree tree;
        cin>>str;
     
        tree.CreateTree(str);
        tree.LevelOrder();
        cout<<endl;
    }
    return 0;
}

另一种思路：