首页 > 代码库 > timus 1136 Parliament(思路过程)
timus 1136 Parliament(思路过程)
该题的意思(具体可以进链接 http://acm.timus.ru/problem.aspx?space=1&num=1136 ):给出二叉树的先序遍历的顺序,输出该二叉树后序遍历的顺序(其中该二叉树的根节点大于左节点、小于右节点)!
刚看到该题目的思路是用这样的数组存储:int arr[3003][4];
arr[i][0](i>=0&&i<=3000)存储第i个数的值
arr[i][1](i>=0&&i<=3000)存储第i个数的根节点的值
arr[i][2](i>=0&&i<=3000)存储第i个数的左节点的值
arr[i][2](i>=0&&i<=3000)存储第i个数的右节点的值
也可以写成结构体格式
struct Node
{
int key,left,right,root;
};
Node nn[3003];
按照这样的思路写出来对后续的更新是比较麻烦的
也想过用结构体指针去写,还是觉得比较繁琐!
后面改了种思路再写就发现简单多了
还是原来的数组 int arr[3003][4]
其中 arr[i][0](i>=0&&i<=3000)存储第i个数的值
arr[i][1](i>=0&&i<=3000)存储第i个数的根节点的位置
arr[i][2](i>=0&&i<=3000)存储第i个数的左节点的位置
arr[i][2](i>=0&&i<=3000)存储第i个数的右节点的位置
这样的存储也就有了和结构体指针等效的存储效果了。第x个位置上的左节点的值 arr[arr[x][2]][0]
从第x个节点处找最顶层的父节点(假设所有的点都隶属一棵树),把根节点值赋给re(一个整数)
re=x;
while(arr[re][1]!=-1) //第x个树根节点有值时,初始化数组值全为-1
{
re=arr[re][1];
}
后面的比较好弄了,先建树,如果对结果不是很有把握,可以输入一个数便输出对应的数组数据存储情况!
数据没有错就写后序遍历输出最后结果就行了!
timus 1136 Parliament(思路过程)