已知二叉树的前序和中序后序 怎么用c求它的层次遍历

不建立二叉树行不行，可以的话最好不要建立

无需建立二叉树：
1. 获取当前前序序列的第一个元素并输出（按层次遍历）
2. 从对应的中序序列中找到该元素，该元素此时将二分中序序列中的元素
3. 依据划分出的两个序列，在前序序列中找到这两个序列（按照中序中序列的元素个数即可划分）
4. 对划分后的先序序列继续1, 2，3两步（要平行进行不能处理完一个序列再处理另一个序列）直到遍历全部元素，此时得到的序列即为层次遍历序列。
例如： 先序ABDECFG， 中序DBEAFCG
   按照算法：
1. 输出先序第一个元素A
2. 依据A得到中序划分后的两个序列DBE，FCG，因此此时序列第一个子序列的长度为3
   3.  由于划分后的左序列长度为3，先序中除A以外剩下的元素被划分为BDE、CFG
   4.  对先序序列BDE和CFG重复上面的步骤，先输出两个序列的先序第一个元素B、C
   5, 从中序序列DBE，FCG得到划分的子序列D、E和F、G，左序列的长度都为1
   6. 因此前序序列被划分为了D、E和F、G四个序列，接着输出D、E、F、G
  因此遍历的序列为ABCDEFG

#include #include #include struct treenode { struct treenode *left; struct treenode *right; char value; }; struct nodelist { struct treenode *node; struct nodelist *next; }; char *lrd1 = "debfca"; char *ldr1 = "dbeafc"; void dlrtree(struct treenode *root) { struct treenode *node = root; struct nodelist *last = null, *tmp = null, *ptr; ptr = (struct nodelist *)malloc(sizeof(struct nodelist)); if (ptr == null) return; ptr->node = root; ptr->next = null; last = ptr; printf("dlrtree:"); while(ptr != null) { node = ptr->node; printf("%c", node->value); if (node->left != null) { tmp = (struct nodelist *)malloc(sizeof(struct nodelist)); if (tmp == null) return; last->next = tmp; last = tmp; tmp->next = null; last->node = node->left; } if (node->right != null) { tmp = (struct nodelist *)malloc(sizeof(struct nodelist)); if (tmp == null) return; last->next = tmp; last = tmp; tmp->next = null; last->node = node->right; } tmp = ptr; ptr = ptr->next; free(tmp); } printf("\n"); } void replacechar(char *str) { int i; for (i = 0; i < strlen(str); i++) { if (str[i] == '+') str[i] = '|'; if (str[i] == '\\') str[i] = ' '; if (str[i] == '-') str[i] = ' '; } } void displaytree(struct treenode *root, char *deepstr) { int l; char *ptr; printf("%s%c\n", deepstr, root->value); l = strlen(deepstr) + 4; ptr = (char *)malloc(l); strcpy(ptr, deepstr); replacechar(ptr); if (root->left != null && root->right != null) { printf("%s |\n", ptr); strcat(ptr, " +-"); displaytree(root->left, ptr); strcpy(ptr, deepstr); replacechar(ptr); printf("%s |\n", ptr); strcat(ptr, " \\-"); displaytree(root->right, ptr); } else if (root->left != null) { printf("%s |\n", ptr); strcat(ptr, " \\-"); displaytree(root->left, ptr); } else if (root->right != null) { printf("%s |\n", ptr); strcat(ptr, " \\-"); displaytree(root->left, ptr); } return ; } struct treenode *createtree(struct treenode *root, char *lrdlst, char *ldrlst) { char *llrd, *lldr; char *rlrd, *rldr; int len; int i, k; len = strlen(lrdlst); llrd = (char *)malloc(len + 1); lldr = (char *)malloc(len + 1); rlrd = (char *)malloc(len + 1); rldr = (char *)malloc(len + 1); if (llrd == null || lldr == null || rlrd == null || rldr == null) { if (llrd != null) free(llrd); if (lldr != null) free(lldr); if (rlrd != null) free(rlrd); if (rldr != null) free(rldr); return null; } if (root == null && strlen(ldrlst) > 0) { root = (struct treenode *)malloc(sizeof(struct treenode)); if (root == null) { free(llrd); free(lldr); free(rlrd); free(rldr); return null; } } else if (root == null && strlen(ldrlst) == 0) { return null; } root->value = lrdlst[len - 1]; strcpy(lldr, ldrlst); *strchr(lldr, root->value) = 0; if (strlen(lldr) == 0) root->left = null; else { root->left = (struct treenode *)malloc(sizeof(struct treenode)); k = 0; for (i = 0; i < len; i++) { if (strchr(lldr, lrdlst[i]) != null) { llrd[k++] = lrdlst[i]; } } llrd[k] = 0; createtree(root->left, llrd, lldr); } strcpy(rldr, ldrlst); strcpy(rldr, strchr(rldr, root->value) + 1); if (strlen(rldr) == 0) root->right = null; else { root->right = (struct treenode *)malloc(sizeof(struct treenode)); k = 0; for (i = 0; i < len; i++) { if (strchr(rldr, lrdlst[i]) != null) { rlrd[k++] = lrdlst[i]; } } rlrd[k] = 0; createtree(root->right, rlrd, rldr); } free(llrd); free(lldr); free(rlrd); free(rldr); return root; } int main() { struct treenode * r; r = createtree(null, lrd1, ldr1); printf("tree view\n"); displaytree(r, ""); dlrtree(r); return 0;; }