PRoblem Description 已知一個按先序序列輸入的字符序列，如abc,,de,g,,f,,,(其中逗號表示空節(jié)點)。請建立二叉樹并按中序和后序方式遍歷二叉樹，最后求出葉子節(jié)點個數(shù)和二叉樹深度。
Input 輸入一個長度小于50個字符的字符串。 Output 輸出共有7行： 第1行輸出前序遍歷序列； 第2行輸出中序遍歷序列； 第3行輸出后序遍歷序列； 第4行輸出層序遍歷序列； 第5行輸出葉子節(jié)點個數(shù)； 第6行輸出葉子節(jié)點（從上到下，從左到右）； 第7行輸出二叉樹深度。
Example Input
abc,,de,g,,f,,,
Example Output
abcdegf cbegdfa cgefdba abcdefg 3 cfg 5
建樹
struct node *creat(struct node *t) { char c; c = str[i ++]; if (c == ',') t = NULL; else { t = (struct node *)malloc(sizeof(struct node)); t -> data = c; t -> l = creat(t -> l); t -> r = creat(t -> r); } return t; }前序遍歷
void qianxu(struct node *t) { if (t != NULL) { printf("%c", t -> data); qianxu(t -> l); qianxu(t -> r); }}中序遍歷
void zhonxu(struct node *t) { if (t != NULL) { zhonxu(t -> l); printf("%c",t -> data); zhonxu(t -> r); } }后序遍歷
void houxu(struct node *t) { if (t != NULL) { houxu(t -> l); houxu(t -> r); printf("%c",t -> data); }}層序遍歷
void cengxu(struct node *t) { int in = 0, out = 0; struct node *a[1050]; a[in ++] = t; while(in > out) { if (a[out] != NULL) { printf("%c",a[out] -> data); a[in ++] = a[out] -> l; a[in ++] = a[out] -> r; } out ++; } }葉子個數(shù)
void num(struct node *t) { if (t != NULL) { if (t -> l == NULL && t -> r == NULL) count ++; else { num(t -> l); num(t -> r); } } }葉子節(jié)點（從上到下，從左到右） 由層序遍歷修改而得
void cengxunum(struct node *t) { int in = 0; int out = 0; struct node *p[1050]; p[in ++] = t; while(in > out) { if (p[out] != NULL) { if (p[out] -> l == NULL &&p[out] -> r == NULL) { printf("%c",p[out] -> data); } else { p[in ++] = p[out] -> l; p[in ++] = p[out] -> r; } } out ++; } }二叉樹深度
int depth(struct node *t) { int d1, d2; if (t != NULL) { d1 = depth(t -> l); d2 = depth(t -> r); if (d1 > d2) return d1 + 1; else return d2 + 1; } return 0; }最終代碼：
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<math.h> struct node { char data; struct node *l, *r; }tree; struct node *creat(struct node *t); void qianxu(struct node *t); void zhonxu(struct node *t); void houxu(struct node *t); void cengxu(struct node *t); void num(struct node *t); void cengxunum(struct node *t); int depth(struct node *t); char str[1050]; int i; int count = 0; int main() { while(scanf("%s",str)!=EOF) { i = 0; struct node *tree = NULL; tree = creat(tree); qianxu(tree); printf("/n"); zhonxu(tree); printf("/n"); houxu(tree); printf("/n"); cengxu(tree); printf("/n"); num(tree); printf("%d/n",count); cengxunum(tree); printf("/n"); int de; de = depth(tree); printf("%d/n",de); } return 0; } struct node *creat(struct node *t) { char c; c = str[i ++]; if (c == ',') t = NULL; else { t = (struct node *)malloc(sizeof(struct node)); t -> data = c; t -> l = creat(t -> l); t -> r = creat(t -> r); } return t; } void zhonxu(struct node *t) { if (t != NULL) { zhonxu(t -> l); printf("%c",t -> data); zhonxu(t -> r); } } void houxu(struct node *t) { if (t != NULL) { houxu(t -> l); houxu(t -> r); printf("%c",t -> data); }}void qianxu(struct node *t) { if (t != NULL) { printf("%c", t -> data); qianxu(t -> l); qianxu(t -> r); }}void cengxu(struct node *t) { int in = 0, out = 0; struct node *a[1050]; a[in ++] = t; while(in > out) { if (a[out] != NULL) { printf("%c",a[out] -> data); a[in ++] = a[out] -> l; a[in ++] = a[out] -> r; } out ++; } } void num(struct node *t) { if (t != NULL) { if (t -> l == NULL && t -> r == NULL) count ++; else { num(t -> l); num(t -> r); } } } void cengxunum(struct node *t) { int in = 0; int out = 0; struct node *p[1050]; p[in ++] = t; while(in > out) { if (p[out] != NULL) { if (p[out] -> l == NULL &&p[out] -> r == NULL) { printf("%c",p[out] -> data); } else { p[in ++] = p[out] -> l; p[in ++] = p[out] -> r; } } out ++; } } int depth(struct node *t) { int d1, d2; if (t != NULL) { d1 = depth(t -> l); d2 = depth(t -> r); if (d1 > d2) return d1 + 1; else return d2 + 1; } return 0; }新聞熱點
疑難解答
