层次遍历二叉树

描述

二叉树是非常重要的树形数据结构，层次遍历一棵二叉树是按从上到下、从左到右的次序访问树上的结点。例如，图1020所示的二叉树层次遍历序列为A B C D E F。

图1020

请根据先序遍历序列建立一棵的二叉树（用#代表空树或空子树），输出层次遍历序列。

输入

二叉树的先序遍历序列，用#代表空树或空子树

输出

二叉树层次遍历序列

样例输入

A B # D # # C E # # F # #

样例输出

LevelOrder: A B C D E F

 

 

#include<iostream.h>
#include<list>
using namespace std;
typedef struct Tnode
{
    char v;
    struct Tnode*left,*right;
}Node;
list <Node*> q;
Node* Create()
{
    Node * T;
    char ch;
//    ch=getchar();getchar();
    cin>>ch;
    if(ch=='#')
        T=NULL;
    else
    {
        if(T=new Node)
        {
            T->v=ch;
            T->left=Create();
            T->right=Create();
        }
    }
    return T;
}
int main()
{
    Node* T;
    T=Create();
    if(T)
    q.push_back(T);
    printf("LevelOrder:");
    while(q.size()>0)
    {
        Node* u=q.front();q.pop_front();
        printf(" %c",u->v);
        if(u->left!=NULL)q.push_back(u->left);
        if(u->right!=NULL)q.push_back(u->right);
    }
printf("\n");
    return 0;
}

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

#include<iostream.h> #include<queue> using namespace std; //#include<list.h> typedef struct Node { char c; struct Node *left, *right; }Node; Node *Create() { Node *T; char ch; cin>>ch; if(ch=='#') T=NULL; else { if(T=new Node) { T->c=ch; T->left=Create(); T->right=Create(); } } return T; } int main() { queue<Node*> q; Node* T; T=Create(); if(T) q.push(T); cout<<"LevelOrder:"; while(q.size()>0) { Node* u=q.front(); q.pop(); cout<<u->c<<" "; if(u->left) q.push(u->left); if(u->right) q.push(u->right); } cout<<endl; return 0; }