AcWing 3540. 二叉搜索树
原题链接
简单
作者:
pennyshuai
,
2022-07-12 13:31:54
,
所有人可见
,
阅读 135
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=500;
struct Node
{
int val;
int left;
int right;
}node[N];
int idx=1;//树的结点下标从1开始
int n;
void preorder(int i)
{
if(node[i].val==0) return;
cout<<node[i].val<<' ';
preorder(node[i].left);
preorder(node[i].right);
}
void inorder(int i)
{
if(node[i].val==0) return;
inorder(node[i].left);
cout<<node[i].val<<' ';
inorder(node[i].right);
}
void postorder(int i)
{
if(node[i].val==0) return;
postorder(node[i].left);
postorder(node[i].right);
cout<<node[i].val<<' ';
}
int main()
{
cin>>n;
for(int i=0;i<n;++i)
{
int a;
cin>>a;
int k=1;
while(true)
{
if(node[k].val==a) break;
if(node[k].val==0)
{
node[k]={a,++idx,++idx};//加入新的节点时,为该节点预留两个子节点位置
break;
}
if(node[k].val<a) k=node[k].right;
else if(node[k].val>a) k=node[k].left;
}
}
preorder(1);
cout<<endl;
inorder(1);
cout<<endl;
postorder(1);
return 0;
}