1.编写函数， 输入字符序列，建立二叉树。（√）
2.编写函数， 先序遍历二叉树。
3.编写函数， 中序遍历二叉树。（√）
4.编写函数， 后序遍历二叉树
5.编写一个主函数，在主函数中设计一个简单的菜单，分别调用上述函数。（√）
注意：因为代码为先序键入，所以输入时需以先序顺序输入，不必空格分开?
#include<stdio.h>
#include<iostream> //包含cout
#include<malloc.h>
using namespace std;//提前说明后cout函数行才不用专门加
typedef struct BiNode{ //二叉链表定义
char data;
struct BiNode *lchild,*rchild;//定义左孩子和右孩子指针
}BiTNode,*BiTree;
// 先序遍历的顺序建立二叉链表
void CreateBiTree(BiTree &T){
//按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T
char ch;
cin >> ch; //输入字符 第一空
if(ch=='#') T=NULL; //递归结束，建空树
else{
T=new BiTNode;//分配动态空间
T->data=ch; //生成根结点 第二空
CreateBiTree(T->lchild); //递归创建左子树 第三空
CreateBiTree(T->rchild); //递归创建右子树 第四空
} //else
} //CreateBiTree
void InOrderTraverse(BiTree T){
//中序遍历二叉树T的递归算法
if(T){
InOrderTraverse(T->lchild);//中序遍历左子树
cout << T->data;//输出T->data
InOrderTraverse(T->rchild);//遍历右
}
}
int main(){
int i;
BiTree t;
while(1){
printf("1、先序输入\n");
printf("2、中序输出\n");
printf("请选择：");
cin >> i;
switch(i){
case 1:CreateBiTree(t);break;
case 2:InOrderTraverse(t);
printf("\n");//将换行符写在这，避免输出段与菜单段连在一起出现
break;
}
}
system("pause");
return 0;
}
?
|