企业官网建设流程全解析

将子女兄弟链表调整为普通树然后将普通树调整为子女兄弟链表，注意是在原树上直接进行调整，不是根据原树创建转换后的新树，为了操作方便，树指针域用vector表示

C++代码：

子女兄弟链表存在共享子树情形：

#include <iostream> #include <stack> #include <vector> #include <string> #include <map> using namespace std; class Dnode //二叉树和多叉树节点类 { public: char data; //树节点数据域 vector<Dnode*> p; //指针域vector Dnode(char d = '\0') :data(d) { p.push_back(nullptr); p.push_back(nullptr); } }; class dtreestacknode //遍历树时记录回退路径的栈节点 { public: Dnode* ptr; //树节点指针 int direction; //回退方向 dtreestacknode(int d, Dnode* p) :direction(d), ptr(p) {} }; class info //映射表中关键字对应的值类型 { public: int count = 0; //同一子树的引用计数 Dnode* p = nullptr; //子树附加头节点指针 info(int c, Dnode* ptr) :count(c), p(ptr) {} }; class infoshare { public: vector<int> left; vector<int> right; Dnode* share = nullptr; vector<int>::size_type position = 0; }; Dnode* strtodtree(); //广义表转换为子女右兄弟链表示的二叉树，返回二叉树根节点指针 int Searchd(Dnode* ptr, int d); //选择二叉树下一路径方向的函数 int Search(Dnode* ptr, int d); //选择多叉树下一路径方向的函数 void suboutput(Dnode* ptr); //输出子女右兄弟链表示 int Reversesearchd(Dnode* ptr, int d); //反向遍历二叉树时选择下一路径的函数 void creatsharelist(string& glist, map<string, infoshare>& sharelist); map<string, infoshare>::iterator Searchshare(int left, map<string, infoshare>& sharelist); int main() { Dnode* ptr = strtodtree(); //由广义表创建二叉树 const Dnode* const dest = ptr; stack<dtreestacknode> dstack; //记录遍历回退路径的栈 stack<Dnode*> tstack; //记录已遍历二叉树层次结构的栈 map<Dnode*, info> share; //映射表，保存子树第一个节点-对应info对象的键值对 int d = 3; while (true) //遍历子女右兄弟链二叉树建表 { int interval; if ((interval = Reversesearchd(ptr, d)) == 0) { if (ptr == dest) { if (d != 3) dstack.pop(); break; } else { if (d == 1) { dstack.pop(); } ptr = dstack.top().ptr; d = dstack.top().direction; } } else { Dnode* dir = nullptr; if (d == 3) { if (ptr != dest) { if (interval == 2) { dir = ptr->p[1]; if (ptr->p[0] == nullptr) { d = 3; ptr = dir; continue; } } else { auto p = share.find(ptr->p[0]); if (p != share.end()) { ++p->second.count; ptr = dstack.top().ptr; d = dstack.top().direction; continue; } else { info temp(1, ptr); share.insert(make_pair(ptr->p[0], temp)); dir = ptr->p[0]; } } } else { dir = ptr->p[0]; } dtreestacknode temp(interval, ptr); dstack.push(temp); } else { auto p = share.find(ptr->p[0]); if (p != share.end()) { ++p->second.count; dstack.pop(); ptr = dstack.top().ptr; d = dstack.top().direction; continue; } else { info temp(1, ptr); share.insert(make_pair(ptr->p[0], temp)); dir = ptr->p[0]; dstack.top().direction = interval; } } d = 3; ptr = dir; } } { auto m = share.begin(); //删除非共享子表对应的记录 while (m != share.end()) { if (m->second.count == 1) m = share.erase(m); else ++m; } } d = 3; int flag = 0; //重要变量,记录最近二叉树分支节点左链指针域是否被修改过 while (true) //循环,将vector容器实现指针域的子女右兄弟链二叉树直接修改为普通树，不是另外新建等价地普通树 { if (Reversesearchd(ptr, d) == 0) { if (ptr == dest) { if (d == 3) ptr->p.clear(); else { dstack.pop(); if (!tstack.empty()) tstack.pop(); } break; } else { if (d == 3) { if (!(dstack.top().ptr->p[0] != nullptr && dstack.top().direction == 1) || dstack.top().ptr->p[0] != ptr) { tstack.top()->p.push_back(ptr); if ((dstack.top().ptr->p[0] != nullptr && dstack.top().direction == 1) && dstack.top().ptr->p[0] != ptr) tstack.pop(); } else { tstack.pop(); } ptr->p.clear(); } else { if (d == 1) tstack.pop(); else ptr->p.clear(); dstack.pop(); } ptr = dstack.top().ptr; d = dstack.top().direction; } } else { Dnode* interval = nullptr; if (d == 3) { if (ptr != dest) { if (!(dstack.top().ptr->p[0] != nullptr && dstack.top().direction == 1)) { if (ptr->p[0] != nullptr) { auto p = share.find(ptr->p[0]); if (p != share.end()) { if (--p->second.count != 0) { dstack.top().ptr->p[1] = ptr->p[1]; delete ptr; tstack.top()->p.push_back(p->second.p); if (dstack.top().ptr->p[1] != nullptr) { ptr = dstack.top().ptr->p[1]; d = 3; } else { ptr = dstack.top().ptr; d = dstack.top().direction; } } else { tstack.top()->p.push_back(ptr); if (ptr->p[1] != nullptr) /// { dtreestacknode temp(2, ptr); dstack.push(temp); ptr = ptr->p[1]; d = 3; } else { flag = 0; ptr->p.pop_back(); tstack.push(ptr); dtreestacknode temp(1, ptr); dstack.push(temp); ptr = ptr->p[0]; d = 3; } } continue; } } tstack.top()->p.push_back(ptr); } else { if (ptr->p[0] != nullptr) { auto p = share.find(ptr->p[0]); if (p != share.end()) { --p->second.count; if (dstack.top().ptr->p[0] == ptr) { if (p->second.count != 0) { dstack.top().ptr->p[0] = p->second.p; flag = 1; } else { if (flag == 1) dstack.top().ptr->p.push_back(p->second.p); } } else { dstack.top().ptr->p.push_back(p->second.p); } if (p->second.count != 0) { Dnode* temp = ptr->p[1]; delete ptr; if (temp != nullptr) { ptr = temp; d = 3; } else { ptr = dstack.top().ptr; d = dstack.top().direction; } } else { if (ptr->p[1] != nullptr) // { dtreestacknode temp(2, ptr); dstack.push(temp); ptr = ptr->p[1]; d = 3; } else { flag = 0; ptr->p.pop_back(); tstack.push(ptr); dtreestacknode temp(1, ptr); dstack.push(temp); ptr = ptr->p[0]; d = 3; } } continue; } } if (dstack.top().ptr->p[0] != ptr) tstack.top()->p.push_back(ptr); } if (ptr->p[1] != nullptr) { dtreestacknode temp(2, ptr); dstack.push(temp); ptr = ptr->p[1]; d = 3; continue; } } dtreestacknode temp(1, ptr); dstack.push(temp); } else { dstack.top().direction = 1; } flag = 0; ptr->p.pop_back(); interval = ptr->p[0]; tstack.push(ptr); ptr = interval; d = 3; } } cout << "已将子女右兄弟链表示转换为普通树" << endl; d = 0; while (true) //循环，将普通树直接修改为子女右兄弟链二叉树，非另外新建 { if (Search(ptr, d) == 0) { if (d == 0) { ptr->p.push_back(nullptr); ptr->p.push_back(nullptr); if (ptr == dest) { break; } else { if (dstack.top().direction != 1) { dstack.top().ptr->p[dstack.top().direction - 2]->p[1] = ptr; } ptr = dstack.top().ptr; d = dstack.top().direction; } } else { if (ptr->p.size() == 1) { ptr->p.push_back(nullptr); } else { if (ptr->p.size() > 2) { while (ptr->p.size() > 2) ptr->p.pop_back(); } ptr->p[1] = nullptr; } dstack.pop(); if (ptr == dest) break; else { ptr = dstack.top().ptr; d = dstack.top().direction; } } } else { Dnode* interval = nullptr; if (d == 0) { if (ptr != dest) { auto p = share.find(ptr->p[0]); if (p != share.end()) { if (p->second.count == 0) { p->second.count = 1; } else { Dnode* temp = new Dnode(); temp->p[0] = ptr->p[0]; dstack.top().ptr->p[dstack.top().direction - 1] = temp; if (dstack.top().direction != 1) { dstack.top().ptr->p[dstack.top().direction - 2]->p[1] = temp; } ptr = dstack.top().ptr; d = dstack.top().direction; continue; } } if (dstack.top().direction != 1) { dstack.top().ptr->p[dstack.top().direction - 2]->p[1] = ptr; } } dtreestacknode temp(Search(ptr, d), ptr); dstack.push(temp); interval = ptr->p[Search(ptr, d) - 1]; } else { dstack.top().direction = Search(ptr, d); interval = ptr->p[Search(ptr, d) - 1]; } ptr = interval; d = 0; } } cout << "已将普通树转换为子女右兄弟链表示" << endl; cout << "转换后的子女右兄弟莲表示对应的广义表为" << endl; suboutput(ptr); //输出最终转换结果 return 0; } Dnode* strtodtree() { cout << "请输入广义表字符串形式" << endl; string glist; cin >> glist; map<string, infoshare> sharelist; creatsharelist(glist, sharelist); stack<Dnode*> arrange; Dnode* ptr = nullptr; map<string, infoshare>::iterator p; for (string::size_type i = 0; i != glist.size(); i++) { if (glist[i] == '(') { if (i == 0) { ptr = new Dnode(); arrange.push(ptr); } else { Dnode* temp = new Dnode(); if (arrange.top() == ptr) { if (arrange.size() != 1) { p = Searchshare(i + 1, sharelist); if (p != sharelist.end()) { p->second.share = temp; } } ptr->p[0] = temp; } else { ptr->p[1] = temp; } ptr = temp; if (glist[i + 1] != ')') { p = Searchshare(i + 1, sharelist); if (p != sharelist.end()) { if (p->second.share != nullptr) { i = p->second.right[p->second.position - 1] - 1; temp->p[0] = p->second.share; continue; } } } arrange.push(ptr); } } else { if (glist[i] == ')') { ptr = arrange.top(); arrange.pop(); } else { if (glist[i] != ',') { Dnode* temp = new Dnode(glist[i]); if (ptr == arrange.top()) { ptr->p[0] = temp; } else ptr->p[1] = temp; ptr = temp; } } } } cout << "已将广义表字符串形式转化为子女右兄弟链表示" << endl; return ptr; } int Searchd(Dnode* ptr, int d) { if (d == 2) return 0; else { if (d == 1) { if (ptr->p[1] == nullptr) return 0; else return 2; } else { if (ptr->p[0] != nullptr) return 1; else { if (ptr->p[1] != nullptr) return 2; else return 0; } } } } int Reversesearchd(Dnode* ptr, int d) { if (d == 1) return 0; else { if (d == 2) { if (ptr->p[0] == nullptr) return 0; else return 1; } else { if (ptr->p[1] != nullptr) return 2; else { if (ptr->p[0] != nullptr) return 1; else return 0; } } } } int Search(Dnode* ptr, int d) { if (d < ptr->p.size()) return d + 1; else return 0; } void suboutput(Dnode* ptr) { stack<Dnode*> arrange; int d = 0; Dnode* const dest = ptr; cout << "转换后的子女右兄弟链表示对应的广义表形式为:"; cout << "("; while (true) { if (Searchd(ptr, d) == 0) { if (ptr == dest) { if (d == 0) cout << ')'; break; } else { if (d == 0) { if (ptr->data == '\0') cout << "()"; else cout << ptr->data; cout << ")"; } else { cout << ")"; } ptr = arrange.top(); d = 1; arrange.pop(); } } else { Dnode* interval = nullptr; if (d == 0) { if (ptr->p[0] != nullptr) { if (ptr != dest) cout << "("; arrange.push(ptr); interval = ptr->p[0]; } else { if (ptr->data == '\0') { cout << "()"; } else { cout << ptr->data; } cout << ","; interval = ptr->p[1]; } } else { cout << ","; interval = ptr->p[1]; } d = 0; ptr = interval; } } cout << endl; } void creatsharelist(string& glist, map<string, infoshare>& sharelist) { vector<int> stack; int total = 0; for (const auto& s : glist) { ++total; if (s == '(') { stack.push_back(total); } else if (s == ')') { string temp = glist.substr(stack.back() - 1, total - stack.back() + 1); auto r = sharelist.insert(make_pair(temp, infoshare())).first; r->second.left.push_back(stack.back()); r->second.right.push_back(total); stack.pop_back(); } } auto m = sharelist.begin(); while (m != sharelist.end()) { if (m->second.left.size() == 1 || m->first == "()") m = sharelist.erase(m); else ++m; } } map<string, infoshare>::iterator Searchshare(int left, map<string, infoshare>& sharelist) { auto p = sharelist.begin(); for (; p != sharelist.end(); ++p) { if (p->second.left.size() != p->second.position && p->second.left[p->second.position] == left) { ++p->second.position; return p; } } return p; }

子女右兄弟链无共享子树情形(相对简单)：

#include "stdafx.h" #include <iostream> #include <stack> #include <vector> #include <string> using namespace std; class Dnode { public: char data; vector<Dnode *> p; Dnode(char d = '\0') :data(d) { p.push_back(nullptr); p.push_back(nullptr); } }; class dtreestacknode { public: Dnode *ptr; int direction; dtreestacknode(int d, Dnode *p) :direction(d), ptr(p) {} }; Dnode *strtodtree(); int Searchd(Dnode *ptr, int d); int Search(Dnode *ptr, int d); void suboutput(Dnode *ptr); int Reversesearchd(Dnode *ptr, int d); int main() { Dnode *ptr = strtodtree(); const Dnode *const dest = ptr; stack<dtreestacknode> dstack; stack<Dnode *> tstack; int d = 3; while (true) { if (Reversesearchd(ptr, d) == 0) { if (ptr == dest) { if (d == 3) ptr->p.clear(); else dstack.pop(); break; } else { if (d == 3) { if (!(dstack.top().ptr->p[0] != nullptr && dstack.top().direction == 1)) tstack.top()->p.push_back(ptr); ptr->p.clear(); } else { if (d == 1) tstack.pop(); else ptr->p.clear(); dstack.pop(); } ptr = dstack.top().ptr; d = dstack.top().direction; } } else { Dnode *interval = nullptr; if (d == 3) { if (ptr != dest) { if (!(dstack.top().ptr->p[0] != nullptr && dstack.top().direction == 1)) tstack.top()->p.push_back(ptr); if (ptr->p[1] != nullptr) { dtreestacknode temp(2, ptr); dstack.push(temp); interval = ptr->p[1]; ptr = interval; d = 3; continue; } } ptr->p.pop_back(); dtreestacknode temp(1, ptr); dstack.push(temp); interval = ptr->p[0]; tstack.push(ptr); } else { ptr->p.pop_back(); dstack.top().direction = 1; interval = ptr->p[0]; tstack.push(ptr); } ptr = interval; d = 3; } } cout << "已将子女右兄弟链表示转换为普通树"<<endl; d = 0; while (true) { if (Search(ptr, d) == 0) { if (d == 0) { ptr->p.push_back(nullptr); ptr->p.push_back(nullptr); if (ptr == dest) { break; } else { if (dstack.top().direction != 1) { dstack.top().ptr->p[dstack.top().direction - 2]->p[1] = ptr; } ptr = dstack.top().ptr; d = dstack.top().direction; } } else { if (ptr->p.size() == 1) { ptr->p.push_back(nullptr); } else { if (ptr->p.size() > 2) { while (ptr->p.size() > 2) ptr->p.pop_back(); } ptr->p[1] = nullptr; } dstack.pop(); if (ptr == dest) break; else { ptr = dstack.top().ptr; d = dstack.top().direction; } } } else { Dnode *interval=nullptr; if (d == 0) { if (ptr != dest) { if (dstack.top().direction != 1) { dstack.top().ptr->p[dstack.top().direction - 2]->p[1] = ptr; } } dtreestacknode temp(Search(ptr, d), ptr); dstack.push(temp); interval = ptr->p[Search(ptr, d) - 1]; } else { dstack.top().direction = Search(ptr, d); interval= ptr->p[Search(ptr, d) - 1]; } ptr = interval; d = 0; } } cout<<"已将普通树转换为子女右兄弟链表示"<<endl; suboutput(ptr); return 0; } Dnode *strtodtree() { cout << "请输入广义表字符串形式" << endl; string glist; cin >> glist; stack<Dnode *> arrange; Dnode *ptr = nullptr; for (string::size_type i = 0; i != glist.size(); i++) { if (glist[i] == '(') { if (i == 0) { ptr = new Dnode(); arrange.push(ptr); } else { Dnode *temp = new Dnode(); if (arrange.top() == ptr) { ptr->p[0] = temp; } else { ptr->p[1] = temp; } ptr = temp; arrange.push(ptr); } } else { if (glist[i] == ')') { ptr = arrange.top(); arrange.pop(); } else { if (glist[i] != ',') { Dnode *temp = new Dnode(glist[i]); if (ptr == arrange.top()) ptr->p[0] = temp; else ptr->p[1] = temp; ptr = temp; } } } } cout << "已将广义表字符串形式转化为子女右兄弟链表示" << endl; return ptr; } int Searchd(Dnode *ptr, int d) { if (d == 2) return 0; else { if (d == 1) { if (ptr->p[1] == nullptr) return 0; else return 2; } else { if (ptr->p[0] != nullptr) return 1; else { if (ptr->p[1] != nullptr) return 2; else return 0; } } } } int Reversesearchd(Dnode *ptr, int d) { if (d == 1) return 0; else { if (d == 2) { if (ptr->p[0] == nullptr) return 0; else return 1; } else { if (ptr->p[1] != nullptr) return 2; else { if (ptr->p[0] != nullptr) return 1; else return 0; } } } } int Search(Dnode *ptr, int d) { if (d < ptr->p.size()) return d + 1; else return 0; } void suboutput(Dnode *ptr) { stack<Dnode *> arrange; int d = 0; Dnode *const dest = ptr; cout << "转换后的子女右兄弟链表示对应的广义表形式为:"; cout << "("; while (true) { if (Searchd(ptr, d) == 0) { if (ptr == dest) { if (d == 0) cout << ')'; break; } else { if (d == 0) { if (ptr->data == '\0') cout << "()"; else cout << ptr->data; cout << ")"; } else { cout << ")"; } ptr = arrange.top(); d = 1; arrange.pop(); } } else { Dnode *interval = nullptr; if (d == 0) { if (ptr->p[0] != nullptr) { if (ptr != dest) cout << "("; arrange.push(ptr); interval = ptr->p[0]; } else { if (ptr->data == '\0') { cout << "()"; } else { cout << ptr->data; } cout << ","; interval = ptr->p[1]; } } else { cout << ","; interval = ptr->p[1]; } d = 0; ptr = interval; } } cout << endl; }