2493 - 数据结构/二叉树/创建与遍历
实验原理：
二叉树是最重要的一类树型结构。二叉链表是二叉树的一种比较直观和灵活的存储结构。在二叉链表中的每个结点由三部分组成：左孩子指针、右孩子指针和结点数据。
其中左右孩子指针分别指向本结点的左右孩子结点，如果一个结点的左右孩子不存在，则对应的指针记录为空值，C语言用NULL表示，画图时用^表示。
结点数据的数据类型应该根据实际应用选择，在本次实验中，为了方便输入和输出，我们选用字符类型。
输入创建原理：
二叉树虽然可以很复杂，但是创建二叉树可以用递归方式进行，代码只需要几行，下面我们用伪代码来描述创建流程：
１、结点* 创建结点函数(){
定义结点数据;
输入结点数据;
如果 结点数据为空 则返回NULL;//这里比较重要，我们规定输入字符^表示本结点不创建
创建结点* node;
赋值node的数据为刚刚输入的结点数据;
node.左孩子=创建结点函数();
node.右孩子=创建结点函数();
返回 node;
}
２、在需要创建整课二叉树的地方写上：
二叉树根结点 ＝ 创建结点函数()；
遍历原理：先根遍历、后根遍历、中根遍历原理，请自行补充，
实验步骤：
１、定义二叉链表结点类型；
２、实现二叉链表创建方法；
３、实现二叉链表的三种遍历方法；
４、实现主函数
思考题：
1：为什么很多数据结构会有遍历的需求？
2：如何干净地释放整棵二叉树动态申请的所有结点？
程欣宇2014年4月
题目输入
每行一棵非空的二叉树，每棵二叉树按先序遍历形式，空指针用字符^占位，如图的一棵二叉树。
如果读到一行的第一个字符就是^，表示没有更多输入了，程序退出。
测试时，每棵树不会超过20个结点。
输入是：
AB^DE^^^C^^
^
题目输出
对于每个二叉树，分别进行先根遍历、中根遍历、后根遍历，每种遍历结果输出一行。
输入/输出样例
题目输入
DL^^R^^ AB^DE^^^C^^ ^
题目输出
DLR LDR LRD ABDEC BEDAC EDBCA
提示
1、主函数可以采用以下流程
int main(){
定义结点指针;
do{
结点指针=创建结点函数();
if (结点指针非空){
先根遍历;换行
中根遍历;换行
后根遍历;换行
}
}while(结点指针非空);
return 0;
}
2、
如果不采用一次输入一行字符串处理其中每个字符，而是采用每次输入一个字符处理，需要略过空白换行等字符，如下：
char ch;
do{
scanf("%c",&ch);
}while(ch<=32);//确保读到一个非空白非换行的字符
C++解答
#include "stdio.h" //程欣宇2014年4月13日 struct BinNode { char data; BinNode *rchild; BinNode *lchild; BinNode(char d) { data=d; rchild=lchild=NULL; } ~BinNode() { if (lchild) delete lchild; if (rchild) delete rchild; } static BinNode* create() { char ch; do{ scanf("%c",&ch); }while(ch<=32); if (ch=='^') return NULL; BinNode *node=new BinNode(ch); node->lchild=create(); node->rchild=create(); return node; } void preTravel() { printf("%c",data); if (lchild) lchild->preTravel(); if (rchild) rchild->preTravel(); } void midTravel() { if (lchild) lchild->midTravel(); printf("%c",data); if (rchild) rchild->midTravel(); } void postTravel() { if (lchild) lchild->postTravel(); if (rchild) rchild->postTravel(); printf("%c",data); } }; int main() { BinNode *root; do{ root=BinNode::create(); if (root){ root->preTravel();printf("\n"); root->midTravel();printf("\n"); root->postTravel();printf("\n"); delete root; } }while(root); return 0; }
提示
1、主函数可以采用以下流程
int main(){
定义结点指针;
do{
结点指针=创建结点函数();
if (结点指针非空){
先根遍历;换行
中根遍历;换行
后根遍历;换行
}
}while(结点指针非空);
return 0;
}
2、
如果不采用一次输入一行字符串处理其中每个字符，而是采用每次输入一个字符处理，需要略过空白换行等字符，如下：
char ch;
do{
scanf("%c",&ch);
}while(ch<=32);//确保读到一个非空白非换行的字符