二叉樹簡單歸納（前序,中序，后序，層序遍歷，葉子數(shù)目，樹深度）

2019-11-11 03:06:55

字體：大中小

供稿：網(wǎng)友

PRoblem Description 已知一個(gè)按先序序列輸入的字符序列，如abc,,de,g,,f,,,(其中逗號(hào)表示空節(jié)點(diǎn))。請(qǐng)建立二叉樹并按中序和后序方式遍歷二叉樹，最后求出葉子節(jié)點(diǎn)個(gè)數(shù)和二叉樹深度。

Input 輸入一個(gè)長度小于50個(gè)字符的字符串。 Output 輸出共有7行：第1行輸出前序遍歷序列；第2行輸出中序遍歷序列；第3行輸出后序遍歷序列；第4行輸出層序遍歷序列；第5行輸出葉子節(jié)點(diǎn)個(gè)數(shù)；第6行輸出葉子節(jié)點(diǎn)（從上到下，從左到右）；第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 ++; } }

葉子個(gè)數(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é)點(diǎn)（從上到下，從左到右） 由層序遍歷修改而得

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; }

上一篇：Promise初見

下一篇：Instrumentation