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

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

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                     else
110                         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             else
134             {
135                 if (d == 0)
136                 {
137                     if (ptr->data == '\0')
138                         cout << "()";
139                     else
140                         cout << ptr->data;
141                     cout << ")";
142                 }
143                 else
144                 {
145                     cout << ")";
146                 }
147                 ptr = arrange.top();
148                 d = 1;
149                 arrange.pop();
150             }
151         }
152         else
153         {
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                 else
165                 {
166                     if (ptr->data == '\0')
167                     {
168                         cout << "()";
169                     }
170                     else
171                     {
172                         cout << ptr->data;
173                     }
174                     cout << ",";
175                     interval = ptr->right;
176                 }
177             }
178             else
179             {
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     else
195     {
196         if (d == 1)
197         {
198             if (ptr->right == nullptr)
199                 return 0;
200             else
201                 return 2;
202         }
203         else
204         {
205             if (ptr->left != nullptr)
206                 return 1;
207             else
208             {
209                 if (ptr->right != nullptr)
210                     return 2;
211                 else
212                     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             else
241             {
242                 p->second.left.push_back(stack[stack.size() - 1]);
243                 p->second.right.push_back(total);
244             }
245             stack.pop_back();
246         }
247         else
248         {
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         else
259             ++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         else
107         {
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                 else
119                 {
120                     if (ptr->data == '\0')
121                     {
122                         cout << "()";
123                     }
124                     else
125                     {
126                         cout << ptr->data;
127                     }
128                     cout << ",";
129                     interval = ptr->right;
130                 }
131             }
132             else
133             {
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     else
149     {
150         if (d == 1)
151         {
152             if (ptr->right == nullptr)
153                 return 0;
154             else
155                 return 2;
156         }
157         else
158         {
159             if (ptr->left != nullptr)
160                 return 1;
161             else
162             {
163                 if (ptr->right != nullptr)
164                     return 2;
165                 else
166                     return 0;
167             }
168         }
169     }
170 }

运行结果：