仅用于练习二叉搜索树

构造一个二叉搜索树，编号从1开始，空节点用0表示。
允许有重复数字，用num数字记录重复。
本程序可以用插入方式构造一个简单的二叉搜素树，并用中序遍历输出。
即从小到大输出二叉树的权值。

#include <cstdio>
using namespace std;
const int N=1e5+10;
int l[N],r[N],val[N],num[N];//左右子树、节点权值、次数
int n,idx,root,x;//idx表待分配编号，root表当前节点，x表当前权值
//二叉搜索树的编号从1开始，0表示空节点，保证权值均不同。
inline add(int x){//构造一个节点并返回该节点的编号
    l[++idx]=0,r[idx]=0,val[idx]=x,num[idx]=1;//分配一个新编号，并初始化各个值
    return idx;//返回编号
}
void insert(int x,int root){//往二叉搜索树内插入一个权值为x的节点
    if(x==val[root]) {
        num[root]++;
        return;
    }
    if(x<val[root]){//若x小于根的权值
        if(l[root]==0) l[root]=add(x);//若根的左子树空，则构造一个值为x的节点挂到上面
        else insert(x,l[root]);//否则就继续递归
    }
    if(x>val[root]){//若x大于根的权值
        if(r[root]==0) r[root]=add(x);//若根右子树空，则构造值为x的节点挂上
        else insert(x,r[root]);//否则就继续递归
    }
}
void in(int root){//中序遍历
    if(root==0) return;
    if(l[root]!=0) in(l[root]);
    for(int i=0;i<num[root];i++) printf("%d",val[root]);
    if(r[root]!=0) in(r[root]);
}
int main(){
    scanf("%d%d",&n,&x);//接受n个节点和一个值x初始化根
    root=add(x);//初始化根
    for(int i=1;i<n;i++){//插入剩余的n-1个根
        scanf("%d",&x);
        insert(x,root);
    }
    in(root);//打印中序遍历
    return 0;
}

样例：

//输入
6
5 3 6 2 4 3
//输出：
233456