#include <cstdio> #include <string> #include <iostream> #include <list> #include <map> using namespace std; struct Tree { string name; //结点名字 Tree *fa; //结点父指针 list <Tree *> son; //结点儿子指针链表 Tree() { fa == NULL; } }; map <string, Tree *> mp; //结点与其树指针的键值对 void Print(int dep, Tree *now) //先序递归输出 { if(!now) return; for(int i = 0; i < dep; i++) printf("+"); cout << now -> name << endl; for(list <Tree *> :: 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("------------------------------------------------------------\n"); } else if(fir == "fire") { cin >> sec; Fire(sec); } else { string tmp; cin >> tmp >> sec; Hire(fir, sec); } } } |
Double click to view unformatted code.