数据结构实验之二叉树二：遍历二叉树

2019-11-10 18:20:27

字体：大中小

来源：转载

供稿：网友

PRoblem Description

已知二叉树的一个按先序遍历输入的字符序列，如abc,,de,g,,f,,, (其中,表示空结点)。请建立二叉树并按中序和后序的方式遍历该二叉树。 Input

连续输入多组数据，每组数据输入一个长度小于50个字符的字符串。 Output

每组输入数据对应输出2行：第1行输出中序遍历序列；第2行输出后序遍历序列。

Example Input

abc,,de,g,,f,,,

Example Output

cbegdfacgefdba

Hint

Author xam

#include <iostream>#include <stdio.h>#include <stdlib.h>#include <string.h>using namespace std;typedef struct node{ char a; node *left; node *right;}Node;int top=0;struct node *creat(char *p)//建树方法{ Node *root=NULL; if(top<strlen(p)) { if(p[top]!=',') { root=(Node *)malloc(sizeof(Node)); root->left=NULL; root->right=NULL; root->a=p[top++]; root->left=creat(p); root->right=creat(p); } else { top++; } } return root;}void zhong(Node *root)//中序遍历，先序和后序类似{ if(root) { zhong(root->left); printf("%c", root->a); zhong(root->right); }}void hou(Node *root){ if(root) { hou(root->left); hou(root->right); printf("%c", root->a); }}int main(){ char p[60]; while(~scanf("%s", p)) { Node *root; top=0; root = creat(p); zhong(root); printf("/n"); hou(root); printf("/n"); }}

上一篇：队列的链式存储结构

下一篇：Qt tabwidget自定义样式