根据广义表建立对应二叉树(子女兄弟链表表示)并由二叉树输出对应广义表(子女兄弟链表表示)的C++非递归算法-北京尧图网络

根据输入的广义表建立子女右兄弟链的二叉树表示该二叉树对应于广义表对应的普通树。先考虑更复杂的情形如果广义表中存在共享表则将其转换为带共享子树的二叉树表示每一共享子树带有附加头节点其左链指针指向共享子树最后输出带共享子树的子女右兄弟链表示(广义表形式)C代码#include iostream #include stack #include string #include map #include vector using namespace std; class Dnode //二叉树节点类 { public: char data; Dnode* left; Dnode* right; Dnode(char d \0) :data(d), left(nullptr), right(nullptr) {} }; class info { public: vectorint left; vectorint right; Dnode* share nullptr; vectorint::size_type position 0; }; int Searchd(Dnode* ptr, int d); void creatsharelist(string glist, mapstring, info sharelist); mapstring, info::iterator Searchshare(int left, mapstring, info sharelist); int main() { cout 请输入广义表字符串形式 endl; string glist; cin glist; //输入广义表 mapstring, info sharelist; creatsharelist(glist, sharelist); stackDnode* arrange; Dnode* ptr nullptr; mapstring, info::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-left temp; } else { ptr-right 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-left 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-left temp; } else ptr-right temp; ptr temp; } } } } //ptr指向二叉树根节点 cout 已将广义表字符串形式转化为子女右兄弟链表示 endl; cout 子女右兄弟链表示对应的广义表形式为:; cout (; int d 0; Dnode* const dest ptr; 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-left ! nullptr) { if (ptr ! dest) cout (; arrange.push(ptr); interval ptr-left; } else { if (ptr-data \0) { cout (); } else { cout ptr-data; } cout ,; interval ptr-right; } } else { cout ,; interval ptr-right; } d 0; ptr interval; } } return 0; } int Searchd(Dnode* ptr, int d) { if (d 2) return 0; else { if (d 1) { if (ptr-right nullptr) return 0; else return 2; } else { if (ptr-left ! nullptr) return 1; else { if (ptr-right ! nullptr) return 2; else return 0; } } } } void creatsharelist(string glist, mapstring, info sharelist) { vectorint 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, info())).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; } } mapstring, info::iterator Searchshare(int left, mapstring, info 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 string using namespace std; class Dnode { public: char data; Dnode *left; Dnode *right; Dnode(char d \0) :data(d), left(nullptr), right(nullptr) {} }; int Searchd(Dnode *ptr, int d); int main() { cout 请输入广义表字符串形式 endl; string glist; cin glist; stackDnode * 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-lefttemp; } else { ptr-right 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-left temp; else ptr-right temp; ptr temp; } } } } //ptr指向二叉树根节点 cout 已将广义表字符串形式转化为子女右兄弟链表示 endl; cout 子女右兄弟链表示对应的广义表形式为:; cout (; int d 0; Dnode *const dest ptr; while (true) { if (Searchd(ptr, d) 0) { if (ptr dest) { if (d0) 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-left ! nullptr) { if (ptr ! dest) cout (; arrange.push(ptr); interval ptr-left; } else { if (ptr-data \0) { cout (); } else { cout ptr-data; } cout ,; interval ptr-right; } } else { cout ,; interval ptr-right; } d 0; ptr interval; } } return 0; } int Searchd(Dnode *ptr, int d) { if (d 2) return 0; else { if (d 1) { if (ptr-right nullptr) return 0; else return 2; } else { if (ptr-left ! nullptr) return 1; else { if (ptr-right ! nullptr) return 2; else return 0; } } } }运行结果

根据广义表建立对应二叉树(子女兄弟链表表示)并由二叉树输出对应广义表(子女兄弟链表表示)的C++非递归算法

相关推荐

机试刷题（常见）

多叉树的运算

2021年wordpress国内最好用的网站优化插件

更多资讯

济南电工证啥时候考的？考前押题助你少走弯路

低压电工证理论考几题别怕挂科电子证书怎么考更稳妥

黄陵县高低压电工证怎么考？上岗必备全流程避坑指南

南通电工证发证单位考前押题怎么搞？工地太忙根本没时间复习考试

电工证考试及格线你知道多少？值不值得考

低压电工作业证书报名怎么报名？证书过期了不知道怎么复审延期

今日更新

电工证考试及格线你知道多少？值不值得考

南通电工证发证单位考前押题怎么搞？工地太忙根本没时间复习考试

黄陵县高低压电工证怎么考？上岗必备全流程避坑指南

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？

相关推荐

机试刷题（常见）

多叉树的运算

2021年wordpress国内最好用的网站优化插件

更多资讯

济南电工证啥时候考的？考前押题助你少走弯路

低压电工证理论考几题别怕挂科 电子证书怎么考更稳妥

黄陵县高低压电工证怎么考？上岗必备全流程避坑指南

南通电工证发证单位考前押题怎么搞？工地太忙根本没时间复习考试

电工证考试及格线你知道多少？值不值得考

低压电工作业证书报名怎么报名？证书过期了不知道怎么复审延期

今日更新

电工证考试及格线你知道多少？值不值得考

南通电工证发证单位考前押题怎么搞？工地太忙根本没时间复习考试

黄陵县高低压电工证怎么考？上岗必备全流程避坑指南

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗 良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？

低压电工证理论考几题别怕挂科电子证书怎么考更稳妥

新疆电工作业干活累吗良心建议助你避开考不过的坑