C++, 简洁的二叉搜索树构造
题目描述
给一个可重复的数组构造二叉搜索树并遍历
思想
1) 以第一个点为根节点
2) 什么操作都从根节点出发
3) 当一个新点比根节点小时
当根节点有左儿子则 以左儿子为根递归
当根节点没有左儿子 将新店作为根节点的左儿子
4) 当一个新店比根节点大时类似3)
5) 注意不处理等于根节点的情况
6) 节点数值较小,我们直接以节点的大小作为节点的编号,即数组的下标
C++ 代码
#include <iostream>
using namespace std;
const int N = 1e4;
int n, a[N], l[N], r[N];
//a存储输入, l[root]存root的左儿子, r[root]存root的右儿子
//核心,二叉搜索树构造
void bt(int root, int t)
{
if (root > a[t])
{
if (l[root]) //初始是0,不为0就是有左儿子
{
bt(l[root], t);
}else {
l[root] = a[t];
}
}
else if (root < a[t])
{
if (r[root])
{
bt(r[root], t);
}else {
r[root] = a[t];
}
}
}
void z(int root)
{
if (l[root]) z(l[root]);
cout << root << ' ';
if (r[root]) z(r[root]);
}
void q(int root)
{
cout << root << ' ';
if (l[root]) q(l[root]);
if (r[root]) q(r[root]);
}
void h(int root)
{
if (l[root]) h(l[root]);
if (r[root]) h(r[root]);
cout << root << ' ';
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 2; i <= n; i++) bt(a[1], i);
//前中后序遍历输出树
q(a[1]);
puts("");
z(a[1]);
puts("");
h(a[1]);
return 0;
}