数据结构课上老师问二叉树怎么创建，我突然蒙蔽了一下。如果一个一个节点的指定，不仅慢而且内容太多不好处理。感觉广义表的表示方法比较好用，但是好像很少有写这个代码的，老师上课的代码也是一闪而过，所以就有了这篇文章。

首先给出二叉树定义：

1
2
3
4
5
6
7
8
9
10
11
struct node
{
    char ch;
    node *l, *r;

    node(char CH)
    {
        l = r = NULL;
        ch = CH;
    }
};

点击并拖拽以移动

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

1
2
3
4
const int maxn = 1e5 + 10;

char ch[maxn];
int len;

点击并拖拽以移动

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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;
        }
    }
}

点击并拖拽以移动

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// 非递归写法，确实反而比递归写法更加简单而且容易理解
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; // 修改，因为是引用型参数
}

点击并拖拽以移动

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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 ;
}

点击并拖拽以移动

最后是全部的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
#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;
}

点击并拖拽以移动