英伟达(NVIDIA)在线编程挑战赛-多叉树后序转先序

英伟达(NVIDIA)在线编程挑战赛--多叉树后序转先序

昨晚在1问1答平台上做了 英伟达(NVIDIA)在线编程挑战赛 的第二轮题目：给出一个多叉树的后序遍历，写出先序遍历。

昨天做题的时候一直纠结怎么把字符串中的数字取出来，想用strtok()来把字符串分开，由于自己不熟悉这个函数，试了几次还是没把数字读出来；最后直接拿指针指向字符串，如果指向的是数字，就保存起来。但这种方式读多位数时比较麻烦，比如样式输入里的第一个里面有个'10'，就不好读了。。。结果时间到了，编译没过。。

今天把题拿出来重新想一想，把非数字都换成空格，再用atoi()不就行了，atoi()遇见空格就停的嘛！！这么简单的，昨天就没想到！！

把代码贴出来：从后往前依次找每个根结点的叶子结点，在叶子节点上标记出该叶子节点的根，最后打印出来。

/*Sample code to read in test cases:*/#include <stdio.h>#include <string.h>#include <stdlib.h>#define NUM 1024//保存每个结点的编号，度，根typedef struct NodeInf{int number;int degree;int root;}NodeInf;//从后往前，递归查找每个根结点的叶子节点void f(NodeInf *node, int end){NodeInf *p = node + end, *q = node + end - 1;int tmp1 = (*p).degree;while (tmp1){//如果某个结点的还未找到根（即它的根还是初始化时的-1）if (q->root == -1){q->root = (*p).number;//保存此结点的根tmp1--;//如果此结点也是一个根（即度不为0）if (q->degree > 0){//递归f(node, end - (p - q));}}q--;}}//按先序打印void print(NodeInf *node, int length){NodeInf *p = node, *q = p;int num = (p + length - 1)->degree, root = (p + length - 1)->number;printf("%d,", root);//先打印根结点while (num){//然后从左往右查找此根的叶子结点if (q->root == root){if (q->degree == 0){printf("%d,", q->number);}//如果此叶子结点同时也是根结点，递归else if (q->degree > 0){print(node, q - p + 1);}num--;}q++;}}int main(){FILE * pFile;NodeInf *node;int i, length, num; char *p = NULL;char mystring[NUM];char sysInputFile[] = "data.txt";pFile = fopen(sysInputFile, "r");while (fgets(mystring, NUM, pFile)) {if (mystring == NULL) {continue;// Skip empty lines}else{// Do something with the linei = 0;length = 0;num = 0; p = mystring;//将非数字的字符换成空格while (*p){if (*p >= '0' && *p <= '9'){p++;continue;}*p = ' ';p++;num++;}//node申请空间，保存结点信息node = (NodeInf *)malloc(sizeof(NodeInf)*(num + 1)/2);p = mystring;num = 1;while (*p){if (*p >= '0' && *p <= '9'){if (num == 1){node[i].number = atoi(p);//保存结点编号}else if (num == 2){node[i].degree = atoi(p);//保存结点的度node[i].root = -1;//结点的根初始化为-1i++;num = 0;}num++;}//跳到下一个数字while (*p && *p != ' '){p++;}if (*p){p++;}}length = i;//保存结点的个数f(node, length - 1);print(node, length);free(node);//将最后一个逗号换成空格printf("\b ");printf("\n");//我想，能不能做到 直接不输出最后一个逗号，//而不是先输出再换成空格。}}fclose(pFile);return 0;}