[数据结构与算法]uva122 二叉树层序遍历/bfs

uva 122

题目大意：给出一组二叉树的节点，输出层序遍历的结果，如果路径不完整，输出“not complete"

• 如果采用数组下表体现位置关系的方法（下标为k的节点左右儿子分别为2k和2k+1），数组很容易溢出，或者说根本开不了如此巨大的数组（256个节点串成一条链），所以这种方法只适用于完全树

• 还是得利用结构体模拟。主要需要实现：

  1. 树的建立：在读取输入时建立，对于跳跃的节点，插入able为0的节点链接即可，在后续判断时，必须able为1方可
  2. 遍历：层序遍历是广度优先，可以利用队列实现。最初push root进队列，此后每次取出一个节点，判断该节点的able，可以的话依次在队列尾插入该节点的左右孩子（注意非空），如此直至队列为空，即实现了层序遍历（bfs）
  3. 建立节点，不一定要用动态申请的方法。本题中节点数最多为256,完全可以用数组实现。具体做法是：开一个数组nodes存节点结构体，维护一个int值cnt,表示当前已生成节点个数，生成新节点指针即为nodes + ++cnt，记得初始化，这是结构体+指针的方法。还有数组+下标的方法，是将结构体中的成员都开一个数组，这些数组的下标都使用cnt

• 关于二叉树的物理存储，如果使用静态方法，在其他情况下也是通用的。如果有频繁的添加与删除操作，一直增加的cnt就不合理了。所以可以维护一个“内存池”：将所有空闲的节点存入一个链表，新建时取走一个、销毁时插入一个。

#include <vector>
#include <iostream>
#include <queue>
#include <fstream>

using namespace std;

#define TEST 0
typedef struct Node *pNode;

struct Node
{
    int able;
    int v;
    pNode l, r;

    Node() : able(0), l(NULL), r(NULL) {}
};

pNode root;
vector<int> ans;
ofstream ofs;

void removeTree(pNode d)
{
    if (d == NULL)
        return;
    if (d->l)
        removeTree(d->l);
    if (d->r)
        removeTree(d->r);
    delete d;
}

bool readInput()
{
    while (getchar() != '(')
        continue;
    if (cin.peek() == ')')
        return false;
    int v;
    char c;
    pNode p = root;
    cin >> v;
    getchar();

    while (1)
    {
        c = getchar();
        if (c == 'L')
        {
            if (!p->l)
                p->l = new Node;
            p = p->l;
        }
        if (c == 'R')
        {
            if (!p->r)
                p->r = new Node;
            p = p->r;
        }
        if (c == ')')
            break;
    }
    p->able++;
    p->v = v;
    return true;
}

bool bfs()
{
    pNode cur;
    queue<pNode> q;
    q.push(root);
    while (q.size())
    {
        cur = q.front();
        q.pop();
        if (cur->able != 1)
            return false;
        ans.push_back(cur->v);
        if (cur->l)
            q.push(cur->l);
        if (cur->r)
            q.push(cur->r);
    }
    return true;
}

void showAns()
{
    for (int i = 0; i != ans.size(); ++i)
        (TEST ? ofs : cout) << ans.at(i) << (i == ans.size() - 1 ? "" : " ");
    (TEST ? ofs : cout) << '\n';
}

int main()
{

    if (TEST)
    {
        ofs.open("/home/lixiaoqi/Documents/Code/C++/1.txt");
        if (!ofs.is_open())
            throw runtime_error("FILE NOT OPEN!");
    }

    while (cin.peek() != EOF)
    {
        root = new Node;
        while (readInput())
            continue;
        if (bfs())
            showAns();
        else
            (TEST ? ofs : cout) << "not complete\n";

        ans.clear();
        removeTree(root);
        cin.ignore(1024, '\n');
    }
    return 0;
}