10-BST(二叉树)-建立二叉搜索树，并进行前中后遍历

题目

来源

3540. 二叉搜索树 - AcWing题库

思路

建立二叉搜索树（注意传参时用到了引用，可以直接对root进行修改），同时进行递归遍历；遍历可以分前中后三种写，也可以用标志来代替合在一起。其余详见代码。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int l[N],r[N],w[N],idx;//l存储左子树，r存储右子树，w存储节点上的值
int root=0;
void insert(int& u,int x){ //加个引用，直接在root上可以做修改if(u==0) u=++idx,w[u]=x; //根节点为空，那么就需要建树else if(x<w[u])insert(l[u],x);else if(x>w[u])insert(r[u],x);//如果相等不需要处理
}
void dfs(int u,int t){if(u==0)return;if(t==0)cout<<w[u]<<" ";//前序遍历，先输出根节点dfs(l[u],t);//遍历左子树if(t==1)cout<<w[u]<<" ";//中序遍历，输出根节点dfs(r[u],t);if(t==2)cout<<w[u]<<" ";}int main(){int n;cin>>n;while(n--){int x;cin>>x;insert(root,x);}for(int i=0;i<3;i++)//做出三种遍历操作{dfs(root,i); //i=0,1,2分别表示前序，中序，后序遍历cout<<endl;}return 0;
}