↓ 跳过正文
DogDu’s blog
DogDu’s blog
  1. Posts/

二叉树广义表表示和二叉树的转换

·1782 字·4 分钟· loading
算法与数据结构 数据结构与算法
DogDu
作者
DogDu
相信代码的力量，用实现驱动学习

数据结构课上老师提到“二叉树怎么创建”时，我突然意识到：如果靠手动一个节点一个节点去连，不仅慢，而且很不适合表达结构复杂的样例。相比之下，广义表更像是一种适合输入、输出和调试的树结构描述方式。

这篇文章就围绕这个问题展开，记录广义表表示法，以及它和常见二叉链表表示之间的转换实现。

首先给出二叉树定义：

代码块 · 共 5 行
struct node {     char ch;
node *l, *r;
node(char CH)     {         l = r = NULL;
ch = CH;
} };

然后是广义表表示的内容：

代码块 · 共 3 行
const int maxn = 1e5 + 10;
char ch[maxn];
int len;

说起来二叉树，肯定会想着第一个解法是递归。

定义是：dfs(node * &root,int &p) p用来指向字符串，root 是根节点。

这是调试了半天才整出来的代码，把注释删去了之后，确实很短，很符合递归的特点。

但是理解的成本相当高，不推荐。主要的难点是遇见逗号和右括号都需要return，不方便处理。

代码块 · 共 6 行
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;         }     } }

反而是非递归解法更简单，更容易理解。

代码块 · 共 3 行
// 非递归写法，确实反而比递归写法更加简单而且容易理解 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; // 修改，因为是引用型参数 }

然后可以用前序遍历和中序遍历验证

代码块 · 共 9 行
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

实际上，如果输入的是数字反而更具有普遍性，毕竟英文字母就那么几个（雾）。数字的处理办法也就是再写一个字符串转化成数字的函数罢了，略略略。

顺便再来一个二叉树转化成广义表：

代码块 · 共 17 行
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 ;
}

最后是全部的代码：

CPP 代码 · 共 28 行
#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; }