POJ 2003 Hire and Fire (多重链表树结构好题) - c++编程基础

ing to the following rules:
Each line in the textual representation of the tree will contain exactly one name.
The first line will contain the CEO's name, starting in column 1.
The entire tree, or any sub-tree, having the form

will be represented in textual form as:

The output resulting from each print command in the input will be terminated by one line consisting of exactly 60 hyphens. There will not be any blank lines in the output.

Sample Input

VonNeumann
VonNeumann hires Tanenbaum
VonNeumann hires Dijkstra
Tanenbaum hires Stallings
Tanenbaum hires Silberschatz
Stallings hires Knuth
Stallings hires Hamming
Stallings hires Huffman
print
VonNeumann hires Shannon
fire Tanenbaum
print
fire Silberschatz
fire VonNeumann
print

Sample Output

VonNeumann
+Tanenbaum
++Stallings
+++Knuth
+++Hamming
+++Huffman
++Silberschatz
+Dijkstra
------------------------------------------------------------
VonNeumann
+Stallings
++Knuth
+++Hamming
+++Huffman
++Silberschatz
+Dijkstra
+Shannon
------------------------------------------------------------
Stallings
+Knuth
++Hamming
+++Huffman
+Dijkstra
+Shannon
------------------------------------------------------------

Source

Rocky Mountain 2004

题目链接：http://poj.org/problem?id=2003

题目大意：看题面和输入输出很恐怖的样子，其实题意很简答，一棵树
A hires B 表示把B做为A的儿子
fire A 表示把A结点去掉，去掉以后其第一个儿子结点到它的位置，然后其第一个孙子结点到其第一个儿子结点出，以此类推。。。直到叶子
print 表示按先序遍历，遍历整棵树，＋号个数表示当前点所在层的层数

题目分析：想到好的数据结构可以简化一大部分问题，像这种要对树上结点增删查的问题，我们采用多重链表来构树
多重链表结构体里有三个参数，点的名字，父指针，存储儿子指针的链表，还需要一个键值对存储作为子树根的结点对应的树指针，显然用map，具体操作看代码和注释吧

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include
       using namespace std; struct Tree { string name; //结点名字 Tree *fa; //结点父指针 list 
       
         son; //结点儿子指针链表 Tree() { fa == NULL; } }; map 
        
          mp; //结点与其树指针的键值对 void Print(int dep, Tree *now) //先序递归输出 { if(!now) return; for(int i = 0; i < dep; i++) printf(+); cout << now -> name << endl; for(list 
         
           :: iterator it = now -> son.begin(); it != now -> son.end(); it++) Print(dep + 1, *it); return; } void Fire(string del) { Tree *s = mp[del]; //得到该点的树指针 while((int)s -> son.size() != 0) //遍历最左位置 { //下面三步相当于把当前结点的儿子上移 s -> name = s -> son.front() -> name; mp[s -> name] = s; s = s -> son.front(); } //此时的s到达最左的叶子处，可以删除 mp.erase(del); //释放以del为根的子树 s -> fa -> son.remove(s); //将其从其父亲的儿子指针链表中删除 delete s; //删除s } void Hire(string fir, string sec) { Tree *f = mp[fir]; //得到父指针 Tree *s = new Tree(); //新建一个指针域 s -> fa = f; //将其指向父指针 s -> name = sec; //命名 mp[sec] = s; //建立其与树指针的键值关系 f -> son.push_back(s); //将其加入父亲的儿子指针链表中 return; } int main() { string rt, fir, sec; cin >> rt; Tree *root = new Tree(); mp[rt] = root; root -> name = rt; while(cin >> fir) { if(fir == print) { Print(0, root); printf(------------------------------------------------------------ ); } else if(fir == fire) { cin >> sec; Fire(sec); } else { string tmp; cin >> tmp >> sec; Hire(fir, sec); } } }

POJ 2003 Hire and Fire (多重链表 树结构 好题)(二)

POJ 2003 Hire and Fire (多重链表树结构好题)(二)