10562 - Undraw the Trees-白红宇

10562 - Undraw the Trees

阅读量：5905 次

发布时间：2019-06-19

本文共 2959 字，大约阅读时间需要 9 分钟。

题意:

把教授留下的立体的 tree 转化成线性的 tree, 每个节点的输出形式为 (A()), 若有子节点, 则按先左后右的顺序输出在紧跟 A 的括号里, 依次嵌套, 直至全部输出.

思路:

1. 建树, 这是一棵不规则的树, 所以使用 vector<Node*> children_ 来存放其子节点的指针;

(1). 每读入一个节点, 就判断它的正下方(即下一行相同 index 处) 是否有 '|', 有则说明它有子树;

(2). 在节点的正下下方(即下二行相同 index 处) 看其连续 '-' 所横跨的区间, 就是其子树所在的区间;

(3). 在节点的正下下下方(即下三行), 看 3 中所得到的区间内, 是否有节点(即不为 '-', '|', ' ', '#'), 若有, 则递归创建子树, 并添加到 vector<Node*> children_ 中.

2. 打印树, 从根节点开始, 按 A(B()C()) 的形式递归打印. 最后在最外面再套一层 () 即可.

要点:

1. 注意有空树存在的情况, 此时直接输出 () 即可.

2. 一个节点, 其正下方必须有 '|' 才说明是有子节点的, 否则就是没有子节点的; 不考虑这一点, 会 WA.

题目:

代码:

# include 
    
     # include 
     
      # include 
      
       # include 
       
        # include 
        
         # include 
         
          # include 
          
           # include 
           
            # include 
            
             # include 
             
              # include 
              
               using namespace std;class Node{public: char c_; vector
               
                 children_;};// 判断 line[idx] 是否为一个合法的 Node, 即不能为 '-', '|', ' ' (space) and '#'bool isNode(const string& line, int idx) { assert (idx < line.size()); return (line[idx] != '-' && line[idx] != '|' && line[idx] != ' ' && line[idx] != '#');}// 判断一个节点是否有 child, 即他的正下方必须是 |// 一定要有这个判断, 否则 WAbool hasChild(const vector
                
                 & lines, int numRow, int idx) { int r = numRow + 1; if (r >= lines.size() || idx >= lines[r].size()) return false; return (lines[r][idx] == '|');}// 获取 numRow 行, 第 idx 个数的子节点的下标范围// first 是左下标, second 是右下标 (first, second)// 如果不存在, 则返回 <-2, -2>pair
                 
                   getChildrenRange(const vector
                  
                   & lines, int numRow, int idx) { // 它的下一行同样下标必须是 | if (!hasChild(lines, numRow, idx)) return make_pair(-2, -2); // 下标范围就在下两行 int r = numRow + 2; if (r >= lines.size()) return make_pair(-2, -2); int first, second; for (first=idx; first>=0; first--) { if (lines[r][first] != '-') break; } for (second=idx; second

getChildrenIndex(const vector

& lines, int numRow, int idx) { pair

range = getChildrenRange(lines, numRow, idx); if (range.first == range.second) return vector

(); // 子节点在下三行 int r = numRow + 3; if (r >= lines.size()) return vector

(); vector

childrenIndex; for (int i=0; i

range.first && i < range.second && isNode(lines[r], i)) { childrenIndex.push_back(i); } } return childrenIndex;}// lines 是所有读入行, numRow 指的是当前操作行, idx 指的是操作数的下标Node* buildTree(const vector

& lines, int numRow, int idx) { assert(numRow < lines.size()); Node* root = new Node(); root->c_ = lines[numRow][idx]; vector

childrenIndex = getChildrenIndex(lines, numRow, idx); for (int i=0; i

children_).push_back(child); } return root;}// 打印树void printTree(Node* root) { if (root == NULL) return; printf("%c(", root->c_); vector

& children = root->children_; for (int i=0; i

> numTree; cin.ignore(); while (numTree--) { vector

lines; string line; int i = 0; while (getline(cin, line)) { if (line[0] == '#') break; lines.push_back(line); } if (lines.empty()) { cout << "()" << endl; continue; } int idx; // 获取第一个操作数, 建树 for (idx=0; idx

环境: C++ 4.5.3 - GNU C++ Compiler with options: -lm -lcrypt -O2 -pipe -DONLINE_JUDGE

转载于:https://my.oschina.net/zenglingfan/blog/151916

你可能感兴趣的文章