广播电视大学试题开放本科2006年1月开放本科 1010数据结构A1041.doc

文档介绍：卷号:1010(A)
广播电视大学秦皇岛电大试题库(.cn/test)2006年1月期末考试
“开放本科”计算机科学与技术专业
数据结构(上机)(A)试题
秦皇岛电大试题库(.cn/test)2006年1月
以下程序中根据以字符串形式所给出的用广义表表示的二叉树建立对应的存储结构,并输出二叉树的前序遍历、中序遍历、后序遍历。函数Preorder、Inorder、Postorder分别求二叉树的前序遍历、中序遍历、后序遍历。完成这三个成员函数的编程及调试,使程序能正常实现功能。
#include<>
#include<>
#include<> //给出使用字符串流对象的头文件
typedef char ElemType; //定义二叉树中元素的类型为字符型
struct BTreeNode { //定义二叉树的结点类型
ElemType data; //值域
BTreeNode* left; //左指针域
BTreeNode* right; //右指针域
};
void InitBTree(BTreeNode*& BT)
//初始化二叉树,即把树根指针置空
{
BT=NULL;
}
void CreateBTree(BTreeNode*& BT, char* a)
//根据字符串a所给出的用广义表表示的二叉树建立对应的存储结构
{
BTreeNode* s[10]; //s数组作为存储二叉树中根结点指针的栈使用
int top=-1; //top作为s栈的栈顶指针,初值为-1,表示空栈
BT=NULL; //给树根指针置空
BTreeNode* p; //定义p为指向二叉树结点的指针
int k; //用k作为处理结点的左子树和右子树的标记,k=1处理
//左子树,k=2处理右子树
istrstream ins(a); //把字符串a定义为输入字符串流对象ins
char ch;
ins>>ch; //从ins流对象(即字符串a)中顺序读入一个字符,
//字符串中的空格为字符之间的分隔符
while (ch!='@')
{ //每循环一次处理一个读入的字符,直到扫描到'@'字符为止
switch(ch)
{
case '(':
top++; s[top]=p; k=1; break;
case ')':
top--; break;
case ',':
k=2; break;
default:
p=new BTreeNode;
p->data=ch; p->left=p->right=NULL;
if(BT==NULL)
BT=p; //第一次生成的结点为整个树的根结点
else {
if(k==1) s[top]->left=p;
else s[top]->right=p;
}
} //switch end
ins>>ch;
} //while end
}
bool BTreeEmpty(BTreeNode* BT)
//判断一棵二叉树是否为空,若是则返回true,否则返回false
{
return