二叉树的遍历，叶子数目以及深度

2019-11-10 17:38:48

字体：大中小

来源：转载

供稿：网友

PRoblem Description 已知一个按先序序列输入的字符序列，如abc,,de,g,,f,,,(其中逗号表示空节点)。请建立二叉树并按中序和后序方式遍历二叉树，最后求出叶子节点个数和二叉树深度。

Input 输入一个长度小于50个字符的字符串。 Output 输出共有7行：第1行输出前序遍历序列；第2行输出中序遍历序列；第3行输出后序遍历序列；第4行输出层序遍历序列；第5行输出叶子节点个数；第6行输出叶子节点（从上到下，从左到右）；第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 ++; } }

叶子个数

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

最终代码：

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

上一篇：对符号表达式或函数表达式赋值

下一篇：八大排序算法详解——堆排序