题目1485: 二叉链表存储的二叉树

题目描述树形结构是一类重要的非线性数据结构，其中以树和二叉树最为常用。对于每一个结点至多只有两课子树的一类树，称其为二叉树。二叉树的链式存储结构是一类重要的数据结构，其形式定义如下：而二叉树的前序、中序遍历是非常重要的能够访问二叉树所有结点的算法，下面分别列出一种先序遍历和两种中序遍历的算法。第一种中序遍历的方法（算法6.3）：第二种中序遍历的方法（算法6.2）：通过读入一个字符串，建立二叉树的算法如下：在本题中，将会给出一个按照先序遍历得出的字符串，空格代表空的子节点，大写字母代表节点内容。请通过这个字符串建立二叉树，并按照题目描述中的一种先序遍历和两种中序遍历的算法分别输出每一个非空节点。

输入输入只有一行，包含一个字符串S，用来建立二叉树。保证S为合法的二叉树先序遍历字符串，节点内容只有大写字母，且S的长度不超过100。
输出共有三行，每一行包含一串字符，表示分别按先序、中序、中序得出的节点内容，每个字母后输出一个空格。请注意行尾输出换行。
样例输入

ABC  DE G  F   

样例输出

A B C D E G F C B E G D F A C B E G D F A 

提示 [+]

*** 提示已隐藏，点击上方 [+] 可显示 ***

来源

数据结构算法教学题

/********************************* *    日期：2013-3-7 *    作者：SJF0115 *    题号: 天勤OJ 题目1485: 二叉链表存储的二叉树 *    来源：http://acmclub.com/problem.php?id=1485 *    结果：AC *    来源：数据结构算法教学题 *    总结：**********************************/#include<stdio.h>#include<stdlib.h>#include<string.h>char array[101];//二叉树结点typedef struct BiTNode{char data;struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;//按先序序列创建二叉树int CreateBiTree(BiTree &T,int &index,int &n){if(index >= n){return 0;}//按先序次序输入二叉树中结点的值（一个字符），空格表示空树if(array[index] == ' '){T = NULL;index++;}else{T = (BiTree)malloc(sizeof(BiTNode));//生成根结点T->data = array[index];index++;//构造左子树CreateBiTree(T->lchild,index,n);//构造右子树CreateBiTree(T->rchild,index,n);}return 0;}//输出void Visit(BiTree T){printf("%c ",T->data);}//先序遍历void PreOrder(BiTree T){if(T != NULL){//访问根节点Visit(T);//访问左子结点PreOrder(T->lchild);//访问右子结点PreOrder(T->rchild);}}//中序遍历void InOrder(BiTree T){if(T != NULL){//访问左子结点InOrder(T->lchild);//访问根节点Visit(T);//访问右子结点InOrder(T->rchild);}}//后序遍历void PostOrder(BiTree T){if(T != NULL){//访问左子结点PostOrder(T->lchild);//访问右子结点PostOrder(T->rchild);//访问根节点Visit(T);}}int main(){int len,index;while(gets(array)){BiTree T;len = strlen(array);index = 0;//创建二叉树CreateBiTree(T,index,len);//先序遍历PreOrder(T);printf("\n");//中序遍历index = 0;InOrder(T);printf("\n");//中序遍历index = 0;InOrder(T);printf("\n");}    return 0;}