二叉树：由已知两种遍历求未知遍历

2019-11-10 17:17:27

字体：大中小

来源：转载

供稿：网友

已知前序和中序遍历求后序遍历序列

struct node *creat(char *a, char *b, int n) { struct node *ptr; char *p; int count = 0; if (n <= 0) return NULL; ptr = (struct node *)malloc(sizeof(struct node)); ptr -> data = *a; for (p = &b[0]; p <= b + n - 1;p ++) { if (*p == *a) break; } count = p - b; ptr -> l = creat(a + 1, b, count); ptr -> r = creat(a + 1 + count, p + 1, n - 1 - count); return ptr; }

已知中序和后序遍历求前序遍历序列

struct node *creat(char *a, char *b, int n) { struct node *ptr; if (n <= 0) return NULL; ptr = (struct node *)malloc(sizeof(struct node)); ptr -> data = b[n - 1]; int q = strchr(a, b[n - 1]) - a; ptr -> l = creat(a, b, q); ptr -> r = creat(a + q + 1, b + q, n - q - 1); return ptr; }

上一篇：Qt 出现“undefined reference to `vtable for”原因总结补情形

下一篇：两道状态压缩DP-- POJ 3254,HDU 1074