最有爹味的题解

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 9;
struct node {
    int va,l,r;
};
int n;
node tr[105];

void dfs1(int x){
    cout<<tr[x].va<<" ";
    if(tr[x].l)dfs1(tr[x].l);
    if(tr[x].r)dfs1(tr[x].r);
}
void dfs2(int x){
    
    if(tr[x].l)dfs2(tr[x].l);
    cout<<tr[x].va<<" ";
    if(tr[x].r)dfs2(tr[x].r);
}
void dfs3(int x){
    if(tr[x].l)dfs3(tr[x].l);
    if(tr[x].r)dfs3(tr[x].r);
    cout<<tr[x].va<<" ";
}

int main() {
    cin>>n;
	for (int i=1;i<=n;i++) {
        cin>>tr[i].va;
    }

    // 构建二叉搜索树
    //从2开始去找位置，因为1的位置固定是第一个
    for(int i=2;i<=n;i++){
        int j=1; //每次都从根开始去遍历
        while(true){
            if(tr[j].va > tr[i].va){//要插入的数字小,往左走
                if(tr[j].l==0){
                    tr[j].l = i; //爸爸，我来了
                    break;
                }else{//换一个爸爸
                    j=tr[j].l;
                }
            }else{
                if(tr[j].r==0){
                    tr[j].r = i; //爸爸，我来了
                    break;
                }else{//换一个爸爸
                    j=tr[j].r;
                }
            }
        }
    }
    // for(int i=1;i<=n;i++){
    //     cout<<tr[i].va<<" "<<tr[i].l<<" "<<tr[i].r<<endl;
    // }
	 dfs1(1);
     cout<<endl;
     dfs2(1);
     cout<<endl;
     dfs3(1);
     cout<<endl;
	return 0;
}