作者:php枫羲 | 来源:互联网 | 2023-09-14 12:47
定义left[],right[]作为标记,记录但前节点是哪个点的左(右)孩子比如我们要对4,3,8,6,1。排序排好序后的二叉树如图:把这个过程在纸上用笔走一遍,你就会一目了然
定义left[], right[]作为标记,记录但前节点是哪个点的左(右)孩子
比如我们要对 4,3, 8,6,1。排序排好序后的二叉树如图:
把这个过程在纸上用笔走一遍,你就会一目了然。
#include
#include
#define N 1000
int l[N], r[N], key[N], flag, root;
void insert(int index, int x)
{
if(x <= key[index])
{
if(l[index] == -1) l[index] = flag;
else insert(l[index], x);
}
else
{
if(r[index] == -1) r[index] = flag;
else insert(r[index], x);
}
}
void InOrder(int index)
{
if(l[index] != -1) InOrder(l[index]);
printf("%d ", key[index]);
if(r[index] != -1) InOrder(r[index]);
}
int main()
{
int i, x, n;
memset(l, -1, sizeof(l));
memset(r, -1, sizeof(r));
scanf("%d", &n);
root = -1;
flag = 0;
for(i = 0; i {
scanf("%d", &x);
if(root == -1) key[++root] = x;
else
{
key[++flag] = x;
insert(root, x);
}
}
InOrder(root);
return 0;
}