数据结构实验之二叉树七：叶子问题

2019-11-08 18:47:01

字体：大中小

来源：转载

供稿：网友

PRoblem Description

已知一个按先序输入的字符序列，如abd,,eg,,,cf,,,(其中,表示空结点)。请建立该二叉树并按从上到下从左到右的顺序输出该二叉树的所有叶子结点。 Input

输入数据有多行，每一行是一个长度小于50个字符的字符串。 Output

按从上到下从左到右的顺序输出二叉树的叶子结点。 Example Input

abd,,eg,,,cf,,, xnl,,i,,u,, Example Output

dfg uli Hint

Author

xam

这个题就是用层序遍历的方法到达最后一层输出

#include<stdio.h>#include<string.h>#include<stdlib.h>char a[55];int top;struct node{ int data; struct node *l, *r;};struct node *creat(){ struct node *root; top++; if(a[top] == ',') root = NULL; else { root = (struct node*) malloc(sizeof(struct node)); root -> data = a[top]; root -> l = creat(); root -> r = creat(); } return root;};void yezi(struct node *root){ int in = 0, out = 0; struct node *p[100]; p[in++] = root; while(in > out) { if(p[out]) { if(p[out] -> l == NULL && p[out] -> r == NULL)//判断是不是叶子 printf("%c", p[out] -> data); p[in++] = p[out] -> l; p[in++] = p[out] -> r; } out++; }}int main(){ while(scanf("%s", a) != EOF) { top = -1; struct node *root; root = creat(); yezi(root); printf("/n"); } return 0;}

上一篇：进程产生死锁的原因

下一篇：1062. Talent and Virtue (25)