实验目的 1．掌握二叉树的存储实现。
2．掌握二叉树的遍历思想。
3．掌握二叉树的常见算法的程序实现。
实验要求 1．掌握二叉树的存储实现。
2．掌握二叉树的遍历思想。
3．掌握二叉树的常见算法的程序实现。
实验原理 1. 根据实验内容编程，上机调试、得出正确的运行程序。
2. 编译运行程序，观察运行情况和输出结果。
3. 写出实验报告（包括源程序和运行结果）。
实验步骤 1. 建立二叉树。
2、二叉树的三种遍历。
实验内容 #include<iostream.h>
#include<stdlib.h>
typedef char Elemtype;
struct btreeNode{
Elemtype data;
btreeNode*left;
btreeNode*right;
};
void preorder(btreeNode* bt)
{
if(bt!=NULL){
cout<<bt->data<<' ';
preorder(bt->left);
preorder(bt->right);
}}
void inorder(btreeNode* bt)
{
if(bt!=NULL) {
inorder(bt->left);
cout<<bt->data<<' ';
inorder(bt->right);
}}
void postorder(btreeNode* bt)
{
if(bt!=NULL) {
postorder(bt->left);
postorder(bt->right);
cout<<bt->data<<' ';
}
}
void initbtree(btreeNode*& bt)
{
bt=NULL;
}
void createbtree(btreeNode*& bt,char*a)
{
const int maxsize=20;
btreeNode*s[maxsize];
int top=-1;
bt=NULL;
btreeNode*p;
int k;
int i=0;
while (a[i])
{
switch(a[i]) {
case' ':
break;
case'(':
if(top==maxsize-1) {
cout<<"栈空间太小，请增加maxsize的值!"<<endl;
exit(1);
}
top++;s[top]=p;k=1;
break;
case')':
if(top==-1){
cout<<"二叉树广义表字符串错!"<<endl; exit(1);
}
top--;break;
case',':
k=2;break;
default:
p=new btreeNode;
p->data=a[i];p->left=p->right=NULL;
if(bt==NULL) bt=p;
else {
if(k==1) s[top]->left=p;
else s[top]->right=p;
}
}
i++;
}
}
bool emptybtree(btreeNode*bt)
{
return bt==NULL;
}
void printbtree(btreeNode*bt)
{
if(bt!=NULL) {
cout<<bt->data;
if(bt->left!=NULL||bt->right!=NULL) {
cout<<'(';
printbtree(bt->left);
if(bt->right!=NULL)
cout<<',';
printbtree(bt->right);
cout<<')';
}
}
}
void main()
{
btreeNode* bt;
initbtree(bt);
char b[50];
cout<<"输入二叉树用广义表表示的字符串:"<<endl;
cin.getline(b,sizeof(b));
createbtree(bt,b);
printbtree(bt);cout<<endl;
cout<<"前序: ";preorder(bt);cout<<endl;
cout<<"中序: ";inorder(bt);cout<<endl;
cout<<"后序: ";postorder(bt);cout<<endl;
}
