此文章是vip文章,如何查看?  

1,点击链接获取密钥 http://nicethemes.cn/product/view29882.html

2,在下方输入文章查看密钥即可立即查看当前vip文章


15_3树(普通)的层序遍历

  • 时间:
  • 浏览:
  • 来源:互联网

题目描述:

从文件input_3.txt输入一个树,建树并输出层数为奇数的节点到output_3.txt中。

sample input:

A B C
B D
C E F H
D G

sample output:

第一层:A
第三层:D,E,F,H

AC代码

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <map>
#define maxn 100


using namespace std;
map<char,int>mp;


typedef struct
{
    int level;
    vector<char>child;
}Node;

Node T[maxn];

void InitMap()
{
    char ch='A';
    for(int i=1;i<=26;i++,ch++)
    {
        mp[ch]=i;
    }
}


void LevelOrder(int head)
{
    char Q[maxn],p;
    vector<char>R;
    int front=-1,rear=-1;
    int last=0,level=0;
    Q[++rear]=head;

    while(front<rear)
    {
        p=Q[++front];//出队
        R.push_back(p);//入队
        for(unsigned int i=0;i<T[mp[p]].child.size();i++)
        {
            Q[++rear]=T[mp[p]].child[i];
        }
        if(front==last)
        {
            level++;
            last=rear;
            if(level%2==1)
            {
                printf("第%d层的结点为:",level);
                for(unsigned int i=0;i<R.size();i++)
                {
                    printf("%c",R[i]);
                    if(i<R.size()-1)printf(",");
                }
                printf("\n");
            }
            R.clear();//
        }
    }
}


int main()
{
    freopen("input.txt","r",stdin);
    char root,ch;
    char head;
    int flag=0;
    InitMap();
    while((root=getchar())!=EOF)
    {
        if(!flag)
        {
            head=root;
            flag=1;
        }
        while((ch=getchar())!='\n'&&ch!=EOF)
        {
            if(ch>='A'&&ch<='Z')
            {
                T[mp[root]].child.push_back(ch);
            }
        }
    }//建立图
    LevelOrder(head);

}

本文链接http://element-ui.cn/news/show-50670.aspx