二叉树的创建与遍历
一、试验内容
根据输入的字符串创建树或二叉树，输出树或二叉树的先序遍历和后序遍历序列。

二、运行环境
Visual C++
三、需求分析
1、建立一棵用二叉链表方式存储的二叉树。

2、从键盘接受扩展先序序列，以二叉链表作为存储结构。

3、建立二叉树，并将遍历结果打印输出。

采用递归和非递归两种
方法实现。

四、设计概要
//——————二叉树的二叉链表存储表示——————
typedef struct BiTBode{
TElemType data;
Struct BiTNode *lchild, *rchild //左右孩子指针
}BiTNode, *BiTree;
//—————基本操作的函数原型说明————————
Status CreateBiTree(BiTree &T);
//按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树。

//构造二叉树链表表示的二叉树T。

Status PreOrderTraverse(BiTree T, status(*visit)(TElemType e));
//采用二叉链表存储结构，visit是对结点操作的应用函数。

//先序遍历二叉树T，对每个结点调用函数visit一次且仅以次。

//一旦visit（）失败，则操作失败。

Status PostOrderTraverse(BiTree T, status(*visit)(TElemType e));
//采用二叉链表存储结构，visit是对结点操作的应用函数。

//后序遍历二叉树T，对每个结点调用函数visit一次且仅以次。

//一旦visit（）失败，则操作失败。

—————先序遍历二叉树基本操作的递归算法————
Status PreOrderTraverse(BiTree T,Status(*visit)(TElemType e)){
//采用二叉链表存储结构，visit是对数据元素操作的应用函数，
//先序遍历二叉树T的递归算法，对每个数据元素调用函数visit。

//最简单的visit函数是：
// Status PrintElement(TElemType e) {//输出元素e的值
// printf(e); //实用时，加上格式窜
// return OK;
// }
//调用实例：PreOrderTraverse(T,PrintElement);
if(T) {
if (visit(T->data))
if(PreOrderTraverse(T->lchild,visit))
if(PreOrderTraverse(T->rchild,visit)) return OK;
return ERROR;
}else return OK;
}//PreOrderTraverse
五、源程序代码
#include<stdio.h>
#include<stdlib.h>
typedef struct BiTNode
{ char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
void CreatBiTree(BiTree &T) //先序创建二叉树
{char ch;
if((ch=getchar())=='\n') T=NULL;
else { T=(BiTNode*)malloc(sizeof(BiTNode));
if(!T) exit(1);
T->data=ch;
CreatBiTree(T->lchild);
CreatBiTree(T->rchild);
}
}
void PreTravel(BiTree &T) //先序遍历
{if(T)
{
printf("%c",T->data);
PreTravel(T->lchild);
PreTravel(T->rchild);
}
}
void PostTravel(BiTree &T) //后序遍历
{if(T)
{
PostTravel(T->lchild);
PostTravel(T->rchild);
printf("%c",T->data);
}
}
void main()
{ BiTree T;
printf("请输入字符串:\n" );
CreatBiTree(T);
printf("先序遍历序列:\n");
PreTravel(T);
printf("\n");
printf("后序遍历序列:\n");
PostTravel(T);
printf("\n");
};
六、调试结果
1、输入ABC##DE#G##F### (#表示空格字符)
2、输入AGM##ST##WB#E (#表示空格字符)
输出遍历序列：。