数据结构课上老师提到“二叉树怎么创建”时，我突然意识到：如果靠手动一个节点一个节点去连，不仅慢，而且很不适合表达结构复杂的样例。相比之下，广义表更像是一种适合输入、输出和调试的树结构描述方式。
这篇文章就围绕这个问题展开，记录广义表表示法，以及它和常见二叉链表表示之间的转换实现。
首先给出二叉树定义：
struct node
{
char ch;
node *l, *r;
node(char CH)
{
l = r = NULL;
ch = CH;
}
};然后是广义表表示的内容：
const int maxn = 1e5 + 10;
char ch[maxn];
int len;说起来二叉树，肯定会想着第一个解法是递归。
定义是：dfs(node * &root,int &p) p用来指向字符串，root 是根节点。
这是调试了半天才整出来的代码，把注释删去了之后，确实很短，很符合递归的特点。
但是理解的成本相当高，不推荐。主要的难点是遇见逗号和右括号都需要return，不方便处理。
void dfs(node *&root, int &p)
{
// 如果遇见逗号有两种情况，一个是左边是( 另一个是左边是字母
// 如果是括号，说明后边有字母，不应该再加，把这个逗号留给上一层处理，不然会漏掉字母
if (ch[p] == ',')
return;
else if (ch[p] == ')' || p >= len)
{
++p;
return;
}
else
{
root = new node(ch[p++]);
if (ch[p] == '(')
{
dfs(root->l, ++p);
if (ch[p] == ',')
++p;
// 如果直接++p或者直接p
//++p 可能会导致 (,C) 在返回时p指向C，导致漏过C
// p 可能会导致 D(B,C) 在返回时p指向逗号，而后面还有一个字母，导致直接返回，漏掉字母
dfs(root->r, p);
}
else // 如果字母后面是，或者) 直接返回上一层，统一处理
{
++p;
return;
}
}
}反而是非递归解法更简单，更容易理解。
// 非递归写法，确实反而比递归写法更加简单而且容易理解
void another_answer(node *&root)
{
if (len == 0) // 特判
{
root = NULL;
return;
}
int n = 0; // n用来迭代字符串
stack<node *> st;
node *p = root; // p指针用来迭代
p = new node(ch[n++]); // 同时让n指向下一个
// st.push(root);//不要直接push进去
while (n < len)
{
if (ch[n] == '(') // 如果有(，保存本地，进入下一层(先左边)
{
st.push(p);
p = p->l;
}
else if (ch[n] == ',') // 如果有逗号，显然是左边的结束了，进行上一层的右边
{
st.top()->l = p; // 保存左边的信息
p = st.top();
// st.pop(); //不要pop，因为上一层还有用
p = p->r;
}
else if (ch[n] == ')') // 如果是) ，说明这一层结束了
{
st.top()->r = p; // 保存后边
p = st.top(); // 返回上一层
st.pop(); // pop这一层
}
else
{
p = new node(ch[n]); // 是字母，建立新节点
}
++n;
}
root = p; // 修改，因为是引用型参数
}然后可以用前序遍历和中序遍历验证
void preshow(node *&root)
{
if (root == NULL)
return;
else
{
cout << root->ch;
preshow(root->l);
preshow(root->r);
}
}
void midshow(node *&root)
{
if (root == NULL)
return;
else
{
midshow(root->l);
cout << root->ch;
midshow(root->r);
}
}比如：输入是 A(B(,C),D(E,F))
就可以得到输出是：
ABCDEF
BCAEDF
实际上，如果输入的是数字反而更具有普遍性，毕竟英文字母就那么几个（雾）。数字的处理办法也就是再写一个字符串转化成数字的函数罢了，略略略。
顺便再来一个二叉树转化成广义表：
void convert(node*&root,string &str)
{
str.push_back(root->ch);
if(root->l&&root->r)
{
str.push_back('(');
convert(root->l,str);
str.push_back(',');
convert(root->r,str);
str.push_back(')');
}
else if(root->l)
{
str.push_back('(');
convert(root->l,str);
str.push_back(',');
str.push_back(')');
}
else if(root->r)
{
str.push_back('(');
str.push_back(',');
convert(root->r,str);
str.push_back(')');
}
else
return;
return ;
}最后是全部的代码：
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <stack>
#define ll long long
using namespace std;
struct node
{
char ch;
node *l, *r;
node(char CH)
{
l = r = NULL;
ch = CH;
}
};
const int maxn = 1e5 + 10;
char ch[maxn];
int len;
void convert(node*&root,string &str)
{
str.push_back(root->ch);
if(root->l&&root->r)
{
str.push_back('(');
convert(root->l,str);
str.push_back(',');
convert(root->r,str);
str.push_back(')');
}
else if(root->l)
{
str.push_back('(');
convert(root->l,str);
str.push_back(',');
str.push_back(')');
}
else if(root->r)
{
str.push_back('(');
str.push_back(',');
convert(root->r,str);
str.push_back(')');
}
else
return;
return ;
}
// 非递归写法，确实反而比递归写法更加简单而且容易理解
void another_answer(node *&root)
{
if (len == 0) // 特判
{
root = NULL;
return;
}
int n = 0; // n用来迭代字符串
stack<node *> st;
node *p = root; // p指针用来迭代
p = new node(ch[n++]); // 同时让n指向下一个
// st.push(root);//不要直接push进去
while (n < len)
{
if (ch[n] == '(') // 如果有(，保存本地，进入下一层(先左边)
{
st.push(p);
p = p->l;
}
else if (ch[n] == ',') // 如果有逗号，显然是左边的结束了，进行上一层的右边
{
st.top()->l = p; // 保存左边的信息
p = st.top();
// st.pop(); //不要pop，因为上一层还有用
p = p->r;
}
else if (ch[n] == ')') // 如果是) ，说明这一层结束了
{
st.top()->r = p; // 保存后边
p = st.top(); // 返回上一层
st.pop(); // pop这一层
}
else
{
p = new node(ch[n]); // 是字母，建立新节点
}
++n;
}
root = p; // 修改，因为是引用型参数
}
void dfs(node *&root, int &p)
{
// 如果遇见逗号有两种情况，一个是左边是( 另一个是左边是字母
// 如果是括号，说明后边有字母，不应该再加，把这个逗号留给上一层处理，不然会漏掉字母
if (ch[p] == ',')
return;
else if (ch[p] == ')' || p >= len)
{
++p;
return;
}
else
{
root = new node(ch[p++]);
if (ch[p] == '(')
{
dfs(root->l, ++p);
if (ch[p] == ',')
++p;
// 如果直接++p或者直接p
//++p 可能会导致 (,C) 在返回时p指向C，导致漏过C
// p 可能会导致 D(B,C) 在返回时p指向逗号，而后面还有一个字母，导致直接返回，漏掉字母
dfs(root->r, p);
}
else // 如果字母后面是，或者) 直接返回上一层，统一处理
{
++p;
return;
}
}
}
void preshow(node *&root)
{
if (root == NULL)
return;
else
{
cout << root->ch;
preshow(root->l);
preshow(root->r);
}
}
void midshow(node *&root)
{
if (root == NULL)
return;
else
{
midshow(root->l);
cout << root->ch;
midshow(root->r);
}
}
int main()
{
cin >> ch;
len = strlen(ch);
node *root;
int p = 0;
another_answer(root);
// dfs(root,p);
preshow(root);
cout << endl;
midshow(root);
cout<<endl;
string ans;
convert(root,ans);
cout<<ans;
cout << endl;
system("pause");
return 0;
}