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

2018-02-10 20:14:10来源:cnblogs.com作者:Kukucao人点击

分享

根据输入的广义表建立子女右兄弟链的二叉树表示,该二叉树对应于广义表对应的普通树。先考虑更复杂的情形,如果广义表中存在共享表,则将其转换为带共享子树的二叉树表示,每一共享子树带有附加头节点,其左链指针指向共享子树,最后输出带共享子树的子女右兄弟链表示(广义表形式)

C++代码:

  1 #include "stdafx.h"  2 #include <iostream>  3 #include <stack>  4 #include <string>  5 #include <map>  6 #include <vector>  7 using namespace std;  8   9 class Dnode   //二叉树节点类 10 { 11 public: 12     char data; 13     Dnode *left; 14     Dnode *right; 15     Dnode(char d = '/0') :data(d), left(nullptr), right(nullptr) {} 16 }; 17  18 class info 19 { 20 public: 21     vector<int> left; 22     vector<int> right; 23     Dnode *share = nullptr; 24     vector<int>::size_type position = 0; 25 }; 26  27 int Searchd(Dnode *ptr, int d); 28 void creatsharelist(string &glist, map<string, info> &sharelist); 29 map<string, info>::iterator Searchshare(int left, map<string, info> &sharelist); 30  31 int main() 32 { 33     cout << "请输入广义表字符串形式" << endl; 34     string glist; 35     cin >> glist;     //输入广义表 36  37     map<string, info> sharelist; 38     creatsharelist(glist, sharelist); 39  40     stack<Dnode *> arrange; 41     Dnode *ptr = nullptr; 42  43     map<string, info>::iterator p; 44     for (string::size_type i = 0; i != glist.size(); i++)   //由广义表建子女右兄弟链二叉树 45     { 46         if (glist[i] == '(') 47         { 48             if (i == 0) 49             { 50                 ptr = new Dnode(); 51                 arrange.push(ptr); 52             } 53             else 54             { 55                 Dnode *temp = new Dnode(); 56                 if (arrange.top() == ptr) 57                 { 58                     if (arrange.size() != 1) 59                     { 60                         if (p != sharelist.end()) 61                         { 62                             p->second.share = temp; 63                         } 64                     } 65                      ptr->left=temp; 66                 } 67                 else 68                 { 69                     ptr->right = temp; 70                 } 71                 ptr = temp; 72  73                 if (glist[i + 1] != ')') 74                 { 75                     p = Searchshare(i + 1, sharelist); 76                     if (p != sharelist.end()) 77                     { 78                         if (p->second.share != nullptr) 79                         { 80                             i = p->second.right[p->second.position - 1] - 1; 81                             temp->left = p->second.share; 82                             continue; 83                         } 84                     } 85                 } 86                 arrange.push(ptr); 87             } 88         } 89         else 90         { 91             if (glist[i] == ')') 92             { 93                 ptr = arrange.top(); 94                 arrange.pop(); 95             } 96             else 97             { 98                 if (glist[i] != ',') 99                 {100                     Dnode *temp = new Dnode(glist[i]);101                     if (ptr == arrange.top())102                     {103                         if (p != sharelist.end())104                         {105                             p->second.share = temp;106                         }107                         ptr->left = temp;108                     }109                     else110                         ptr->right = temp;111                     ptr = temp;112                 }113             }114         }115     }116     //ptr指向二叉树根节点117     cout << "已将广义表字符串形式转化为子女右兄弟链表示" << endl;118     cout << "子女右兄弟链表示对应的广义表形式为:";119     cout << "(";120 121     int d = 0;122     Dnode *const dest = ptr;123     while (true)    //输出子女右兄弟链二叉树对应广义表形式124     {125         if (Searchd(ptr, d) == 0)126         {127             if (ptr == dest)128             {129                 if (d==0)130                   cout << ')';131                 break;132             }133             else134             {135                 if (d == 0)136                 {137                     if (ptr->data == '/0')138                         cout << "()";139                     else140                         cout << ptr->data;141                     cout << ")";142                 }143                 else144                 {145                     cout << ")";146                 }147                 ptr = arrange.top();148                 d = 1;149                 arrange.pop();150             }151         }152         else153         {154             Dnode *interval = nullptr;155             if (d == 0)156             {157                 if (ptr->left != nullptr)158                 {159                     if (ptr != dest)160                         cout << "(";161                     arrange.push(ptr);162                     interval = ptr->left;163                 }164                 else165                 {166                     if (ptr->data == '/0')167                     {168                         cout << "()";169                     }170                     else171                     {172                         cout << ptr->data;173                     }174                     cout << ",";175                     interval = ptr->right;176                 }177             }178             else179             {180                 cout << ",";181                 interval = ptr->right;182             }183             d = 0;184             ptr = interval;185         }186     }187     return 0;188 }189 190 int Searchd(Dnode *ptr, int d)191 {192     if (d == 2)193         return 0;194     else195     {196         if (d == 1)197         {198             if (ptr->right == nullptr)199                 return 0;200             else201                 return 2;202         }203         else204         {205             if (ptr->left != nullptr)206                 return 1;207             else208             {209                 if (ptr->right != nullptr)210                     return 2;211                 else212                     return 0;213             }214         }215     }216 }217 218 void creatsharelist(string &glist, map<string, info> &sharelist)219 {220     vector<int> stack;221     int total = 0;222     for (const auto &s : glist)223     {224         if (s == '(')225         {226             ++total;227             stack.push_back(total);228         }229         else if (s == ')')230         {231             ++total;232             string temp = glist.substr(stack[stack.size() - 1] - 1, total - stack[stack.size() - 1] + 1);233             auto p = sharelist.find(temp);234             if (p == sharelist.end())235             {236                 auto q = sharelist.insert(make_pair(temp, *(new info)));237                 q.first->second.left.push_back(stack[stack.size() - 1]);238                 q.first->second.right.push_back(total);239             }240             else241             {242                 p->second.left.push_back(stack[stack.size() - 1]);243                 p->second.right.push_back(total);244             }245             stack.pop_back();246         }247         else248         {249             ++total;250         }251     }252 253     auto m = sharelist.begin();254     while (m != sharelist.end())255     {256         if (m->second.left.size() == 1 || m->first=="()")257             m = sharelist.erase(m);258         else259             ++m;260     }261 }262 263 map<string, info>::iterator Searchshare(int left, map<string, info> &sharelist)264 {265     auto p = sharelist.begin();266     for (; p != sharelist.end(); ++p)267     {268         if (p->second.left.size() != p->second.position && p->second.left[p->second.position] == left)269         {270             ++p->second.position;271             return p;272         }273     }274     return p;275 }

运行结果:

广义表无共享表情形相对简单:

  1 #include "stdafx.h"  2 #include <iostream>  3 #include <stack>  4 #include <string>  5 using namespace std;  6   7 class Dnode  8 {  9 public: 10     char data; 11     Dnode *left; 12     Dnode *right; 13     Dnode(char d = '/0') :data(d), left(nullptr), right(nullptr) {} 14 }; 15 int Searchd(Dnode *ptr, int d); 16  17 int main() 18 { 19     cout << "请输入广义表字符串形式" << endl; 20     string glist; 21     cin >> glist; 22     stack<Dnode *> arrange; 23     Dnode *ptr = nullptr; 24  25     for (string::size_type i = 0; i != glist.size(); i++) 26     { 27         if (glist[i] == '(') 28         { 29             if (i == 0) 30             { 31                 ptr = new Dnode(); 32                 arrange.push(ptr); 33             } 34             else 35             { 36                 Dnode *temp = new Dnode(); 37                 if (arrange.top() == ptr) 38                 { 39                      ptr->left=temp; 40                 } 41                 else 42                 { 43                     ptr->right = temp; 44                 } 45                 ptr = temp; 46                 arrange.push(ptr); 47             } 48         } 49         else 50         { 51             if (glist[i] == ')') 52             { 53                 ptr = arrange.top(); 54                 arrange.pop(); 55             } 56             else 57             { 58                 if (glist[i] != ',') 59                 { 60                     Dnode *temp = new Dnode(glist[i]); 61                     if (ptr == arrange.top()) 62                         ptr->left = temp; 63                     else 64                         ptr->right = temp; 65                     ptr = temp; 66                 } 67             } 68         } 69     } 70     //ptr指向二叉树根节点 71     cout << "已将广义表字符串形式转化为子女右兄弟链表示" << endl; 72     cout << "子女右兄弟链表示对应的广义表形式为:"; 73     cout << "("; 74  75     int d = 0; 76     Dnode *const dest = ptr; 77     while (true) 78     { 79         if (Searchd(ptr, d) == 0) 80         { 81             if (ptr == dest) 82             { 83                 if (d==0) 84                   cout << ')'; 85                 break; 86             } 87             else 88             { 89                 if (d == 0) 90                 { 91                     if (ptr->data == '/0') 92                         cout << "()"; 93                     else 94                         cout << ptr->data; 95                     cout << ")"; 96                 } 97                 else 98                 { 99                     cout << ")";100                 }101                 ptr = arrange.top();102                 d = 1;103                 arrange.pop();104             }105         }106         else107         {108             Dnode *interval = nullptr;109             if (d == 0)110             {111                 if (ptr->left != nullptr)112                 {113                     if (ptr != dest)114                         cout << "(";115                     arrange.push(ptr);116                     interval = ptr->left;117                 }118                 else119                 {120                     if (ptr->data == '/0')121                     {122                         cout << "()";123                     }124                     else125                     {126                         cout << ptr->data;127                     }128                     cout << ",";129                     interval = ptr->right;130                 }131             }132             else133             {134                 cout << ",";135                 interval = ptr->right;136             }137             d = 0;138             ptr = interval;139         }140     }141     return 0;142 }143 144 int Searchd(Dnode *ptr, int d)145 {146     if (d == 2)147         return 0;148     else149     {150         if (d == 1)151         {152             if (ptr->right == nullptr)153                 return 0;154             else155                 return 2;156         }157         else158         {159             if (ptr->left != nullptr)160                 return 1;161             else162             {163                 if (ptr->right != nullptr)164                     return 2;165                 else166                     return 0;167             }168         }169     }170 }

运行结果:

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台