算法
数组模拟建树
用 l 数组和 r 数组分别存放当前结点左右子树的值, 若空则记为-1, 其他操作都是基础数据结构的操作
时间复杂度 $O(n)$
带注释版
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 110, M = 1010;
int n;
int w[N], l[M], r[M]; // w是输入的数组, w[0]就是根节点, l, r数组存放的是每个结点值对应左右子树结点的值, 若空记为-1
void dfs(int root, int x)
{
// 如果遍历到没有左子树且x小于这个结点值的, 直接加到其左子树上, 右子树同理
if (l[root] == -1 && x < root) l[root] = x, l[x] = -1, r[x] = -1;
else if (r[root] == -1 && x > root) r[root] = x, l[x] = -1, r[x] = -1;
// 递归判断
if (x > root) dfs(r[root], x);
else if (x < root) dfs(l[root], x);
}
void preoutput(int root) // 前序遍历: 先输出根节点, 然后遍历左子树和右子树
{
if (root == -1) return;
cout << root << ' ';
preoutput(l[root]), preoutput(r[root]);
}
void inoutput(int root) // 中序遍历: 先遍历左子树, 然后输出根节点, 最后遍历右子树
{
if (root == -1) return;
inoutput(l[root]);
cout << root << ' ';
inoutput(r[root]);
}
void postoutput(int root) // 后序遍历: 先遍历左子树和右子树, 然后输出根节点
{
if (root == -1) return;
postoutput(l[root]), postoutput(r[root]);
cout << root << ' ';
}
int main()
{
cin >> n;
for (int i = 0; i < n; i ++ ) cin >> w[i];
l[w[0]] = -1, r[w[0]] = -1; // 先把整棵树的根节点和左右子树整好
for (int i = 1; i < n; i ++ ) dfs(w[0], w[i]); // 然后对每个输入建树
preoutput(w[0]), puts("");
inoutput(w[0]), puts("");
postoutput(w[0]), puts("");
return 0;
}
纯代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110, M = 1010;
int n;
int w[N], l[M], r[M];
void dfs(int root, int x)
{
if (l[root] == -1 && x < root) l[root] = x, l[x] = -1, r[x] = -1;
else if (r[root] == -1 && x > root) r[root] = x, l[x] = -1, r[x] = -1;
if (x > root) dfs(r[root], x);
else if (x < root) dfs(l[root], x);
}
void preoutput(int root)
{
if (root == -1) return;
cout << root << ' ';
preoutput(l[root]), preoutput(r[root]);
}
void inoutput(int root)
{
if (root == -1) return;
inoutput(l[root]);
cout << root << ' ';
inoutput(r[root]);
}
void postoutput(int root)
{
if (root == -1) return;
postoutput(l[root]), postoutput(r[root]);
cout << root << ' ';
}
int main()
{
cin >> n;
for (int i = 0; i < n; i ++ ) cin >> w[i];
l[w[0]] = -1, r[w[0]] = -1;
for (int i = 1; i < n; i ++ ) dfs(w[0], w[i]);
preoutput(w[0]), puts("");
inoutput(w[0]), puts("");
postoutput(w[0]), puts("");
return 0;
}